Comment générer toutes les permutations d'une liste?

592

Comment générer toutes les permutations d'une liste en Python, indépendamment du type d'éléments dans cette liste?

Par exemple:

permutations([])
[]

permutations([1])
[1]

permutations([1, 2])
[1, 2]
[2, 1]

permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
Ricardo Reyes
la source
5
Je suis d'accord avec la réponse récursive et acceptée - AUJOURD'HUI. Cependant, cela reste un problème informatique énorme. La réponse acceptée résout ce problème avec une complexité exponentielle (2 ^ NN = len (liste)) Résolvez-le (ou prouvez que vous ne pouvez pas) en temps polynomial :) Voir "problème du voyageur de commerce"
FlipMcF
38
@FlipMcF Il sera difficile de le "résoudre" en temps polynomial, étant donné qu'il faut du temps factoriel pour simplement énumérer la sortie ... donc, non, ce n'est pas possible.
Thomas

Réponses:

489

A partir de Python 2.6 (et si vous êtes sur Python 3) vous disposez d' un standard bibliothèque outil pour cela: itertools.permutations.

import itertools
list(itertools.permutations([1, 2, 3]))

Si vous utilisez un ancien Python (<2.6) pour une raison quelconque ou si vous êtes simplement curieux de savoir comment cela fonctionne, voici une belle approche, tirée de http://code.activestate.com/recipes/252178/ :

def all_perms(elements):
    if len(elements) <=1:
        yield elements
    else:
        for perm in all_perms(elements[1:]):
            for i in range(len(elements)):
                # nb elements[0:1] works in both string and list contexts
                yield perm[:i] + elements[0:1] + perm[i:]

Quelques approches alternatives sont répertoriées dans la documentation de itertools.permutations. En voici un:

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

Et un autre, basé sur itertools.product:

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)
Eli Bendersky
la source
14
Cette solution récursive et d'autres ont un risque potentiel de consommer toute la mémoire RAM si la liste permutée est suffisamment grande
Boris Gorelik
3
Ils atteignent également la limite de récursivité (et meurent) avec de grandes listes
dbr
58
bgbg, dbr: Son utilisation d'un générateur, donc la fonction elle-même ne consommera pas de mémoire. Il vous appartient de savoir comment consommer l'itérateur renvoyé par all_perms (par exemple, vous pouvez écrire chaque itération sur le disque et ne pas vous soucier de la mémoire). Je sais que ce post est ancien mais j'écris ceci pour le bénéfice de tous ceux qui le lisent maintenant. De plus, maintenant, la meilleure façon serait d'utiliser itertools.permutations () comme l'ont souligné de nombreuses personnes.
Jagtesh Chadha
18
Pas seulement un générateur. Il utilise des générateurs imbriqués, qui cèdent chacun au précédent dans la pile d'appels, au cas où ce ne serait pas clair. Il utilise la mémoire O (n), ce qui est bien.
cdunn2001
1
PS: je l'ai corrigé, avec for i in range(len(elements))au lieu de for i in range(len(elements)+1). En fait, l'élément isolé elements[0:1]peut être dans len(elements)différentes positions, dans le résultat, non len(elements)+1.
Eric O Lebigot
339

Et dans Python 2.6 et suivants:

import itertools
itertools.permutations([1,2,3])

(renvoyé en tant que générateur. Utilisez list(permutations(l))pour retourner en tant que liste.)

Brian
la source
15
Fonctionne également en Python 3
wheleph
10
Notez qu'il existe un rparamètre, par exemple itertools.permutations([1,2,3], r=2), qui générera toutes les permutations possibles en sélectionnant 2 éléments:[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
toto_tico
278

Le code suivant avec Python 2.6 et supérieur UNIQUEMENT

Tout d'abord, importez itertools:

import itertools

