0

假设我们在 python 2.7.3 中有一个列表

s=['a','b','a','a']

我想计算这个列表元素的所有可能组合，而不干扰它的原始序列，在这种情况下它们将如下所示：

['a','b','ab','ba','aa','abaa','aba','baa']

所以需要 8 个组合。

4

7 回答 7

2

您可以使用itertools.permutations：

>>> res = set()
>>> for k in range(1, len(s)+1):
...     for comb in itertools.permutations(s, k):
...             res.add(''.join(comb))
... 
>>> sorted(res[1:])
['a','aa','aaa','aaab','aab','aaba','ab','aba','abaa','b','ba','baa','baaa']

请注意，有13种可能的组合。

于 2013-09-08T11:28:43.403 回答
1 
>>> s=['a','b','a','a']
>>> {''.join(s[i:j]) for i in range(len(s)) for j in range(i+1,len(s)+1)}
set(['a', 'aba', 'aa', 'ab', 'ba', 'abaa', 'b', 'baa'])

这会生成一个与所需列表具有相同值的集合。

于 2013-09-08T13:25:59.853 回答
0 
In [6]: s=['a','b','a','a']    
In [7]: from itertools import combinations

In [8]: print list(combinations(s, r=3))
[('a', 'b', 'a'), ('a', 'b', 'a'), ('a', 'a', 'a'), ('b', 'a', 'a')]

In [9]: print list(''.join(c) for c in combinations(s, r=3))
['aba', 'aba', 'aaa', 'baa']

In [10]: print set(''.join(c) for c in combinations(s, r=3))
set(['aba', 'aaa', 'baa'])

我认为，您需要itertools.combinationsand itertools.chain。

In [32]: comb_list = list(list(''.join(c) for c in combinations(s, r=i)) for i in range(1,4))

In [33]: print comb_list
[['a', 'b', 'a', 'a'], ['ab', 'aa', 'aa', 'ba', 'ba', 'aa'], ['aba', 'aba', 'aaa', 'baa']]

In [34]: print set(chain(*comb_list))
set(['a', 'aa', 'b', 'aaa', 'ba', 'aba', 'ab', 'baa'])

In [35]: print sorted(set(chain(*comb_list)))
['a', 'aa', 'aaa', 'ab', 'aba', 'b', 'ba', 'baa']
于 2013-09-08T10:32:23.640 回答
0

您想要生成列表的所有唯一子列表。

使用itertools.islice?和一个跨越所有可能长度的for循环（1 ...列表的长度）。将所有结果添加到set.

这个问题也可以很容易地表达为两个嵌套的 for 循环，将它们的结果添加到一个集合中。

于 2013-09-08T10:32:24.413 回答
0

您可以使用itertools.combinations：

>>> res = set()
>>> for k in range(1, len(s)+1):
...     for comb in itertools.combinations(s, k):
...             res.add(''.join(comb))
... 
>>> sorted(res)
['a', 'aa', 'aaa', 'ab', 'aba', 'abaa', 'b', 'ba', 'baa']

请注意，有9种可能的组合。你忘记aaa了你的例子。

于 2013-09-08T10:32:36.847 回答
0

以下程序建议有13种组合：

#!/usr/bin/python3

def combinations(prefix, xs, theset):
    for i in range(len(xs)):
        x = xs[i]
        other = xs[:i] + xs[i+1:]
        newprefix = prefix + x
        if newprefix not in theset:
            theset.add(newprefix)
            combinations(newprefix, other, theset)


theset = set()
combinations('', 'abaa', theset)
print(theset)

输出：

{'a', 'aba', 'aa', 'ab', 'aaa', 'ba', 'aab', 'aaba', 'aaab', 'abaa', 'baa', 'baaa', 'b'}
于 2013-09-08T10:48:36.803 回答
0

我认为您最初的问题有点不清楚，您应该更好地定义组合，但这里有一些可能的解释：

我主要使用链来组合多个生成器，对于大多数算法，我每个序列长度都有一个生成器。对于给定的示例，序列长度为 1、2、3、4。对于每个序列长度，我解决一个子问题。

数学组合，将每个“a”视为不同的值，这有 15 个元素和重复项。子问题只是应用combinations函数itertools

from itertools import chain, combinations
s=['a','b','a','a']
list(chain(*(combinations(s,i) for i in range(1,1+len(s)))))
Out[3]: 
[('a',),
 ('b',),
 ('a',),
 ('a',),
 ('a', 'b'),
 ('a', 'a'),
 ('a', 'a'),
 ('b', 'a'),
 ('b', 'a'),
 ('a', 'a'),
 ('a', 'b', 'a'),
 ('a', 'b', 'a'),
 ('a', 'a', 'a'),
 ('b', 'a', 'a'),
 ('a', 'b', 'a', 'a')]

同上，但没有重复，这个有 9 个元素，它主要还包括'aaa'.

from itertools import chain, combinations
s=['a','b','a','a']
set(chain(*(combinations(s,i) for i in range(1,1+len(s)))))
Out[6]: 
set([('b',),
 ('b', 'a'),
 ('a', 'b'),
 ('a', 'a', 'a'),
 ('a', 'a'),
 ('a', 'b', 'a'),
 ('a',),
 ('a', 'b', 'a', 'a'),
 ('b', 'a', 'a')])

最后你可能想找到所有的子序列，这有 10 个元素，但又重复了。子问题可以通过一个聪明的zip技巧来解决。我们提供给 zipN参数，N作为给定子问题的序列长度，我们通过解压缩列表来传递这些参数*。每个参数都是原始列表，但从更远的一个位置开始。所以第一个论点是s[0:]，第二个s[1]，...。Zip 本质上通过获取每个参数的第一个元素并将它们组合成一个元组来组合这些列表，然后它获取每个参数的第二个元素并将它们组合成一个元组，依此类推，直到到达其中一个列表的末尾。因此，例如zip(s[0:],s[1:])会导致[('a','b'),('b','a'),('a','a')]，它在 3 个元组后停止，因为len(s[1:])==3. 如您所见，这会导致所有长度为 2 的子序列。

from itertools import chain
s=['a','b','a','a']
list(chain(*(zip(*(s[i:] for i in range(n))) for n in range(1,1+len(s)))))
Out[4]: 
[('a',),
 ('b',),
 ('a',),
 ('a',),
 ('a', 'b'),
 ('b', 'a'),
 ('a', 'a'),
 ('a', 'b', 'a'),
 ('b', 'a', 'a'),
 ('a', 'b', 'a', 'a')]

最后，与上面相同但具有唯一元素，这将产生与您的示例相同的输出：

from itertools import chain
s=['a','b','a','a']
set(chain(*(zip(*(s[i:] for i in range(n))) for n in range(1,1+len(s)))))
set([('a', 'b', 'a'),
     ('b', 'a'),
     ('a', 'b'),
     ('a', 'b', 'a', 'a'),
     ('b', 'a', 'a'),
     ('a', 'a'),
     ('b',),
     ('a',)])

我希望其中至少有一个是您想要的。此外，从给定的输出到您提供的字符串列表只不过是应用一些连接。

于 2013-09-08T14:01:24.897 回答