Python: 从一个列表中生成所有可能的序列组合并限制字符长度

Question

我的问题与这个问题完全相同。我有一个字符数组（列表）。我想从该列表中获取所有可能的序列组合，但是限制字符数量（例如：最多2个字符）。此外，在排列行中不能重复使用单个字符：

chars = ['a', 'b', 'c', 'd']

# output
output = [['a', 'b', 'c', 'd'],
          ['ab', 'c', 'd'],
          ['a', 'bc', 'd'],
          ['a', 'b', 'cd'],
          ['ab', 'cd'],
          ['abc', 'd'], # this one will be exempted
          ['a', 'bcd'],  # this one will be exempted
          ['abcd']]  # this one will be exempted

我知道我可以在生成和构建序列时检查条件，以省略超出限制的字符组合。但这会增加运行时间。我的目的是减少现有执行时间。

没有字符计数限制，组合将像2^(N-1)一样生成。如果列表超过15个字符，执行程序需要太长时间。因此，我想通过字符限制减少组合计数。

优先考虑性能。我已经进行了两天的研究和尝试，但没有成功。

- Steve.NayLinAung

---

你没有任何尝试展示吗？ - Jongware

@usr2564301，确实是这样。我尝试了上面重复问题中的解决方案，并进行了修改。我甚至尝试了Python itertools.combination源代码并进行了一些修改。但所有的尝试都没有达到预期。非常抱歉我的无能。 - Steve.NayLinAung

尝试其他答案并以某种原因拒绝它们并不是无能，但我对你的结论表示怀疑。以下是您可以添加的内容：前面的问题有4个答案（但可能有些相同）。由于您担心性能，请添加这些答案的计时，并指出指数问题。 - Jongware

@usr2564301，我仍在努力解决问题，并将尝试您的建议。谢谢。 - Steve.NayLinAung

Answer 1

一种方法是迭代输入列表并逐步构建组合。在每个步骤中，从输入列表中取出下一个字符并添加到先前生成的组合中。

from collections import defaultdict

def make_combinations(seq, maxlen):
    # memo is a dict of {length_of_last_word: list_of_combinations}
    memo = defaultdict(list)
    memo[1] = [[seq[0]]]  # put the first character into the memo

    seq_iter = iter(seq)
    next(seq_iter)  # skip the first character
    for char in seq_iter:
        new_memo = defaultdict(list)

        # iterate over the memo and expand it
        for wordlen, combos in memo.items():
            # add the current character as a separate word
            new_memo[1].extend(combo + [char] for combo in combos)

            # if the maximum word length isn't reached yet, add a character to the last word
            if wordlen < maxlen:
                word = combos[0][-1] + char

                new_memo[wordlen+1] = newcombos = []
                for combo in combos:
                    combo[-1] = word  # overwrite the last word with a longer one
                    newcombos.append(combo)

        memo = new_memo

    # flatten the memo into a list and return it
    return [combo for combos in memo.values() for combo in combos]

输出：

[['a', 'b', 'c', 'd'], ['ab', 'c', 'd'], ['a', 'bc', 'd'],
 ['a', 'b', 'cd'], ['ab', 'cd']]

---

这种实现在输入较短的情况下比朴素的itertools.product方法慢：

input: a b c d
maxlen: 2
iterations: 10000

itertools.product: 0.11653625800136069 seconds
make_combinations: 0.16573870600041118 seconds

但是当输入列表较长时，它会快速处理：

input: a b c d e f g h i j k
maxlen: 2
iterations: 10000

itertools.product: 6.9087735799985240 seconds
make_combinations: 1.2037671390007745 seconds

- Aran-Fey

Answer 2

通常，更容易生成一个大的组合/排列列表，然后过滤结果以达到所需的输出。您可以使用递归生成器函数获取组合，然后过滤和连接结果：

chars = ['a', 'b', 'c', 'd']
def get_combos(c):
  if len(c) == 1:
    yield c
  else:
     yield c
     for i in range(len(c)-1):
       yield from get_combos([c[d]+c[d+1] if d == i else c[d] if d < i else c[d+1] for d in range(len(c)-1)])

final_listing = list(get_combos(chars))
last_results = list(filter(lambda x:all(len(c) < 3 for c in x), [a for i, a in enumerate(final_listing) if a not in final_listing[:i]]))

输出：

[['a', 'b', 'c', 'd'], ['ab', 'c', 'd'], ['ab', 'cd'], ['a', 'bc', 'd'], ['a', 'b', 'cd']]

- Ajax1234