it-swarm-eu.dev

Jak generovat všechny permutace seznamu v Pythonu

Jak generujete všechny permutace seznamu v Pythonu, nezávisle na typu prvků v tomto seznamu?

Například:

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]
481
Ricardo Reyes

Počínaje Pythonem 2.6 (a pokud jste na Pythonu 3) máte k dispozici nástroj standard-library: itertools.permutations .

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

Pokud používáte starší Python (<2.6) z nějakého důvodu nebo jste jen zvědaví, jak to funguje, zde je jeden pěkný přístup, převzatý z 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:]

V dokumentaci itertools.permutations je uvedeno několik alternativních přístupů. Zde je jeden:

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

A další, založené na 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)
371
Eli Bendersky

A v Python 2.6 dále:

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

(vráceno jako generátor. Použijte list(permutations(l)) pro návrat jako seznam.)

322
Brian

Následující kód s Pythonem 2.6 a vyšším

Nejprve importujte itertools:

import itertools

Permutace (záležitosti objednávky):

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

Kombinace (pořadí nezáleží):

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

Kartézský produkt (s několika iterables):

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

Kartézský produkt (s jedním iterovatelným a sám):

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)]
254
e-satis
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])

volal jako:

permutations('abc')
36
kx2k

Toto řešení implementuje generátor, aby se zabránilo držení všech permutací v paměti:

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
21
Ricardo Reyes
#!/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])

Výstup:

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

Jelikož přecházím na obsah seznamu, je nutné zadat jako vstup proměnlivý typ sekvence. Např. perm(list("ball")) bude fungovat a perm("ball") nebude, protože nemůžete změnit řetězec. 

Tato implementace Pythonu je inspirována algoritmem prezentovaným v knize Počítačové algoritmy Horowitze, Sahniho a Rajasekerana .

19
Silveira Neto

Následující kód je permutace daného seznamu na místě, implementovaná jako generátor. Protože vrací pouze odkazy na seznam, seznam by neměl být upravován mimo generátor. Řešení není rekurzivní, takže používá nízkou paměť. Dobře pracovat také s více kopiemi prvků v seznamu vstupů.

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 __== '__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
14
Ber

Podle mého názoru může být zcela zřejmý také:

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
13
tzwenn

Ve funkčním stylu

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

Výsledek:

[[0, 1, 2], [1, 0, 2], [1, 2, 0], [0, 2, 1], [2, 0, 1], [2, 1, 0]]
11
Paolo
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

Výstup:

[
    [1, 2.0, 'three'], 
    [1, 'three', 2.0], 
    [2.0, 1, 'three'], 
    [2.0, 'three', 1], 
    ['three', 1, 2.0], 
    ['three', 2.0, 1]
]
10
zmk

Použil jsem algoritmus založený na faktoriálním číslovém systému - Pro seznam délek n můžete sestavit každou položku permutace podle položek a vybrat z položek v každé fázi. Máte n možností pro první položku, n-1 pro druhou, a pouze jednu pro poslední, takže můžete použít číslice čísla v systému faktoriálních čísel jako indexy. Čísla 0 až n! -1 odpovídají všem možným permutacím v lexikografickém pořadí.

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

výstup:

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

Tato metoda není rekurzivní, ale je o něco pomalejší na mém počítači a xrange zvyšuje chybu, když n! je příliš velký na to, aby mohl být převeden na celé číslo C (n = 13 pro mě). Stačilo to, když jsem to potřeboval, ale není to itertools.permutations dlouhým výstřelem.

8
timeeeee

Tento algoritmus má časovou složitost n factorial, kde n je délka vstupního seznamu

Vytiskněte výsledky v průběhu:

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

Příklad: 

permutation([1,2,3])

Výstup:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
7
Chen Xie

Člověk může skutečně iterovat nad prvním prvkem každé permutace, jako v tzwennově odpovědi; Toto řešení dávám přednost:

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

Toto řešení je o 30% rychlejší, zřejmě díky rekurzi končící na len(elements) <= 1 namísto 0. Je také mnohem efektivnější z hlediska paměti, protože používá funkci generátoru (prostřednictvím yield), jako v řešení Riccarda Reyesho .

6
Eric O Lebigot

To je inspirováno implementací Haskellu s použitím seznamu porozumění: 

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
5
piggybox

Pro výkon, numpy řešení inspirované 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, :]

Kopírování velkých bloků paměti šetří čas - Je 20x rychlejší než 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
4
B. M.

Odpusťte mé negramotnosti v pythonu, protože nebudu nabízet řešení v pythonu. článek ve Wikipedii na Permutace a jejich generace to vypadá jako unrank funkce v papír Myrvold a Ruskey .

Zdá se mi, že by to mohlo být použito v generátoru stejně jako v jiných odpovědích, aby se značně snížil požadavek na paměť. Jen nezapomeňte, že permutace nebudou v lexikografickém pořadí.

3
Eonwe
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)
3
Adrian Statescu
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:]))
3
manish kumar

Zde je algoritmus, který pracuje na seznamu, aniž by vytvořil nové přechodné seznamy podobné Berovu řešení na adrese 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

Kód si můžete vyzkoušet zde: http://repl.it/J9v

3
cdiggins

Krása rekurze:

>>> 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']
3
darxtrix

Tento algoritmus je nejúčinnější, vyhýbá se předávání matic a manipulaci s rekurzivními voláními, pracuje v Pythonu 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()

Používání:

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

Generovat všechny možné permutace

Používám 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

Zkušební případy:

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

JINÝ PŘÍSTUP (bez 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

Vstup může být řetězec nebo seznam

print(permutation('abcd'))
print(permutation(['a', 'b', 'c', 'd']))
1
Tatsu

Vidím hodně iterace probíhající uvnitř těchto rekurzivních funkcí, ne přesně čistý rekurze ...

tak pro ty z vás, kteří nemohou dodržovat ani jednu smyčku, zde je hrubé, naprosto zbytečné plně rekurzivní řešení

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

Další řešení:

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

Chcete-li ušetřit lidi možné hodiny vyhledávání a experimentování, zde je non-rekurzivní řešení permutaions v Pythonu, který také pracuje s Numba (jak v. 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]]

Chcete-li vytvořit dojem o výkonu:

%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

Takže tuto verzi používejte pouze v případě, že ji musíte zavolat z njitted funkce, jinak preferujete implementaci itertools.

1
Anatoly Alekseev
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')

Výstup: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

0

Použití 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]]

0
Hello.World

Moje řešení 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") )
0
abelenky