6

I have some complex calculation algorithm that basically tests if some smaller matrixes fit onto another big matrix.
It depends on the order of the smaller matrixes if all of them fit onto the big matrix or not. If the small matrixes don't fit, it should rearrange the ArrayList and try again until all possible orders/sequences were tested.

If I have 5 small matrixes, then there is a total amount of 5! (= 120) possible orders that the array can have.

My problem is that I have no idea on how to rearrange these objects (matrixes), so I can test every possible order. I hope someone can help me out?

HD_92
  • 197
  • 2
  • 13
  • 1
    this link can help you http://cs.fit.edu/~ryan/java/programs/combinations/Permute-java.html to permute your array. – kaysush Jan 03 '13 at 04:09

2 Answers2

14

For n objects there are n! permutations. Consider a set:

S = {a1, a2, a3 ..., an};

Algorithm to find permutation for above set could be:

foreach(item i : S) {
   /* all other item except i1 and i */
   foreach(item i1 : S - {i}) {
       foreach(item i2 : S - {i, i1}) {
          .
          .
          .
          foreach(item in : S - {i, i2, .... in-1}) {
             /* permutation list */
             P = { i1, i2, ...., in-1, in }; 
          }
       }
   }
}

Obviously we can not have n for loops but we can recursively construct this algorithm until we get n elements in list P. Below is the actual java code to do the permutation using above algorithm:

public static void 
permutations(Set<Integer> items, Stack<Integer> permutation, int size) {

    /* permutation stack has become equal to size that we require */
    if(permutation.size() == size) {
        /* print the permutation */
        System.out.println(Arrays.toString(permutation.toArray(new Integer[0])));
    }

    /* items available for permutation */
    Integer[] availableItems = items.toArray(new Integer[0]);
    for(Integer i : availableItems) {
        /* add current item */
        permutation.push(i);

        /* remove item from available item set */
        items.remove(i);

        /* pass it on for next permutation */
        permutations(items, permutation, size);

        /* pop and put the removed item back */
        items.add(permutation.pop());
    }
}

Here is the main method:

public static void main(String[] args) {
    // TODO Auto-generated method stub


    Set<Integer> s = new HashSet<Integer>();
    s.add(1);
    s.add(2);
    s.add(3);

    permutations(s, new Stack<Integer>(), s.size());
}

It printed the result:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
Shivam
  • 2,134
  • 1
  • 18
  • 28
1

There is a quite smarter solution if you are on Java > 8:

static Stream<List<Integer>> permutations(List<Integer> input) {
    if (input.size() == 1) {
        return Stream.of(new LinkedList<>(input));
    }
    return input.stream()
            .flatMap(first -> permutations(input.stream()
               .filter(a -> !a.equals(first))
               .toList())
            .map(LinkedList::new)
            .peek(l -> l.addFirst(first)));
}
Johannes Erchen
  • 134
  • 8