Permutations d'un ensemble de nombres donné

Question

Quelqu'un peut-il expliquer un bon algorithme pour trouver toutes les permutations d'un ensemble donné de nombres d'une manière efficace?

Answer 1

http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

Answer 2

Avez-vous regardé Knuth 'The Art of Computer Programming'? Le volume 3, Tri et Recherche le couvre, ce qui est logique car un tri crée une permutation particulière des données. Méfiez-vous des algorithmes combinatoires (et permutationnels) qui trouvent toutes les combinaisons ou permutations. Ils ont des coûts de notation Big-O très élevés.

Answer 3

Les approches les plus simples sont les méthodes récursives, c'est-à-dire, dans un pseudocode exécutable;

def permute(theseq): 
    if len(theseq) <= 1: 
    yield theseq 
    return 
    for i in range(len(theseq)): 
    theseq[0], theseq[i] = theseq[i], theseq[0] 
    for subperm in permute(theseq[1:]): 
     yield theseq[:1] + subperm 
    theseq[0], theseq[i] = theseq[i], theseq[0] 

au cas où vous n'êtes pas familier avec executable pseudocode, les notations [1:] et [:1] sont destinés à désigner (« tout sauf le premier » respecively et « juste le premier ») « tranches », et les deux missions identiques effectue les tâches suivantes: "échanger les 0e et 1e articles" et "les remettre en place" (c'est-à-dire les échanger de nouveau ;-). yield signifie "fournir ce résultat mais être prêt à continuer quand itéré sur", tandis que return signifie "nous avons tous terminé, bye bye!".

Il existe des approches un peu meilleures sur différents axes de performance, mais la première étape consiste à s'assurer que vous êtes totalement familier avec l'approche récursive fondamentale et que vous la comprenez bien - donc je m'arrête ici pour l'instant. Si et quand vous ne comprenez pleinement cette approche, pourquoi il bien et woks dandy, et comment et pourquoi il ne semble pas vraiment optimale de la performance, je serai heureux de développer cette réponse -)

Answer 4

Mon C# mise en œuvre du pseudocode Alex:

private int length; 
    private List<List<string>> permutations; 

    public List<List<string>> Generate(List<string> list) 
    { 
     length = list.Count; 
     permutations = new List<List<string>>(); 

     foreach(List<string> subperms in Recursive(list)) 
      permutations.Add(subperms); 

     return permutations; 
    } 

    private List<List<string>> Recursive(List<string> list) 
    { 
     List<List<string>> subperms = new List<List<string>>(); 

     if (list.Count <= 1) 
     { 
      subperms.Add(list); 
      return subperms; 
     } 

     for (int i = 0; i < list.Count; i++) 
     { 
      string temp = list[0]; 
      list[0] = list[i]; 
      list[i] = temp; 

      List<string> tail = new List<string>(list); 
      tail.RemoveAt(0); 

      List<string> head = new List<string>(); 
      head.Add(list[0]); 

      foreach (List<string> subperm in Recursive(tail)) 
      { 
       List<string> headCopy = new List<string>(head); 
       headCopy.AddRange(subperm); 

       if (headCopy.Count == length) 
        permutations.Add(headCopy); 
       else 
        subperms.Add(headCopy); 
      } 

      temp = list[0]; 
      list[0] = list[i]; 
      list[i] = temp; 
     } 

     return subperms; 
    }