有条件的排列

Question

社区！

我正在尝试解决此任务：

输入：我有一个单词列表。输出：我需要返回每个符合以下条件的排列列表：

• 所有排列在输入列表中都有一个邻居
• 列表元素的顺序无法更改

示例：

In: ['cat', 'sat', 'on']
Out: [('cat', 'sat', 'on'), ('cat', 'sat'), ('sat', 'on'), ('cat'), ('sat'), ('on')]

解释示例：不允许排列（'cat'，'on'），因为'cat'和'on'在输入列表中不是邻居。不允许进行排列（“ cat”，“ on”，“ sat”），因为inat列表中的“ on”在使用“ sat”时更正确，但是在此排列中，单词的顺序没有保存。

我试图编写此函数并在之后清除结果：

def findsubsets(S,m): 
    return set(itertools.combinations(S, m))

但是我认为，然后我们生成所有可能的组合（在大多数操作系统情况下，我的列表中包含很多单词），我们正在使用大量内存，因此我试图找到解决方案，但不会生成组合，然后我将选择所需的排列。我正在寻找明确的解决方案，而无需进行其他转换。

我正在写Python 3，我正在寻找内存最少的这些任务的解决方案。我在此站点上搜索了类似的问题，但没有找到。

感谢您解决此问题。

Answer 1

看来您正在寻找的是一组可能的子列表，您可以通过简单的循环获得它。

original = ['cat', 'sat', 'on']
result = []

n = len(original)
for i in range(n):
    for j in range(i + 1, n + 1):
        # Append tuple(original[i:j]) if that's what you are looking for
        result.append(original[i:j])

print(result)

[['cat'], ['cat', 'sat'], ['cat', 'sat', 'on'], ['sat'], ['sat', 'on'], ['on']]