Python：获取列表连续元素的所有组合

Question

假设有一个数组，例如 x = ['A','I','R']，我想要输出为

[['A','I','R'],['A','I'],['I','R'],['A'],['I'],['R']]

我不想要的输出是：

[['A','I','R'],['A','I'],['I','R'],['A','R'],['A'],['I'],['R']]  # extra ['A','R'] which is not in sequence .

以下是会产生我不想要的输出的代码：

letter_list = [a for a in str]
all_word = []
for i in xrange(0,len(letter_list)):
    all_word = all_word + (map(list, itertools.combinations(letter_list,i))) # dont use append. gives wrong result.
all_word = filter(None,all_word) # remove empty combination
all_word = all_word + [letter_list] # add original list

我的意思是我只想要序列的组合。是否有使用 itertools 的方法，还是我应该编写自定义函数？

- minatverma

---

可能是一个重复的问题，这里有一个链接：字符串的子串 - sloth

请注意，如我在Code Review SE的回答中所解释的那样，指数级的内存使用。对于长度为1000个字符的文本，如果像这样分割，将需要167167000个字符，并且占用1.25GB的内存空间。 - holroy

Answer 1

是的，你可以使用 itertools：

>>> x = ['A', 'I', 'R']
>>> xs = [x[i:j] for i, j in itertools.combinations(range(len(x)+1), 2)]
>>> xs
[['A'], ['A', 'I'], ['A', 'I', 'R'], ['I'], ['I', 'R'], ['R']]
>>> sorted(xs, key=len, reverse=True)
[['A', 'I', 'R'], ['A', 'I'], ['I', 'R'], ['A'], ['I'], ['R']]

Credit: answer by hochl

- Asclepius

Answer 2

尝试使用yield：

x = ['A','I','R']

def groupme(x):
    s = tuple(x)
    for size in range(1, len(s) + 1):
        for index in range(len(s) + 1 - size):
            yield list(x[index:index + size])

list(groupme(x))

>>> [['A'], ['I'], ['R'], ['A', 'I'], ['I', 'R'], ['A', 'I', 'R']]

- xiº

---

从当前的解决方案来看，这是唯一一个不使用大量内存的方法，它使用yield在迭代时仅提供所需的单词。然而，对于使用1000个字符的测试用例，它仍会生成500500个不同的元素。 :-D - holroy

Answer 3

不要试图太神奇：两个循环就可以实现你想要的功能；一个循环用于可能的序列起始位置，内部循环用于可能的序列长度：

x = "AIR" # strings are iterables/sequences, too!
all_words = []
for begin in xrange(len(x)):
    for length in xrange(1,len(x) - begin+1):
        all_words.append(x[begin:begin+length])

- Marcus Müller

---

如上面的评论所述，当文本输入超过几百个字符时，这确实会占用大量内存。 - holroy

Answer 4

使用列表推导式：

letters=['A', 'I', 'R']
[letters[start:end+1] 
 for start in xrange(len(letters)) 
 for end in xrange(start, len(letters))]

[['A'], ['A', 'I'], ['A', 'I', 'R'], ['I'], ['I', 'R'], ['R']]

如果有必要按照您提出的顺序（从长到短，长度相同时按起始位置）进行排序，可以使用以下方法：

[letters[start:start+l+1]
 for l in range(len(letters))[::-1]
 for start in xrange(len(letters)-l)]

[['A', 'I', 'R'], ['A', 'I'], ['I', 'R'], ['A'], ['I'], ['R']]

针对Holroy的评论，如果您使用生成器表达式（只需将外部的[]替换为()）而不是使用列表推导式，则可以获得更少内存占用的代码。但在这种情况下，您必须小心，不要多次使用结果或尝试在结果上使用列表方法（例如len或删除元素）。

- Teudimundo

---

如上面的评论所述，当文本输入超过几百个字符时，这确实会占用大量内存。 - holroy