Algorithme pour générer toutes les permutations possibles d’une liste?

Question

Dire que j'ai une liste de n éléments, je sais qu'il y a n! possible des moyens de commande de ces éléments. Qu'est ce qu'un algorithme permettant de générer tous les ordres possibles de cette liste? Exemple, j'ai la liste [a, b, c]. L'algorithme de retour [[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a]].

Je suis en train de lire ça ici http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

Mais Wikipédia n'a jamais été bon d'expliquer. Je ne comprends pas grand-chose.

Answer 1

En gros, pour chaque élément de gauche à droite, vous générer toutes les permutations des éléments restants. Vous pouvez faire cela de façon récursive, (ou de manière itérative si vous aimez la douleur) jusqu'à ce que vous obtenir le dernier élément à quel point il y a un seul ordre possible.

Ainsi, étant donné une liste: [1,2,3,4]

Vous venez de générer toutes les permutations qui commencent par 1, puis toutes les permutations qui commencent par 2, puis 3 et 4.

Cela permet de réduire efficacement le problème de trouver des permutations d'une liste de quatre éléments à une liste de trois éléments. Une fois que vous continuer à réduire à 2 puis 1 élément, vous disposez de tous.

Answer 2

Voici un algorithme en Python qui fonctionne en place sur un tableau:

 def permute(xs, low=0):
    if low + 1 >= len(xs):
        yield xs
    else:
        for p in permute(xs, low + 1):
            yield p        
        for i in range(low + 1, len(xs)):        
            xs[low], xs[i] = xs[i], xs[low]
            for p in permute(xs, low + 1):
                yield p        
            xs[low], xs[i] = xs[i], xs[low]

for p in permute([1, 2, 3, 4]):
    print p
 

Vous pouvez essayer le code par vous-même ici: http://repl.it/J9v

Answer 3

Wikipédia réponse à "l'ordre lexicographique" semble tout à fait explicite dans le livre de cuisine de style pour moi. Il cite un 14ème siècle, l'origine de l'algorithme!

J'ai juste écrit une rapide mise en œuvre en Java de la page Wikipedia de l'algorithme de vérification et il ne fut pas difficile. Mais ce que vous avez dans votre Q comme un exemple n'est PAS "la liste de toutes les permutations", mais "une LISTE de toutes les permutations", wikipédia ne sera pas beaucoup vous aider. Vous avez besoin d'un langage dans lequel la liste de permutations sont facilement construits. Et croyez-moi, les listes de quelques milliards de dollars ne sont pas souvent traités dans des langages impératifs. Vous voulez vraiment un non-stricte langage de programmation fonctionnel, dans lequel la liste de la première classe de l'objet, de sortir des trucs tout en ne rendant pas la machine à proximité de mort thermique de l'Univers.

C'est facile. Dans la norme Haskell ou modernes de PF langue:

-- perms of a list
perms :: [x] -> [[x]]
perms (a:as) = [bs1 ++ a:bs2 | bs <- bss, (bs1,bs2) <- splits bs] 
           where bss = perms as

et

-- list of ways of splitting a list into two parts
splits :: [x] -> [([x],[x])]
splits []     = [([],[])]
splits (a:as) = ([],a:as):[(a:bs,cs) |(bs,cs) <- splits as]

Answer 4

Comme l'a dit WhirlWind, vous commencez au début.

Vous échangez le curseur avec chaque valeur restante, y compris le curseur lui-même. Il s’agit de nouvelles instances (j’utilisais int[] et array.clone() dans l’exemple).

Ensuite, effectuez des permutations sur toutes ces différentes listes, en vous assurant que le curseur est à droite.

Lorsqu'il n'y a plus de valeurs restantes (le curseur se trouve à la fin), imprimez la liste. C'est la condition d'arrêt.

 public void permutate(int[] list, int pointer) {
    if (pointer == list.length) {
        //stop-condition: print or process number
        return;
    }
    for (int i = pointer; i < list.length; i++) {
        int[] permutation = (int[])list.clone();.
        permutation[pointer] = list[i];
        permutation[i] = list[pointer];
        permutate(permutation, pointer + 1);
    }
}
 

Answer 5

Récursive prend toujours un certain effort mental à maintenir. Et pour les grands nombres, factorielle est facilement énorme et de dépassement de pile sera facilement être un problème.

Pour les petits groupes (3 ou 4, ce qui est le plus souvent rencontrés), plusieurs boucles sont assez simple et direct. Il est regrettable réponses avec des boucles avais pas voté.

Commençons par énumération (plutôt que de permutation). Il suffit de lire le code du pseudo-code perl.

$foreach $i1 in @list
    $foreach $i2 in @list 
        $foreach $i3 in @list
            print "$i1, $i2, $i3\n"

L'énumération est plus souvent rencontré de permutation, mais si la permutation est nécessaire, il suffit d'ajouter les conditions:

$foreach $i1 in @list
    $foreach $i2 in @list 
        $if $i2==$i1
            next
        $foreach $i3 in @list
            $if $i3==$i1 or $i3==$i2
                next
            print "$i1, $i2, $i3\n"

Maintenant, si vous avez vraiment besoin de méthode générale potentiellement pour les grandes listes, on peut utiliser radix méthode. Tout d'abord, considérons le problème d'énumération:

$n=@list
my @radix
$for $i=0:$n
    $radix[$i]=0
$while 1
    my @temp
    $for $i=0:$n
        push @temp, $list[$radix[$i]]
    print join(", ", @temp), "\n"
    $call radix_increment

subcode: radix_increment
    $i=0
    $while 1
        $radix[$i]++
        $if $radix[$i]==$n
            $radix[$i]=0
            $i++
        $else
            last
    $if $i>=$n
        last

Radix incrément est essentiellement le nombre de comptage (dans la base de nombre d'éléments de liste).

Maintenant, si vous avez besoin d'permutaion, il suffit d'ajouter les contrôles à l'intérieur de la boucle:

subcode: check_permutation
    my @check
    my $flag_dup=0
    $for $i=0:$n
        $check[$radix[$i]]++
        $if $check[$radix[$i]]>1
            $flag_dup=1
            last
    $if $flag_dup
        next

Edit: Le code ci-dessus devrait fonctionner, mais pour la permutation, radix_increment pourrait être un gaspillage. Donc, si le temps est une préoccupation pratique, nous devons changer radix_increment en permute_inc:

subcode: permute_init
    $for $i=0:$n
        $radix[$i]=$i

subcode: permute_inc                                       
    $max=-1                                                
    $for $i=$n:0                                           
        $if $max<$radix[$i]                                
            $max=$radix[$i]                                
        $else                                              
            $for $j=$n:0                                   
                $if $radix[$j]>$radix[$i]                  
                    $call swap, $radix[$i], $radix[$j]     
                    break                                  
            $j=$i+1                                        
            $k=$n-1                                        
            $while $j<$k                                   
                $call swap, $radix[$j], $radix[$k]         
                $j++                                       
                $k--                                       
            break                                          
    $if $i<0                                               
        break                                              

Bien sûr, maintenant ce code est logiquement plus complexe, je vais partir pour le lecteur de l'exercice.