Friday, October 25, 2013

Permutaion Program

Let's see how we can apply permutation on the following input.
a, b,c
The expected output is,
a b c
a c b
b c a
b a c
c a b
c b a

The logic is simple. Each position p (where p>1) will have p rotations after which the next position is rotated.

input: abc
position:321

  • print (a, b, c)
  • rotate b  and print (a, c, b)
  • rotate c; (a, b, c) count exhausted. position 2 is already rotated 2 times
  • rotate next position which is a and print (b, c, a)
  • rotate c and print (b, a, c)
  • rotate a; (b, c, a) count exhausted. position 2 is already rotated 2 times
  • rotate next position which is b and print (c, a, b)
  • rotate a and print (c, b, a)
  • rotate b; (c, a, b) count exhausted. position 2 is already rotated 2 times
  • try rotating next position which is c
  • count is exhausted. position 3 is already rotated 3 times. look for next position
  • no more positions, hence terminate

public class Permutation {

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5,6);
        permute(list, list.size());
    }


    private static void permute(List<Integer> arr, int rotationCount) {
        int i = arr.size() - rotationCount;
        for (int j = 1; j <= rotationCount; j++) {
            if (rotationCount > 2) {
                permutateWorking(arr, rotationCount - 1);
            } else {
                System.out.println(arr.toString());
            }
            Collections.rotate(arr.subList(i, arr.size()), -1);
        }
    }
}