Wie generiere ich alle Permutationen einer Liste?

592

Wie generieren Sie alle Permutationen einer Liste in Python, unabhängig von der Art der Elemente in dieser Liste?

Zum Beispiel:

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
quelle
5
Ich stimme der rekursiven, akzeptierten Antwort zu - HEUTE. Dies ist jedoch immer noch ein großes Problem der Informatik. Die akzeptierte Antwort löst dieses Problem mit exponentieller Komplexität (2 ^ NN = len (Liste)). Löse es (oder beweise, dass du es nicht kannst) in Polynomzeit :) Siehe "Problem mit reisenden Verkäufern"
FlipMcF
37
@FlipMcF Es wird schwierig sein, es in Polynomzeit zu "lösen", da es nur eine faktorielle Zeit benötigt, um die Ausgabe aufzulisten ... also, nein, es ist nicht möglich.
Thomas

Antworten:

488

Ab Python 2.6 (und wenn Sie Python 3 verwenden) haben Sie ein Standardbibliothekstool dafür : itertools.permutations.

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

Wenn Sie aus irgendeinem Grund ein älteres Python (<2.6) verwenden oder nur neugierig sind, wie es funktioniert, finden Sie hier einen guten Ansatz, der von http://code.activestate.com/recipes/252178/ übernommen wurde :

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:]

Einige alternative Ansätze sind in der Dokumentation von aufgeführt itertools.permutations. Hier ist eine:

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

Und eine andere, basierend auf 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
quelle
14
Diese und andere rekursive Lösungen können möglicherweise den gesamten Arbeitsspeicher aufbrauchen, wenn die permutierte Liste groß genug ist
Boris Gorelik
3
Sie erreichen auch die Rekursionsgrenze (und sterben) mit großen Listen
dbr
58
bgbg, dbr: Es wird ein Generator verwendet, sodass die Funktion selbst keinen Speicher verbraucht. Es bleibt Ihnen überlassen, wie Sie den von all_perms zurückgegebenen Iterator verwenden (sagen Sie, Sie könnten jede Iteration auf die Festplatte schreiben und sich keine Gedanken über den Speicher machen). Ich weiß, dass dieser Beitrag alt ist, aber ich schreibe ihn zum Nutzen aller, die ihn jetzt lesen. Auch jetzt wäre der beste Weg, itertools.permutations () zu verwenden, wie von vielen hervorgehoben.
Jagtesh Chadha
18
Nicht nur ein Generator. Es werden verschachtelte Generatoren verwendet, die jeweils den vorherigen im Aufrufstapel ergeben, falls dies nicht klar ist. Es verwendet O (n) Speicher, was gut ist.
cdunn2001
1
PS: Ich habe es behoben, mit for i in range(len(elements))statt for i in range(len(elements)+1). Tatsächlich kann sich das herausgegriffene Element elements[0:1]in len(elements)unterschiedlichen Positionen befinden, im Ergebnis jedoch nicht len(elements)+1.
Eric O Lebigot
339

Und ab Python 2.6 :

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

(Wird als Generator zurückgegeben. Verwenden Sie list(permutations(l))diese Option , um als Liste zurückzukehren.)

Brian
quelle
15
Funktioniert auch in Python 3
wheleph
10
Beachten Sie, dass es einen rParameter gibt, der z. B. itertools.permutations([1,2,3], r=2)alle möglichen Permutationen generiert und 2 Elemente auswählt:[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
toto_tico
277

Der folgende Code NUR mit Python 2.6 und höher

Importieren Sie zunächst itertools:

import itertools

Permutation (Ordnungsangelegenheiten):

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)]

Kombination (Reihenfolge spielt keine Rolle):

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

Kartesisches Produkt (mit mehreren Iterablen):

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)]

