it-swarm-tr.com

Python'da bir listenin tüm permütasyonları nasıl oluşturulur?

Python'daki bir listenin tüm izinlerini, o listedeki öğelerin türünden bağımsız olarak nasıl oluşturursunuz?

Örneğin:

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

Python 2.6 ile başlayarak (ve Python 3 kullanıyorsanız) bunun için standard-library aracınız var: itertools.permutations .

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

Herhangi bir sebepten dolayı bir eski Python (<2.6) kullanıyorsanız veya nasıl çalıştığını bilmek istiyorsanız, burada 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:]

itertools.permutations belgesinde birkaç alternatif yaklaşım listelenmiştir. Işte bir tane:

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

Ve bir tane daha, itertools.product 'a dayalı:

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

Ve Python 2.6 sonrası:

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

(jeneratör olarak geri döndü. Liste olarak geri dönmek için list(permutations(l)) işlevini kullanın.)

322
Brian

Aşağıdaki kod Python 2.6 ve üstü SADECE

İlk olarak, itertools dosyasını içe aktarın:

import itertools

Permütasyon (sipariş önemlidir):

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

Kombinasyon (sipariş önemli değil):

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

Kartezyen ürün (birkaç tekrarlanabilir):

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

Kartezyen ürün (biri tekrarlanabilir ve kendisiyle):

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

olarak adlandırılan:

permutations('abc')
36
kx2k

Bu çözüm tüm izinleri hafızada tutmaktan kaçınmak için bir jeneratör uygular:

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

Çıktı:

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

Listenin içeriğini değiştirdiğim için girdi olarak değişken bir dizi türü gerekir. Örneğin. perm(list("ball")) çalışacak ve perm("ball") çalışmaz çünkü dizgiyi değiştiremezsiniz. 

Bu Python uygulaması, Bilgisayar Algoritmaları adlı kitabında Horowitz, Sahni ve Rajasekeran .

19
Silveira Neto

Aşağıdaki kod, belirli bir listenin, bir jeneratör olarak uygulanan yerinde kullanım iznidir. Yalnızca listeye referanslar döndürdüğü için, liste jeneratörün dışında değiştirilmemelidir. Giriş listesindeki öğelerin birden fazla kopyasıyla da iyi çalışın.

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

Ayrıca bence oldukça açık bir şekilde olabilir:

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

İşlevsel bir tarzda

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

Sonuç:

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

Çıktı:

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

Faktörel sayı sistemine dayanan bir algoritma kullandım - Uzunluk n listesi için her bir permütasyon maddesini, her aşamada kalan maddeleri seçerek maddeye göre birleştirebilirsiniz. Birinci öğe için n seçeneğine, ikinci için n-1 seçeneğine ve sonuncusu için yalnızca bir seçeneğe sahipsiniz, böylece faktör sayı sistemindeki bir sayının dizinlerini dizin olarak kullanabilirsiniz. Bu şekilde 0 - n! -1 arasındaki rakamlar, sözlük sırasındaki tüm olası permütasyonlara karşılık gelir.

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

çıktı:

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

Bu yöntem özyinelemeli değildir, ancak bilgisayarımda biraz daha yavaş ve xrange n olduğunda bir hataya neden oluyor! C uzunluğunda bir tamsayıya dönüştürülemeyecek kadar büyük (benim için n = 13). İhtiyaç duyduğumda yeterliydi, ama uzun zamandır itertools.permutation yok.

8
timeeeee

Bu algoritmanın n factorial zaman karmaşıklığına sahip olduğunu unutmayın; burada n, giriş listesinin uzunluğudur.

Sonuçları kaçak olarak yazdır:

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

Örnek: 

permutation([1,2,3])

Çıktı:

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

Gerçekten de, tzwenn'in cevabında olduğu gibi, her permütasyonun ilk elemanı üzerinde yineleme yapabilir; Bu çözümü şu şekilde yazmayı tercih ederim:

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

Bu çözüm yaklaşık% 30 daha hızlıdır, görünüşe göre 0..__ yerine len(elements) <= 1 ile biten özyinelemeler sayesinde, Riccardo Reyes'in çözümünde olduğu gibi bir jeneratör işlevini (yield aracılığıyla) kullandığından, daha verimlidir.

6
Eric O Lebigot

Bu liste kavrayışı kullanılarak Haskell uygulamasından ilham almıştır: 

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

Performans için, Knuth , (p22) 'den esinlenerek hazırlanan bir çözüm:

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

Büyük bellek bloklarını kopyalamak zaman kazandırır - list(itertools.permutations(range(n))'den 20 kat daha hızlıdır:

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.

Python okuryazarlığımı bağışlayın çünkü python'da çözüm önermeyeceğim .. Python 2.6'nın permütasyonları üretmek için hangi yöntemi kullandığını ve eliben'ın Johnson-Trotter permütasyon nesli gibi göründüğünü bilmediğim için makaleyi arayabilirsinin Wikipedia'da Permütasyonlar ve bunların üretimi , Myrvold ve Ruskey tarafından yazılmıştır 'daki unrank işlevine benziyor.

Bana göre bu, bellek gereksinimini önemli ölçüde azaltmak için, diğer cevaplarda olduğu gibi bir jeneratörde kullanılabileceği gibi görünüyor. Unutma ki permütasyonlar sözlükbilimsel olmayacak.

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

İşte Ber'in çözümüne benzeyen https://stackoverflow.com/a/108651/184528 adreslerinde yeni ara listeler oluşturmadan bir listede çalışan bir algoritma. 

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

Kodu burada kendiniz deneyebilirsiniz: http://repl.it/J9v

3
cdiggins

Özyinelemenin güzelliği:

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

Bu algoritma en etkili olanı, tekrarlamalı aramalarda dizi geçişinden ve manipülasyondan kaçınır, Python 2, 3'te çalışır:

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

Kullanımı:

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

Mümkün olan tüm izinleri üret

Python3.4 kullanıyorum:

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

Test Durumları:

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

BİR YAKLAŞIM (lib'ler olmadan)

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

Giriş bir dize veya liste olabilir

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

Tam olarak saf özyinelemeyi değil, bu özyinelemeli işlevlerin içinde bir çok iterasyon olduğunu görüyorum ...

yani, tek bir döngü bile yerine getiremeyenleriniz için, işte size brüt, tamamen gereksiz, tamamen özyineli bir çözüm.

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

Başka bir çözüm:

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

Sizi milletlerce muhtemel arama ve deneme saatlerinden kurtarmak için, işte Python'da Numba ile çalışan özyinelemesiz permutaions çözümü:

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

Performans hakkında bir izlenim bırakmak için:

%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

Bu yüzden bu sürümü sadece njitted fonksiyonundan çağırmanız gerekiyorsa kullanın, aksi takdirde itertools uygulamasını tercih edin.

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

Çıktı: ['abc', 'acb', 'bac', 'bca', 'kabin', 'cba']

0

Counter öğesini kullanma

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

Python Çözümüm:

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