Permutation (l'ordre compte):

print list(itertools.permutations([1,2,3,4], 2))
[(1, 2), (1, 3), (1, 4),
(2, 1), (2, 3), (2, 4),
(3, 1), (3, 2), (3, 4),
(4, 1), (4, 2), (4, 3)]

Combinaison (l'ordre n'a pas d'importance):

print list(itertools.combinations('123', 2))
[('1', '2'), ('1', '3'), ('2', '3')]

Produit cartésien (avec plusieurs itérables):

print list(itertools.product([1,2,3], [4,5,6]))
[(1, 4), (1, 5), (1, 6),
(2, 4), (2, 5), (2, 6),
(3, 4), (3, 5), (3, 6)]

Produit cartésien (avec un itérable et lui-même):

print list(itertools.product([1,2], repeat=3))
[(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2),
(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)]
e-satis
la source
`imprimer la liste (itertools.permutations ([1,2,3,4], 2)) ^` SyntaxError: syntaxe invalide` Je commence juste à utiliser VS Code Qu'est-ce que j'ai fait de mal? Le pointeur pointe sous le "t" de "liste"
gus
39
def permutations(head, tail=''):
    if len(head) == 0: print tail
    else:
        for i in range(len(head)):
            permutations(head[0:i] + head[i+1:], tail+head[i])

appelé comme:

permutations('abc')
kx2k
la source
Pourquoi imprimer la queue et ensuite retourner Aucun? Pourquoi ne pas retourner la queue à la place? Pourquoi ne rien retourner quand même?
bugmenot123
30
#!/usr/bin/env python

def perm(a, k=0):
   if k == len(a):
      print a
   else:
      for i in xrange(k, len(a)):
         a[k], a[i] = a[i] ,a[k]
         perm(a, k+1)
         a[k], a[i] = a[i], a[k]

perm([1,2,3])

Production:

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

Comme j'échange le contenu de la liste, un type de séquence modifiable est requis en entrée. Par exemple, perm(list("ball"))cela fonctionnera et perm("ball")ne fonctionnera pas parce que vous ne pouvez pas changer une chaîne.

Cette implémentation Python est inspirée de l'algorithme présenté dans le livre Computer Algorithms de Horowitz, Sahni et Rajasekeran .

Silveira Neto
la source
Je suppose que k est la longueur ou les permutations. Pour k = 2 sorties [1, 2, 3]. Cela ne devrait-il pas être (1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2) ??
Konstantinos Monachopoulos
k est l'indice de l'élément que vous souhaitez échanger
sf8193
22

Cette solution implémente un générateur, pour éviter de conserver toutes les permutations en mémoire:

def permutations (orig_list):
    if not isinstance(orig_list, list):
        orig_list = list(orig_list)

    yield orig_list

    if len(orig_list) == 1:
        return

    for n in sorted(orig_list):
        new_list = orig_list[:]
        pos = new_list.index(n)
        del(new_list[pos])
        new_list.insert(0, n)
        for resto in permutations(new_list[1:]):
            if new_list[:1] + resto <> orig_list:
                yield new_list[:1] + resto
Ricardo Reyes
la source
16

Dans un style fonctionnel

def addperm(x,l):
    return [ l[0:i] + [x] + l[i:]  for i in range(len(l)+1) ]

def perm(l):
    if len(l) == 0:
        return [[]]
    return [x for y in perm(l[1:]) for x in addperm(l[0],y) ]

print perm([ i for i in range(3)])

Le résultat:

[[0, 1, 2], [1, 0, 2], [1, 2, 0], [0, 2, 1], [2, 0, 1], [2, 1, 0]]
Paolo
la source
15

Le code suivant est une permutation sur place d'une liste donnée, implémentée en tant que générateur. Comme il ne renvoie que des références à la liste, la liste ne doit pas être modifiée en dehors du générateur. La solution est non récursive, utilise donc une mémoire faible. Fonctionne bien également avec plusieurs copies d'éléments dans la liste d'entrée.

def permute_in_place(a):
    a.sort()
    yield list(a)

    if len(a) <= 1:
        return

    first = 0
    last = len(a)
    while 1:
        i = last - 1

        while 1:
            i = i - 1
            if a[i] < a[i+1]:
                j = last - 1
                while not (a[i] < a[j]):
                    j = j - 1
                a[i], a[j] = a[j], a[i] # swap the values
                r = a[i+1:last]
                r.reverse()
                a[i+1:last] = r
                yield list(a)
                break
            if i == first:
                a.reverse()
                return

if __name__ == '__main__':
    for n in range(5):
        for a in permute_in_place(range(1, n+1)):
            print a
        print

    for a in permute_in_place([0, 0, 1, 1, 1]):
        print a
    print
Ber
la source
15

Un moyen assez évident à mon avis pourrait également être:

def permutList(l):
    if not l:
            return [[]]
    res = []
    for e in l:
            temp = l[:]
            temp.remove(e)
            res.extend([[e] + r for r in permutList(temp)])

    return res
tzwenn
la source
11
list2Perm = [1, 2.0, 'three']
listPerm = [[a, b, c]
            for a in list2Perm
            for b in list2Perm
            for c in list2Perm
            if ( a != b and b != c and a != c )
            ]
print listPerm

Production:

[
    [1, 2.0, 'three'], 
    [1, 'three', 2.0], 
    [2.0, 1, 'three'], 
    [2.0, 'three', 1], 
    ['three', 1, 2.0], 
    ['three', 2.0, 1]
]
zmk
la source
2
Bien qu'il produise techniquement la sortie souhaitée, vous résolvez quelque chose qui pourrait être O (n lg n) dans O (n ^ n) - "légèrement" inefficace pour les grands ensembles.
James
3
@James: Je suis un peu dérouté par le O (n log n) que vous donnez: le nombre de permutations est n !, qui est déjà beaucoup plus grand que O (n log n); donc, je ne vois pas comment une solution pourrait être O (n log n). Cependant, il est vrai que cette solution est dans O (n ^ n), qui est beaucoup plus grand que n !, comme cela ressort clairement de l'approximation de Stirling.
Eric O Lebigot
9

J'ai utilisé un algorithme basé sur le système de nombres factoriels - Pour une liste de longueur n, vous pouvez assembler chaque élément de permutation article par article, en sélectionnant parmi les articles laissés à chaque étape. Vous avez n choix pour le premier élément, n-1 pour le second et un seul pour le dernier, vous pouvez donc utiliser les chiffres d'un nombre dans le système de nombres factoriels comme indices. De cette façon, les nombres 0 à n! -1 correspondent à toutes les permutations possibles dans l'ordre lexicographique.

from math import factorial
def permutations(l):
    permutations=[]
    length=len(l)
    for x in xrange(factorial(length)):
        available=list(l)
        newPermutation=[]
        for radix in xrange(length, 0, -1):
            placeValue=factorial(radix-1)
            index=x/placeValue
            newPermutation.append(available.pop(index))
            x-=index*placeValue
        permutations.append(newPermutation)
    return permutations

permutations(range(3))

production:

[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

Cette méthode est non récursive, mais elle est légèrement plus lente sur mon ordinateur et xrange déclenche une erreur lorsque n! est trop grand pour être converti en un entier long C (n = 13 pour moi). C'était suffisant quand j'en avais besoin, mais ce n'est pas une itertools.permutations par un long shot.

timeeeee
la source
3
Salut, bienvenue dans Stack Overflow. Bien que publier la méthode de la force brute ait ses mérites, si vous ne pensez pas que votre solution est meilleure que la solution acceptée, vous ne devriez probablement pas la publier (en particulier sur une vieille question qui a déjà tant de réponses).
Hannele
1
Je cherchais en fait une approche sans bibliothèque de force brute, alors merci!
Jay Taylor
8

Notez que cet algorithme a une n factorialcomplexité temporelle, où nest la longueur de la liste d'entrée

Imprimez les résultats sur la course:

global result
result = [] 

def permutation(li):
if li == [] or li == None:
    return

if len(li) == 1:
    result.append(li[0])
    print result
    result.pop()
    return

for i in range(0,len(li)):
    result.append(li[i])
    permutation(li[:i] + li[i+1:])
    result.pop()    

Exemple:

permutation([1,2,3])

Production:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
Chen Xie
la source
8

On peut en effet parcourir le premier élément de chaque permutation, comme dans la réponse de tzwenn. Il est cependant plus efficace d'écrire cette solution de cette façon:

def all_perms(elements):
    if len(elements) <= 1:
        yield elements  # Only permutation possible = no permutation
    else:
        # Iteration over the first element in the result permutation:
        for (index, first_elmt) in enumerate(elements):
            other_elmts = elements[:index]+elements[index+1:]
            for permutation in all_perms(other_elmts): 
                yield [first_elmt] + permutation

Cette solution est environ 30% plus rapide, apparemment grâce à la récursivité se terminant à la len(elements) <= 1place de 0. Il est également beaucoup plus efficace en mémoire, car il utilise une fonction de générateur (à travers yield), comme dans la solution de Riccardo Reyes.

Eric O Lebigot
la source
6

Ceci est inspiré par l'implémentation Haskell utilisant la compréhension de liste:

def permutation(list):
    if len(list) == 0:
        return [[]]
    else:
        return [[x] + ys for x in list for ys in permutation(delete(list, x))]

def delete(list, item):
    lc = list[:]
    lc.remove(item)
    return lc
tirelire
la source
6

Implémentation régulière (pas de rendement - fera tout en mémoire):

def getPermutations(array):
    if len(array) == 1:
        return [array]
    permutations = []
    for i in range(len(array)): 
        # get all perm's of subarray w/o current item
        perms = getPermutations(array[:i] + array[i+1:])  
        for p in perms:
            permutations.append([array[i], *p])
    return permutations

Mise en œuvre du rendement:

def getPermutations(array):
    if len(array) == 1:
        yield array
    else:
        for i in range(len(array)):
            perms = getPermutations(array[:i] + array[i+1:])
            for p in perms:
                yield [array[i], *p]

L'idée de base est de parcourir tous les éléments du tableau pour la 1ère position, puis en 2e position de parcourir tous les autres éléments sans l'élément choisi pour le 1er, etc. Vous pouvez le faire avec la récursivité , où le le critère d'arrêt est d'arriver à un tableau de 1 élément - auquel cas vous retournez ce tableau.

entrez la description de l'image ici

David Refaeli
la source
Cela ne fonctionne pas pour moi _> ValueError: les opérandes n'ont pas pu être diffusés avec les formes (0,) (2,) , pour cette ligne:perms = getPermutations(array[:i] + array[i+1:])
RK1
@ RK1 quelle était l'entrée?
David Refaeli
Je passe dans un numpytableau _> getPermutations(np.array([1, 2, 3])), je vois que cela fonctionne pour une liste, je suis juste confus car l'argument func est array:)
RK1
@ RK1 content que cela fonctionne :-) list est un mot-clé en python, donc ce n'est généralement pas une bonne idée d'appeler votre paramètre un mot-clé, car il "l'ombre". J'utilise donc le tableau de mots, car c'est la fonctionnalité réelle de la liste que j'utilise - leur manière de tableau. Je suppose que si j'écrivais de la documentation, je la clarifierais. Je pense également que les questions de base "d'entrevue" devraient être résolues sans paquets externes, comme numpy.
David Refaeli
Haha c'est vrai, ouais j'essayais de l'utiliser avec numbaet je suis devenu gourmand avec la vitesse alors j'ai essayé de l'utiliser exclusivement avec des numpytableaux
RK1
4

Pour les performances, une solution numpy inspirée de Knuth , (p22):

from numpy import empty, uint8
from math import factorial

def perms(n):
    f = 1
    p = empty((2*n-1, factorial(n)), uint8)
    for i in range(n):
        p[i, :f] = i
        p[i+1:2*i+1, :f] = p[:i, :f]  # constitution de blocs
        for j in range(i):
            p[:i+1, f*(j+1):f*(j+2)] = p[j+1:j+i+2, :f]  # copie de blocs
        f = f*(i+1)
    return p[:n, :]

La copie de grands blocs de mémoire permet de gagner du temps - c'est 20 fois plus rapide que list(itertools.permutations(range(n)):

In [1]: %timeit -n10 list(permutations(range(10)))
10 loops, best of 3: 815 ms per loop

In [2]: %timeit -n100 perms(10) 
100 loops, best of 3: 40 ms per loop
BM
la source
3
from __future__ import print_function

def perm(n):
    p = []
    for i in range(0,n+1):
        p.append(i)
    while True:
        for i in range(1,n+1):
            print(p[i], end=' ')
        print("")
        i = n - 1
        found = 0
        while (not found and i>0):
            if p[i]<p[i+1]:
                found = 1
            else:
                i = i - 1
        k = n
        while p[i]>p[k]:
            k = k - 1
        aux = p[i]
        p[i] = p[k]
        p[k] = aux
        for j in range(1,(n-i)/2+1):
            aux = p[i+j]
            p[i+j] = p[n-j+1]
            p[n-j+1] = aux
        if not found:
            break

perm(5)
Adrian Statescu
la source
3

Voici un algorithme qui fonctionne sur une liste sans créer de nouvelles listes intermédiaires similaires à la solution de Ber sur https://stackoverflow.com/a/108651/184528 .

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

cdiggins
la source
3

La beauté de la récursivité:

>>> import copy
>>> def perm(prefix,rest):
...      for e in rest:
...              new_rest=copy.copy(rest)
...              new_prefix=copy.copy(prefix)
...              new_prefix.append(e)
...              new_rest.remove(e)
...              if len(new_rest) == 0:
...                      print new_prefix + new_rest
...                      continue
...              perm(new_prefix,new_rest)
... 
>>> perm([],['a','b','c','d'])
['a', 'b', 'c', 'd']
['a', 'b', 'd', 'c']
['a', 'c', 'b', 'd']
['a', 'c', 'd', 'b']
['a', 'd', 'b', 'c']
['a', 'd', 'c', 'b']
['b', 'a', 'c', 'd']
['b', 'a', 'd', 'c']
['b', 'c', 'a', 'd']
['b', 'c', 'd', 'a']
['b', 'd', 'a', 'c']
['b', 'd', 'c', 'a']
['c', 'a', 'b', 'd']
['c', 'a', 'd', 'b']
['c', 'b', 'a', 'd']
['c', 'b', 'd', 'a']
['c', 'd', 'a', 'b']
['c', 'd', 'b', 'a']
['d', 'a', 'b', 'c']
['d', 'a', 'c', 'b']
['d', 'b', 'a', 'c']
['d', 'b', 'c', 'a']
['d', 'c', 'a', 'b']
['d', 'c', 'b', 'a']
darxtrix
la source
3

Cet algorithme est le plus efficace, il évite le passage de tableaux et la manipulation lors d'appels récursifs, fonctionne en Python 2, 3:

def permute(items):
    length = len(items)
    def inner(ix=[]):
        do_yield = len(ix) == length - 1
        for i in range(0, length):
            if i in ix: #avoid duplicates
                continue
            if do_yield:
                yield tuple([items[y] for y in ix + [i]])
            else:
                for p in inner(ix + [i]):
                    yield p
    return inner()

Usage:

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

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
Cmyker
la source
3
def pzip(c, seq):
    result = []
    for item in seq:
        for i in range(len(item)+1):
            result.append(item[i:]+c+item[:i])
    return result


def perm(line):
    seq = [c for c in line]
    if len(seq) <=1 :
        return seq
    else:
        return pzip(seq[0], perm(seq[1:]))
manish kumar
la source
3

UNE AUTRE APPROCHE (sans libs)

def permutation(input):
    if len(input) == 1:
        return input if isinstance(input, list) else [input]

    result = []
    for i in range(len(input)):
        first = input[i]
        rest = input[:i] + input[i + 1:]
        rest_permutation = permutation(rest)
        for p in rest_permutation:
            result.append(first + p)
    return result

L'entrée peut être une chaîne ou une liste

print(permutation('abcd'))
print(permutation(['a', 'b', 'c', 'd']))
Tatsu
la source
Cela ne fonctionne pas pour une liste avec des entiers, par exemple. [1, 2, 3]retours[6, 6, 6, 6, 6, 6]
RK1
@ RK1, vous pouvez essayer celaprint(permutation(['1','2','3']))
Tatsu
Merci qui fonctionne
RK1
3

Avertissement: fiche informée par l'auteur du package. :)

Le package trotter est différent de la plupart des implémentations en ce qu'il génère des pseudo-listes qui ne contiennent pas réellement de permutations mais décrivent plutôt des mappages entre permutations et positions respectives dans un ordre, ce qui permet de travailler avec de très grandes «listes» de permutations, comme indiqué dans cette démo qui effectue des opérations et des recherches assez instantanées dans une pseudo-liste "contenant" toutes les permutations des lettres de l'alphabet, sans utiliser plus de mémoire ou de traitement qu'une page Web typique.

Dans tous les cas, pour générer une liste de permutations, nous pouvons procéder comme suit.

import trotter

my_permutations = trotter.Permutations(3, [1, 2, 3])

print(my_permutations)

for p in my_permutations:
    print(p)

Production:

Une pseudo-liste contenant 6 3 permutations de [1, 2, 3].
[1, 2, 3]
[1, 3, 2]
[3, 1, 2]
[3, 2, 1]
[2, 3, 1]
[2, 1, 3]
Richard Ambler
la source
2

Générer toutes les permutations possibles

J'utilise python3.4:

def calcperm(arr, size):
    result = set([()])
    for dummy_idx in range(size):
        temp = set()
        for dummy_lst in result:
            for dummy_outcome in arr:
                if dummy_outcome not in dummy_lst:
                    new_seq = list(dummy_lst)
                    new_seq.append(dummy_outcome)
                    temp.add(tuple(new_seq))
        result = temp
    return result

Cas de test:

lst = [1, 2, 3, 4]
#lst = ["yellow", "magenta", "white", "blue"]
seq = 2
final = calcperm(lst, seq)
print(len(final))
print(final)
Miled Louis Rizk
la source
2

Pour vous faire gagner des heures de recherche et d'expérimentation, voici la solution de permutations non récursives en Python qui fonctionne également avec Numba (à partir de la version 0.41):

@numba.njit()
def permutations(A, k):
    r = [[i for i in range(0)]]
    for i in range(k):
        r = [[a] + b for a in A for b in r if (a in b)==False]
    return r
permutations([1,2,3],3)
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Pour donner une impression de performance:

%timeit permutations(np.arange(5),5)

243 µs ± 11.1 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
time: 406 ms

%timeit list(itertools.permutations(np.arange(5),5))
15.9 µs ± 8.61 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
time: 12.9 s

N'utilisez donc cette version que si vous devez l'appeler à partir de la fonction njitted, sinon préférez l'implémentation itertools.

Anatoly Alekseev
la source
1

Je vois beaucoup d'itérations en cours à l'intérieur de ces fonctions récursives, pas exactement une récursivité pure ...

donc pour ceux d'entre vous qui ne peuvent pas respecter une seule boucle, voici une solution récursive grossière, totalement inutile

def all_insert(x, e, i=0):
    return [x[0:i]+[e]+x[i:]] + all_insert(x,e,i+1) if i<len(x)+1 else []

def for_each(X, e):
    return all_insert(X[0], e) + for_each(X[1:],e) if X else []

def permute(x):
    return [x] if len(x) < 2 else for_each( permute(x[1:]) , x[0])


perms = permute([1,2,3])
Karo Castro-Wunsch
la source
1

Une autre solution:

def permutation(flag, k =1 ):
    N = len(flag)
    for i in xrange(0, N):
        if flag[i] != 0:
            continue
        flag[i] = k 
        if k == N:
            print flag
        permutation(flag, k+1)
        flag[i] = 0

permutation([0, 0, 0])
anhldbk
la source
0

Ma solution Python:

def permutes(input,offset):
    if( len(input) == offset ):
        return [''.join(input)]

    result=[]        
    for i in range( offset, len(input) ):
         input[offset], input[i] = input[i], input[offset]
         result = result + permutes(input,offset+1)
         input[offset], input[i] = input[i], input[offset]
    return result

# input is a "string"
# return value is a list of strings
def permutations(input):
    return permutes( list(input), 0 )

# Main Program
print( permutations("wxyz") )
abelenky
la source
0
def permutation(word, first_char=None):
    if word == None or len(word) == 0: return []
    if len(word) == 1: return [word]

    result = []
    first_char = word[0]
    for sub_word in permutation(word[1:], first_char):
        result += insert(first_char, sub_word)
    return sorted(result)

def insert(ch, sub_word):
    arr = [ch + sub_word]
    for i in range(len(sub_word)):
        arr.append(sub_word[i:] + ch + sub_word[:i])
    return arr


assert permutation(None) == []
assert permutation('') == []
assert permutation('1')  == ['1']
assert permutation('12') == ['12', '21']

print permutation('abc')

Sortie: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Ilgorbek Kuchkarov
la source
0

En utilisant Counter

from collections import Counter

def permutations(nums):
    ans = [[]]
    cache = Counter(nums)

    for idx, x in enumerate(nums):
        result = []
        for items in ans:
            cache1 = Counter(items)
            for id, n in enumerate(nums):
                if cache[n] != cache1[n] and items + [n] not in result:
                    result.append(items + [n])

        ans = result
    return ans
permutations([1, 2, 2])
> [[1, 2, 2], [2, 1, 2], [2, 2, 1]]
Bonjour le monde
la source