首页 文章

如何在Python中生成列表的所有排列

提问于
浏览
464

如何在Python中生成列表的所有排列,与该列表中的元素类型无关?

例如:

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]

28 回答

  • 3

    人们确实可以迭代每个排列的第一个元素,如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 . 它还具有更高的内存效率,因为它使用生成器功能(通过 yield ),就像Riccardo Reyes的解决方案一样 .

  • 1

    这是一个在列表上工作的算法,无需创建类似于Ber的@555263_解决方案的新中间列表 .

    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

  • 7

    对于性能而言,这是一个受Knuth启发的numpy解决方案,(第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, :]
    

    复制大块内存节省时间 - 比 list(itertools.permutations(range(n)) 快20倍:

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

    另一种方案:

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

    请注意,此算法具有 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]
    
  • 4

    递归之美:

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

    这个算法是最有效的算法,它避免了递归调用中的数组传递和操作,适用于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)
    
  • 251

    以下代码仅适用于Python 2.6及更高版本

    首先,导入 itertools

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

    笛卡尔积(有一个可迭代的本身):

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

    我看到在这些递归函数中进行了很多迭代,而不是完全纯粹的递归...

    所以对于那些不能遵守一个循环的人来说,这是一个粗略的,完全不必要的完全递归的解决方案

    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

    Starting with Python 2.6 (如果您使用的是Python 3),您可以使用 standard-library 工具:itertools.permutations .

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

    如果您出于某种原因使用 older Python (<2.6) 或只是想知道它是如何工作的,这里有一个很好的方法,取自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 的文档中列出了几种替代方法 . 这是一个:

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

    生成所有可能的排列

    我正在使用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)
    
  • 3
    #!/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]
    

    因为我'm swapping the content of the list it'需要一个可变序列类型作为输入 . 例如 . perm(list("ball")) 将起作用 perm("ball") 赢得't because you can' t更改字符串 .

    这个Python实现的灵感来自Horowitz,Sahni和Rajasekeran的计算机算法一书中提出的算法 .

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

    称为:

    permutations('abc')
    
  • 0

    我的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( per