以各種可能的順序排列陣列

我有一些複雜的計算算法，基本上可以測試一些較小的矩陣是否適合另一個大矩陣。
如果它們全部適合大矩陣，它取決於較小矩陣的順序。如果小矩陣不適合，它應該重新排列ArrayList並重試，直到所有可能的命令/序列都被測試。以各種可能的順序排列陣列

如果我有5個小矩陣，那麼總共有5！（= 120）數組可能具有的可能順序。

我的問題是，我不知道如何重新排列這些對象（矩陣），所以我可以測試每一個可能的順序。我希望有人能幫助我？

來源

2013-01-03 HD_92

這個鏈接可以幫助你http://cs.fit.edu/~ryan/java/programs/combinations/Permute-java.html來排列你的數組。 – kaysush

謝謝你的鏈接！這真的很有幫助。 –

對於n對象有n!排列。考慮一組：

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

算法找到置換爲上述設定的可能是：

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

顯然，我們不能有nfor循環，但直到我們得到的名單n元素，我們可以遞歸構建算法P。下面是實際的Java代碼中使用上述算法進行排列：

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

它打印的結果：

[1, 2, 3] 
[1, 3, 2] 
[2, 1, 3] 
[2, 3, 1] 
[3, 1, 2] 
[3, 2, 1]

來源

2013-01-03 05:24:42 Shivam

非常感謝您的詳細解答！這正是我所期待的。 –

以各種可能的順序排列陣列

回答

相關問題