목록의 모든 순서를 생성하려면 어떻게 해야 합니까?

목록의 모든 순서를 생성하려면 어떻게 해야 합니까?

목록의 모든 순서를 생성하려면 어떻게 해야 합니까?예를 들어 다음과 같습니다.

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]

표준 라이브러리에서 사용:

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

---

여기서 각색한 것은 어떻게 하면itertools.permutations수 .

def permutations(elements):
    if len(elements) <= 1:
        yield elements
        return
    for perm in permutations(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여기 하나 있습니다.

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

그리고 또 다른 하나는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)

Python 2.6 이후의 경우:

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

이치노list(permutations(xs))리스트로 되돌립니다.

Import, Importitertools:

import itertools

치환(순서 중요):

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

조합(순서는 중요하지 않습니다):

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

데카르트 제품(여러 개의 반복 가능 포함):

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

데카르트 제품(반복 가능한 제품 1개 및 자체):

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

def permutations(head, tail=''):
    if len(head) == 0:
        print(tail)
    else:
        for i in range(len(head)):
            permutations(head[:i] + head[i+1:], tail + head[i])

다음과 같이 호출:

permutations('abc')

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

출력:

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

gg의 、 e력으 e e 、 으 e e e e e e e e e e e e e e e e e e e e e. :perm(list("ball"))가 있습니다.perm("ball")'어느 쪽인가' 입니다.

이 Python 구현은 Horowitz, Sahni 및 Rajasekeran의 "컴퓨터 알고리즘"에 제시된 알고리즘에서 영감을 얻었습니다.

이 솔루션은 모든 순열을 메모리에 보관 유지하는 것을 방지하기 위해 제너레이터를 구현합니다.

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

기능적인 스타일로

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

그 결과:

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

다음 코드는 생성기로 구현된 특정 목록의 인플레이스 순열입니다.목록에 대한 참조만 반환하므로 생성기 외부에서 목록을 수정하면 안 됩니다.이 솔루션은 비재귀적이므로 메모리가 부족합니다.입력 목록에 있는 요소의 여러 복사본에서도 잘 작동합니다.

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

제 의견으로는 다음과 같은 분명한 방법이 있을 수 있습니다.

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

정기적인 구현(수율 없음 - 메모리의 모든 작업을 수행합니다):

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

수율 구현:

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]

첫 번째 위치에서는 배열 내의 모든 요소를 검토하고 두 번째 위치에서는 선택한 요소를 제외한 나머지 요소를 첫 번째 위치에서는 모두 검토하는 것이 기본입니다.이를 재귀적으로 수행할 수 있습니다. 여기서 중지 기준은 1개의 요소로 구성된 배열에 도달하는 것입니다. 이 경우 해당 배열이 반환됩니다.

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

출력:

[
    [1, 2.0, 'three'], 
    [1, 'three', 2.0], 
    [2.0, 1, 'three'], 
    [2.0, 'three', 1], 
    ['three', 1, 2.0], 
    ['three', 2.0, 1]
]

요인 번호 체계에 기반한 알고리즘을 사용했는데, 길이 n의 리스트는 각 단계에 남아 있는 항목 중에서 선택하여 항목별로 치환할 수 있습니다.첫 번째 항목에는 n개, 두 번째 항목에는 n-1개, 마지막 항목에는 1개만 선택할 수 있으므로 요인 번호 체계에서 숫자의 자릿수를 지수로 사용할 수 있습니다.이와 같이 0 ~ n!-1의 숫자는 사전순으로 가능한 모든 순열과 일치합니다.

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

출력:

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

이 방법은 비표준이지만 컴퓨터에서 약간 느리고, n!이 너무 커서 C 긴 정수로 변환할 수 없을 때 xrange가 오류를 일으킵니다(나의 경우 n=13).내가 필요할 땐 충분했지만, 그건 절대 반복이 아니야.

이 알고리즘에는, 다음과 같은 기능이 있습니다.n factorial시간의 복잡성, 장소n입력 목록의 길이입니다.

실행 시 결과 인쇄:

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

예를 들어:

permutation([1,2,3])

출력:

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

치환의 첫 번째 요소를 반복할 수 있는 것은 tzwenn의 대답입니다.단, 이 솔루션은 다음과 같이 기술하는 것이 효율적입니다.

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

이 솔루션은 약 30% 고속입니다.재귀가 다음 시간에 끝나기 때문입니다.len(elements) <= 1대신0또, 제너레이터 기능을 사용하고 있기 때문에, 메모리 효율이 훨씬 뛰어납니다.yieldRiccardo Reyes의 솔루션에서와 같습니다.

이는 목록 이해를 사용한 Haskell 구현에서 영감을 얻었습니다.

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

퍼포먼스에는 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, :]

대용량 메모리 블록을 복사하면 시간을 절약할 수 있습니다.그보다 20배 빠릅니다.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

다음과 같은 기본 제공 방법을 사용하지 않는 경우:

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

직접 퍼머트 기능을 구현할 수 있습니다.

from collections.abc import Iterable


def permute(iterable: Iterable[str]) -> set[str]:
    perms = set()

    if len(iterable) == 1:
        return {*iterable}

    for index, char in enumerate(iterable):
        perms.update([char + perm for perm in permute(iterable[:index] + iterable[index + 1:])])

    return perms


if __name__ == '__main__':
    print(permute('abc'))
    # {'bca', 'abc', 'cab', 'acb', 'cba', 'bac'}
    print(permute(['1', '2', '3']))
    # {'123', '312', '132', '321', '213', '231'}

면책사항: 패키지 작성자에 의한 파렴치한 플러그.:)

