生成所有长度的所有排列

Question

如何生成列表 b(1,6,8,3,9,5) 的所有可能排列（包括不同长度的排列）？示例：

List a = [1,2,3]
generateperms(a)
1,2,3
3,1,2
3,2,1
1,3,2
2,1,3
2,3,1
2,3
1,2
1,3
2,1
3,2
3,1

依此类推并获得每个长度的所有排列？

编辑： 我将使用这个用 python 编写的，效果很好：

import itertools  
a = ['a','b','c']  
for i in range(len(a)):  
    print list(itertools.permutations(a,i+1))  

Answer 1

我认为这将是每个子集的所有排列。

返回子集的最简单方法是考虑从 0（空集）到输入列表（完整集）长度的所有二进制整数。因此，您可以从 0 到 2**(length(input)) 进行计数，并使用结果来屏蔽要从该特定子集中排除的所有元素。

从那里您应该能够使用网上许多代码示例中的任何一个来返回排列。

Answer 2

我建议从更简单的事情开始。假设 l 是一个包含 n 元素的列表。首先，你能编写一个函数来生成具有固定长度k的l的所有排列吗？然后，您能否找到一种方法，使用不同的 k 值重复调用该函数，以生成长度为 0 的排列、长度为 1 的所有排列、长度为 2 的所有排列，依此类推，直到您得到n？

Answer 3

考虑生成字符串的所有排列的递归实现。如果您在构建子排列时存储它们，那么您将拥有您想要的所有排列。

在 erlang 中，作为起点（这是 3.3 Permutations 的修改版本）

perms([]) -> [[]];
perms(L) ->
  [ [H|T] || H <- L, T <- perms(L -- [H])]
  ++ [ [T] || H <- L, T <- perms(L -- [H]) ].

但请注意，这会给您留下重复项和大量空数组的数组，您必须删除这些数组才能使输出更漂亮。

Answer 4

之前我提到过，我在 Python 中编写了一个可怕的 lambda 表达式，使用他们在 2.6 中添加的 bin() 整数到二进制字符串内置函数来生成序列的所有子集。

这是它的更丑陋的版本：

subsets = lambda s: (
    (s[x] for x,c in 
       enumerate("0" * (len(s)-len(bin(i)[2:])) + bin(i)[2:])
       if int(c)) 
     for i in range(0,2**len(s)
     )
)

但我注意到我可以通过简单调用字符串的 zfill() 来替换该表达式的 "0" * ... +" 部分code> 方法（感谢 SO 用户：gimel）。 ：

subsets = lambda s: (
        [s[x] for x,c in 
              enumerate(bin(i)[2:].zfill(len(s)))
              if int(c)
              ]
        for i in range(0,2**len(s))
    )

尽管看起来很简单，但它是我所描述的一个相对简单的实现：给定表示从零到集合大小的任何整数的二进制字符串，屏蔽掉与二进制字符串中的零相对应的任何元素。外部（生成器）表达式仅涵盖了必要的范围，

如果我知道的话，我可能会想到使用带有两个参数的 itertools.permutations() 方法。查看该函数的 __doc__ 字符串 但是，我确实需要花一些时间来说服自己这两种方法都会给出相同的结果。

Answer 5

一般来说，长度为 n 的列表有 n!安排或排列。因此，对于多个长度，我们将有 n!(nk)!其中 k 为 0 < k＜名词

Answer 6

对于列列表 feature_cols，我们可以使用这个衬垫：

[combo for i in range(1, len(feature_cols) + 1) for combo in itertools.combinations(feature_cols, i) ]

这基本上是在做：

all_combinations = []
for i in range(1, len(feature_cols) + 1):
    for combo in itertools.combinations(feature_cols, i):
        all_combinations.append(combo)

例如

>>> feature_columns = ['TV', 'Radio', 'Newspaper']
>>> all_combinations = [combo for i in range(1, len(feature_cols) + 1) for combo in itertools.combinations(feature_cols, i) ]
>>> all_combinations
[('TV',),
 ('Radio',),
 ('Newspaper',),
 ('TV', 'Radio'),
 ('TV', 'Newspaper'),
 ('Radio', 'Newspaper'),
 ('TV', 'Radio', 'Newspaper')]