Lab 08, Esc101, 2004-05 Semester-II

Solve the following problems

Problem 1

Write a program which prints all permutations of the sequence of numbers 1,2,3, ... n for a given 'n' value. For example, if n is 3, the program should print

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Hint: Write a method

public static void permutationHelper(int[] prefix, int[] toPermute)

that computes all the permutations in the array toPermute and prints each permutation, prefixed by all numbers in the array prefix. For example, if prefix contains the number 2 and toPermute the numbers 1 and 3, then PermutationHelper prints

2 1 3
2 3 1

The permutationHelper method does the following: If toPermute has no elements, print the elements in prefix. Otherwise, for each element e in toPermute, make an array toPermute2, which is equal to permute except for e, and an array prefix2, consisting of prefix and e. Then call permutationHelper with prefix2 and toPermute2.

Problem 2

Write a method which takes two arrays of characters and a String object. This method should find the Union, Intersection or Difference of the two arrays according the value in the third argument and return the result as another array.

For ex. A = {'a', 'b' 'c'} B = {'a', 'd'}

If third argument is "Union" then return {'a', 'b', 'c', 'd'}
If third argument is "Intersection" then return {'a'}
If the third argument is "Difference" then return {'b', 'c'}

For further interest (not to be evaluated)

Problem 3

Given the list of boys and the girls on whom they had a crush (dated), as well as vice versa, how many perfect matchings are possible. A matching is perfect, if all the boys can be paired with exactly one girl, and each girl is also paired up with exactly one boy. A boy can be paired with a girl if and only if the boy had a crush on the girl and the girl too had a crush on the boy.

The biggest coincidence in this whole scenario is that the number of boys is equal to the number of girls.

Input

Take some n, i.e. the number of boys and two n X n matrices, A and B. A has an entry a_ij = 1 if the i^th boy had a crush on j^th girl. B has an entry b_ij = 1 if the i^th girl had a crush on the j^th boy. All other entries of the matrix will have a zero value.

Output

your program has to output the number of perfect matchings, as described above.

Sample Input 1:

n= 2

1 0
1 1

0 1
1 0

Sample Output 1:

0

Sample Input 2:

n = 2

1 0
1 1

1 0
0 1

Sample Output 2:

1