Generazione di permutazioni di un set - con efficienza e con distinzione

Question

Sto costruendo sul codice da here. Mi piacerebbe per generare tutte le permutazioni di una serie, per esempio (tratto dal filo):

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

ci sono permutazioni possibili per ogni set, ma questo non è quello che mi piacerebbe realizzare. Prendere, oneroso, seguente gruppo:

ciò comporterebbe permutazioni delle amout estrema . Ciò richiederebbe un tempo molto lungo da calcolare, poiché ogni zero è considerato unico.

Piuttosto, mi piacerebbe generare solo permute distinte. Se lo facciamo, ci sono solo

permutazioni remaining, come 18 elementi sono identici (k).

Ora, potrei eseguire il codice dal thread menzionato e memorizzare i risultati in un HashSet, eliminando le permutazioni duplicate. Tuttavia, sarebbe estremamente inefficiente. Sto cercando un algoritmo per generare permutazioni con distinzione direttamente.

Answer 1

Con l'algoritmo di scambio per trovare le permutazioni è possibile escludere direttamente le parti che producono permutazioni duplicate. Questo algoritmo è disponibile su internet e puoi trovare maggiori informazioni a riguardo.

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

Ecco l'immagine che mostra come funziona l'algoritmo di scambio.

in modo da avere {A,B,C}, {A,C,B}, {B,A,C}, {B,C,A}, {C,B,A}, {C,A,B}

Consideriamo ora A e B sono uguali. Ho modificato l'immagine con Photoshop (scusate se è terribile!) E sostituito B con A. Come si può vedere nell'immagine

Ive ha identificato i duplicati in immagine. Se li si salta avrete {A,A,C}, {A,C,A}, {C,A,A}

Dovete memorizzare gli elementi che vengono scambiati in modo da se gli oggetti sono uguali e abbiamo già avuto che di swap saltiamo per evitare gonzi

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. 

Per il test se si elimina questa parte quindi questo algoritmo produrrà permutazioni duplicate e la console emetterà n!.

Answer 2

Proviamo:

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

Ops, non v'è alcun indice j tale che a[j] < a[j + 1].Ma dal momento che vogliamo tutti permutazioni distinte, possiamo ordinare ogni array e garanzia cominciamo dall'inizio:

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

Facciamo un po 'di più:

{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} 
... 

Come si può vedere, la grande elementi sono costantemente (e distintamente) spostandosi verso sinistra fino:

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

e termina senza duplicare permutazioni.

Answer 3

ho fatto questo problema prima. Devi solo ordinare prima l'array e quindi usare un array booleano [] visitato per contrassegnare gli elementi che hai visitato. La mia soluzione utilizzando backtracking, in 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

Questa è finora la soluzione migliore che ho trovato. Suggerimenti per l'ottimizzazione benvenuto. Restituisce esattamente n!/K! elementi.

Ci vuole circa un secondo per permutare {20, 4, 3, 3, 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; 
    } 
}