生成集合的排列 - 有效且具有區別

Question

我建立在代碼從here。我想生成一組的所有排列，例如（從線程獲取）：

Collection: 1, 2, 3 
Permutations: {1, 2, 3} 
       {1, 3, 2} 
       {2, 1, 3} 
       {2, 3, 1} 
       {3, 1, 2} 
       {3, 2, 1} 

有對每一組可能的排列，但這並不是想什麼，我來實現。舉個考慮，下面的一組：

這將產生排列的極端大寫金額。這需要很長的時間來計算，因爲每個零都被認爲是唯一的。

而不是那個，我想只產生不同的排列。如果我們這樣做，只有

排列remaining，18項是相同的（K）。

現在，我可以從提到的線程運行代碼並將結果存儲在HashSet中，從而消除重複的排列。但是，這將是非常低效的。我正在尋找一種算法來直接生成差異排列。

Answer 1

使用交換算法來查找排列，您可以直接排除產生重複排列的零件。這個算法在互聯網上可用，你可以找到更多關於它的信息。

private static void Main(string[] args) 
{ 
    List<int> set = new List<int> 
    { 
     20, 4, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 
    }; 
    var permutes = Permute(set); 

    Console.WriteLine(permutes.Count); // outputs 58140 
} 

private static List<int[]> Permute(List<int> set) 
{ 
    List<int[]> result = new List<int[]>(); 

    Action<int> permute = null; 
    permute = start => 
    { 
     if (start == set.Count) 
     { 
      result.Add(set.ToArray()); 
     } 
     else 
     { 
      List<int> swaps = new List<int>(); 
      for (int i = start; i < set.Count; i++) 
      { 
       if (swaps.Contains(set[i])) continue; // skip if we already done swap with this item 
       swaps.Add(set[i]); 

       Swap(set, start, i); 
       permute(start + 1); 
       Swap(set, start, i); 
      } 
     } 
    }; 

    permute(0); 

    return result; 
} 

private static void Swap(List<int> set, int index1, int index2) 
{ 
    int temp = set[index1]; 
    set[index1] = set[index2]; 
    set[index2] = temp; 
} 

這是顯示交換算法如何工作的圖像。

所以，你必須{A,B,C}, {A,C,B}, {B,A,C}, {B,C,A}, {C,B,A}, {C,A,B}

現在考慮A和B是相等的。我用photoshop編輯了圖像（對不起，如果我可怕的話）！並且用A代替B。正如你可以像

在看到香港專業教育學院確定了圖像副本。如果你跳過它們，你將有{A,A,C}, {A,C,A}, {C,A,A}

你必須以存儲交換，所以如果該項目是相等的項目，我們已經有這樣的交換，我們只是跳過防止受騙者

if (swaps.Contains(set[i])) continue; // skip if we already done swap with this item 
swaps.Add(set[i]); // else add it to the list of swaps. 

對於測試，如果你刪除這部分然後這個算法會產生重複的排列，控制檯會輸出n!。

Answer 2

讓我們試一下：

Knuths 
1. Find the largest index j such that a[j] < a[j + 1]. If no 
such index exists, the permutation is the last permutation. 

{20,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} 
    > > = = = = = = = = = = = = = = = = = 

哎呀，沒有索引j這樣a[j] < a[j + 1]。但是，因爲我們希望所有不同的排列組合，我們可以在每個陣列和保障，我們從頭開始進行排序：

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,20} 

1. Find the largest index j such that a[j] < a[j + 1]. If no 
such index exists, the permutation is the last permutation. 

j = 18 since a[18] < a[19] 

2. Find the largest index l such that a[j] < a[l]. Since j + 1 
is such an index, l is well defined and satisfies j < l. 

l = 19 since a[18] < a[19] 

3. Swap a[j] with a[l]. 

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,10} 

4. Reverse the sequence from a[j + 1] up to and including the final element a[n]. 

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,10} 

讓我們做幾個：

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,10} 
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,0,20} 
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,20,0} 
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,0,10} 
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,10,0} 
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,0,0,20} 
... 

正如你所看到的，大元素正在穩定（明顯地）向左移動，直到：

{10,20,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} 
yields {20,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} 

並且沒有重複的排列結束。

Answer 3

我以前做過這個問題。你只需要先對數組進行排序，然後使用一個布爾型[]訪問數組標記你訪問過的元素。我在Java中使用回溯的解決方案：

public class Solution { 
    public List<List<Integer>> permuteUnique(int[] num) { 
     List<List<Integer>> result = new ArrayList<List<Integer>>(); 
     List<Integer> list = new ArrayList<Integer>(); 
     boolean[] visited = new boolean[num.length]; 

     Arrays.sort(num); 
     helper(result, list, num, visited); 

     return result; 
    } 

    private void helper(List<List<Integer>> result, List<Integer> list, 
      int[] num, boolean[] visited) { 
     for (int i = 0; i < num.length; i++) { 
      if (visited[i] 
        || (i > 0 && num[i] == num[i - 1] && !visited[i - 1])) { 
       continue; 
      } 
      list.add(num[i]); 
      visited[i] = true; 
      if (list.size() == num.length) { 
       result.add(new ArrayList<Integer>(list)); 
      } else { 
       helper(result, list, num, visited); 
      } 
      list.remove(list.size() - 1); 
      visited[i] = false; 
     } 
    } 
} 

Answer 4

這是迄今爲止我所想到的最佳解決方案。建議優化歡迎。它完全返回n！/ k！項目。

大約需要一秒鐘，置換{20，圖4，3,3，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0， 0}。

private static IEnumerable<int[]> Permute(int[] list) 
{ 
    if (list.Length > 1) 
    {  
     int n = list[0]; 
     foreach (int[] subPermute in Permute(list.Skip(1).ToArray())) 
     {  
      for (int index = 0; index <= subPermute.Length; index++) 
      { 
       int[] pre = subPermute.Take(index).ToArray(); 
       int[] post = subPermute.Skip(index).ToArray(); 

       if (post.Contains(n)) 
        continue; 

       yield return pre.Concat(new[] { n }).Concat(post).ToArray(); 
      }  
     } 
    } 
    else 
    { 
     yield return list; 
    } 
}