Kartesisches Produkt (mit einem iterierbaren und sich selbst):

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
quelle
`print list (itertools.permutations ([1,2,3,4], 2)) ^` SyntaxError: ungültige Syntax` Ich fange gerade mit VS Code an Was habe ich falsch gemacht? Der Zeiger zeigt unter das "t" von "list"
gus vor
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])

genannt als:

permutations('abc')
kx2k
quelle
Warum Schwanz drucken und dann Keine zurückgeben? Warum nicht stattdessen den Schwanz zurückgeben? Warum nicht sowieso etwas zurückgeben?
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])

Ausgabe:

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

Da ich den Inhalt der Liste austausche, ist ein veränderbarer Sequenztyp als Eingabe erforderlich. ZB perm(list("ball"))wird funktionieren und perm("ball")nicht, weil Sie eine Zeichenfolge nicht ändern können.

Diese Python-Implementierung ist von dem Algorithmus inspiriert, der im Buch Computer Algorithms von Horowitz, Sahni und Rajasekeran vorgestellt wird .

Silveira Neto
quelle
Ich nehme an, k ist die Länge oder die Permutationen. Für k = 2 Ausgänge [1, 2, 3]. Sollte es nicht (1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2) sein?
Konstantinos Monachopoulos
k ist der Index des Elements, das Sie tauschen möchten
sf8193
22

Diese Lösung implementiert einen Generator, um zu vermeiden, dass alle Permutationen im Speicher bleiben:

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
quelle
16

In einem funktionalen Stil

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)])

Das Ergebnis:

[[0, 1, 2], [1, 0, 2], [1, 2, 0], [0, 2, 1], [2, 0, 1], [2, 1, 0]]
Paolo
quelle
15

Der folgende Code ist eine direkte Permutation einer bestimmten Liste, die als Generator implementiert ist. Da nur Verweise auf die Liste zurückgegeben werden, sollte die Liste nicht außerhalb des Generators geändert werden. Die Lösung ist nicht rekursiv und verwendet daher wenig Speicher. Funktioniert auch gut mit mehreren Kopien von Elementen in der Eingabeliste.

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
quelle
15

Ein ganz offensichtlicher Weg könnte meiner Meinung nach auch sein:

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
quelle
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

Ausgabe:

[
    [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
quelle
2
Während es technisch die gewünschte Ausgabe erzeugt, lösen Sie etwas, das O (n lg n) in O (n ^ n) sein könnte - "leicht" ineffizient für große Mengen.
James
3
@James: Ich bin ein wenig verwirrt von dem O (n log n), das du gibst: Die Anzahl der Permutationen ist n!, Was bereits viel größer ist als O (n log n); Ich kann also nicht sehen, wie eine Lösung O (n log n) sein könnte. Es ist jedoch wahr, dass diese Lösung in O (n ^ n) vorliegt, das viel größer als n! Ist, wie aus Stirlings Näherung hervorgeht.
Eric O Lebigot
9

Ich habe einen Algorithmus verwendet, der auf dem Fakultätszahlensystem basiert. Für eine Liste der Länge n können Sie jede Permutation Element für Element zusammenstellen und aus den Elementen auswählen, die in jeder Phase übrig bleiben. Sie haben n Auswahlmöglichkeiten für das erste Element, n-1 für das zweite und nur eine für das letzte, sodass Sie die Ziffern einer Zahl im Fakultätsnummernsystem als Indizes verwenden können. Auf diese Weise entsprechen die Zahlen 0 bis n! -1 allen möglichen Permutationen in lexikographischer Reihenfolge.

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))

Ausgabe:

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

Diese Methode ist nicht rekursiv, auf meinem Computer jedoch etwas langsamer, und xrange löst einen Fehler aus, wenn n! ist zu groß, um in eine C-lange Ganzzahl konvertiert zu werden (n = 13 für mich). Es war genug, als ich es brauchte, aber es ist bei weitem kein itertools.permutations.

timeeeee
quelle
3
Hallo, willkommen bei Stack Overflow. Obwohl das Posten der Brute-Force-Methode ihre Vorzüge hat, sollten Sie sie wahrscheinlich nicht posten, wenn Sie nicht der Meinung sind, dass Ihre Lösung besser ist als die akzeptierte Lösung (insbesondere bei einer alten Frage, die bereits so viele Antworten hat).
Hannele
1
Ich war tatsächlich auf der Suche nach einem Brute-Force-Ansatz ohne Bibliothek, also danke!
Jay Taylor
8

Beachten Sie, dass dieser Algorithmus eine n factorialzeitliche Komplexität aufweist, wobei ndie Länge der Eingabeliste ist

Drucken Sie die Ergebnisse während des Laufs aus:

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()    

Beispiel:

permutation([1,2,3])

Ausgabe:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
Chen Xie
quelle
8

Man kann tatsächlich über das erste Element jeder Permutation iterieren, wie in tzwenns Antwort. Es ist jedoch effizienter, diese Lösung folgendermaßen zu schreiben:

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

Diese Lösung ist etwa 30% schneller, anscheinend dank der Rekursion, die auf len(elements) <= 1statt endet 0. Es ist auch viel speichereffizienter, da es eine Generatorfunktion (durch yield) verwendet, wie in Riccardo Reyes 'Lösung.

Eric O Lebigot
quelle
6

Dies ist inspiriert von der Haskell-Implementierung mit Listenverständnis:

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
Piggybox
quelle
6

Regelmäßige Implementierung (kein Ertrag - erledigt alles im Speicher):

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

Ertragsimplementierung:

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]

Die Grundidee besteht darin, alle Elemente im Array für die 1. Position und dann in der 2. Position alle übrigen Elemente ohne das ausgewählte Element für die 1. Position usw. zu durchlaufen. Sie können dies mit Rekursion tun , wobei die Das Stoppkriterium führt zu einem Array mit 1 Element. In diesem Fall geben Sie dieses Array zurück.

Geben Sie hier die Bildbeschreibung ein

David Refaeli
quelle
Dies funktioniert bei mir nicht _> ValueError: Operanden konnten nicht zusammen mit Formen (0,) (2,) für diese Zeile perms = getPermutations(array[:i] + array[i+1:])
gesendet werden
@ RK1 was war die Eingabe?
David Refaeli
Ich übergebe ein numpyArray _> getPermutations(np.array([1, 2, 3])), ich sehe, dass es für eine Liste funktioniert, wurde gerade verwirrt, da das func arg ist array:)
RK1
@ RK1 froh, dass es funktioniert :-) list ist ein Schlüsselwort in Python, daher ist es normalerweise keine gute Idee, Ihren Parameter als Schlüsselwort zu bezeichnen, da es ihn "beschattet". Ich verwende also das Wort Array, da dies die eigentliche Funktionalität der Liste ist, die ich verwende - ihre Array-ähnliche Art und Weise. Ich denke, wenn ich Dokumentation schreiben würde, würde ich es klarstellen. Ich glaube auch, dass grundlegende "Interview" -Fragen ohne externe Pakete wie Numpy gelöst werden sollten.
David Refaeli
Haha, das stimmt, ja, ich habe versucht, es mit zu benutzen numbaund wurde gierig nach Geschwindigkeit, also habe numpy
ich
4

Für die Aufführung eine von Knuth inspirierte Numpy-Lösung (S. 22):

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, :]

Das Kopieren großer Speicherblöcke spart Zeit - es ist 20x schneller als 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
quelle
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
quelle
3

Hier ist ein Algorithmus, der mit einer Liste arbeitet, ohne neue Zwischenlisten zu erstellen, die der Lösung von Ber unter https://stackoverflow.com/a/108651/184528 ähneln .

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

Sie können den Code hier selbst ausprobieren: http://repl.it/J9v

cdiggins
quelle
3

Die Schönheit der Rekursion:

>>> 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
quelle
3

Dieser Algorithmus ist der effektivste, er vermeidet das Übergeben und Manipulieren von Arrays bei rekursiven Aufrufen und funktioniert in 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()

Verwendungszweck:

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
quelle
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
quelle
3

EIN ANDERER ANSATZ (ohne Bibliotheken)

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

Die Eingabe kann eine Zeichenfolge oder eine Liste sein

print(permutation('abcd'))
print(permutation(['a', 'b', 'c', 'd']))
Tatsu
quelle
Dies funktioniert nicht für eine Liste mit ganzen Zahlen, z. [1, 2, 3]Rückkehr[6, 6, 6, 6, 6, 6]
RK1
@ RK1, du kannst es versuchenprint(permutation(['1','2','3']))
Tatsu
Danke, das funktioniert
RK1
3

Haftungsausschluss: formloser Plug vom Paketautor. :) :)

Das Traber- Paket unterscheidet sich von den meisten Implementierungen darin, dass es Pseudolisten generiert, die keine Permutationen enthalten, sondern Zuordnungen zwischen Permutationen und jeweiligen Positionen in einer Reihenfolge beschreiben, sodass wie gezeigt mit sehr großen Permutationslisten gearbeitet werden kann in dieser Demo, die ziemlich sofortige Operationen und Suchvorgänge in einer Pseudoliste ausführt, die alle Permutationen der Buchstaben im Alphabet enthält, ohne mehr Speicher oder Verarbeitung als eine typische Webseite zu benötigen.

In jedem Fall können wir Folgendes tun, um eine Liste von Permutationen zu erstellen.

import trotter

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

print(my_permutations)

for p in my_permutations:
    print(p)

Ausgabe:

Eine Pseudoliste mit 6 3-Permutationen von [1, 2, 3].
[1, 2, 3]
[1, 3, 2]
[3, 1, 2]
[3, 2, 1]
[2, 3, 1]
[2, 1, 3]
Richard Ambler
quelle
2

Generieren Sie alle möglichen Permutationen

Ich benutze 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

Testfälle:

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

Um Ihnen möglicherweise stundenlanges Suchen und Experimentieren zu ersparen, finden Sie hier die nicht rekursive Permutationslösung in Python, die auch mit Numba funktioniert (ab 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]]

Um einen Eindruck von der Leistung zu vermitteln:

%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

Verwenden Sie diese Version daher nur, wenn Sie sie über die Funktion njitted aufrufen müssen. Andernfalls bevorzugen Sie die Implementierung von itertools.

Anatoly Alekseev
quelle
1

Ich sehe eine Menge Iteration in diesen rekursiven Funktionen, nicht gerade reine Rekursion ...

Für diejenigen unter Ihnen, die sich nicht einmal an eine einzige Schleife halten können, ist hier eine grobe, völlig unnötige, vollständig rekursive Lösung

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
quelle
1

Eine andere Lösung:

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
quelle
0

Meine Python-Lösung:

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
quelle
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')

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

Ilgorbek Kuchkarov
quelle
0

Verwenden von 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]]
Hallo Welt
quelle