为了数组中的每一个可能的序列 [英] Order array in every possible sequence

问题描述

我如果有一些较小的矩阵，适合到另一个大的矩阵，基本上测试一些复杂的计算算法。结果
这取决于小矩阵的顺序，如果所有的人都适合搬上大矩阵或不上了。
如果小矩阵不适合，应该重新安排ArrayList和再试，直到所有可能的顺序/序列进行了测试。

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.

如果我有5个小型矩阵，再有就是 5总额！ （= 120）可能令该阵列可以有。

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?

推荐答案

有关 N 对象有 N！排列。考虑一组：

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 }; 
          }
       }
   }
}

显然，我们不能有 N 为循环，但直到我们得到我们可以递归构建算法在列表ñ元素 P 。下面是实际的Java code。使用上述算法做置换：

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());
    }
}

下面是主要的方法：

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]

这篇关于为了数组中的每一个可能的序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！