트로터 패키지는 실제로 순열을 포함하지 않고 순열과 각 위치 간의 매핑을 순서대로 기술하는 유사 목록을 생성하는 점에서 대부분의 구현과 다릅니다. 따라서 이 데모에서 보여지듯이 매우 큰 순열 목록으로 작업할 수 있습니다.조작과 검색은, 일반적인 Web 페이지보다 많은 메모리나 처리를 사용하지 않고, 알파벳의 문자의 모든 순열을 「포함」하는 의사 리스트로 행해집니다.

어떤 경우에도 순열 목록을 생성하기 위해 다음을 수행할 수 있습니다.

import trotter

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

print(my_permutations)

for p in my_permutations:
    print(p)

출력:

[1, 2, 3]의 6개의 3-변환을 포함하는 의사 리스트.
[1, 2, 3][1, 3, 2][3, 1, 2][3, 2, 1][2, 3, 1][2, 1, 3]

또 다른 접근법(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

입력은 문자열 또는 목록일 수 있습니다.

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

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)

다음은 Ber의 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

http://repl.it/J9v 에서 코드를 직접 사용해 볼 수 있습니다.

재귀의 장점:

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

이 알고리즘은 가장 효과적인 알고리즘으로 재귀 호출에서의 어레이 통과 및 조작을 회피하고 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()

사용방법:

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)

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

가능한 모든 순열 생성

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

테스트 케이스:

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

이 재귀함수 안에서 많은 반복이 일어나고 있는 것 같아요. 순수 재귀가 아니라...

단 하나의 루프도 견딜 수 없는 분들을 위해, 여기 완전 불필요하고 완전히 재귀적인 해결책이 있습니다.

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

검색 및 실험 시간을 절약하기 위해 Numba(0.41 현재)에서도 작동하는 Python의 비재귀 permutions 솔루션을 소개합니다.

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

성능에 대한 인상을 주기 위해:

%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

따라서 이 버전은 njitted 함수에서 호출해야 하는 경우에만 사용하고, 그렇지 않은 경우 itertools 구현을 선호합니다.

어쨌든 우리는 cympy 라이브러리를 사용할 수 있고, 또한 멀티셋 순열을 지원할 수 있습니다.

import sympy
from sympy.utilities.iterables import multiset_permutations
t = [1,2,3]
p = list(multiset_permutations(t))
print(p)

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

답변은 Numpy 어레이의 모든 순서를 취득하는 것으로 매우 고무되어 있습니다.

또 다른 솔루션:

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

이것이 초기 정렬 후 순열을 생성하는 점근적 최적 방법 O(n*n!)입니다.

최대 n개의 순열이 있으며, hasNextPermutation(..)은 O(n) 시간 복잡도로 실행됩니다.

3단계는 3단계는 3단계는 3단계입니다.

1. a[j]를 늘릴 수 있는 가장 큰 j를 찾습니다.
2. a[j]를 최소 실현 가능한 양만큼 늘리다
3. 새로운 a[0..]를 확장하기 위한 가장 간단한 방법을 사전 검색한다.j]

'''
Lexicographic permutation generation

consider example array state of [1,5,6,4,3,2] for sorted [1,2,3,4,5,6]
after 56432(treat as number) ->nothing larger than 6432(using 6,4,3,2) beginning with 5
so 6 is next larger and 2345(least using numbers other than 6)
so [1, 6,2,3,4,5]
'''
def hasNextPermutation(array, len):
    ' Base Condition '
    if(len ==1):
        return False
    '''
    Set j = last-2 and find first j such that a[j] < a[j+1]
    If no such j(j==-1) then we have visited all permutations
    after this step a[j+1]>=..>=a[len-1] and a[j]<a[j+1]

    a[j]=5 or j=1, 6>5>4>3>2
    '''
    j = len -2
    while (j >= 0 and array[j] >= array[j + 1]):
        j= j-1
    if(j==-1):
        return False
    # print(f"After step 2 for j {j}  {array}")
    '''
    decrease l (from n-1 to j) repeatedly until a[j]<a[l]
    Then swap a[j], a[l]
    a[l] is the smallest element > a[j] that can follow a[l]...a[j-1] in permutation
    before swap we have a[j+1]>=..>=a[l-1]>=a[l]>a[j]>=a[l+1]>=..>=a[len-1]
    after swap -> a[j+1]>=..>=a[l-1]>=a[j]>a[l]>=a[l+1]>=..>=a[len-1]

    a[l]=6 or l=2, j=1 just before swap [1, 5, 6, 4, 3, 2] 
    after swap [1, 6, 5, 4, 3, 2] a[l]=5, a[j]=6
    '''
    l = len -1
    while(array[j] >= array[l]):
        l = l-1
    # print(f"After step 3 for l={l}, j={j} before swap {array}")
    array[j], array[l] = array[l], array[j]
    # print(f"After step 3 for l={l} j={j} after swap {array}")
    '''
    Reverse a[j+1...len-1](both inclusive)

    after reversing [1, 6, 2, 3, 4, 5]
    '''
    array[j+1:len] = reversed(array[j+1:len])
    # print(f"After step 4 reversing {array}")
    return True

array = [1,2,4,4,5]
array.sort()
len = len(array)
count =1
print(array)
'''
The algorithm visits every permutation in lexicographic order
generating one by one
'''
while(hasNextPermutation(array, len)):
    print(array)
    count = count +1
# The number of permutations will be n! if no duplicates are present, else less than that
# [1,4,3,3,2] -> 5!/2!=60
print(f"Number of permutations: {count}")

언급URL : https://stackoverflow.com/questions/104420/how-do-i-generate-all-permutations-of-a-list