Перестановки с условием

Question

сообщество!

Я пытаюсь решить эту задачу:

Ввод: у меня есть список слов. Вывод: мне нужно вернуть список перестановок, каждая из которых соответствует следующим условиям:

• у всех перестановок есть сосед во входном списке
• порядок элементов списка не может быть изменен

Пример:

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

Объясняющий пример: перестановка ('cat', 'on') недопустима, поскольку 'cat' и 'on' не являются соседями в списке ввода. Перестановка ('cat', 'on', 'sat') недопустима, потому что 'on' в списке входов правильнее, когда 'sat', но в этой перестановке порядок слов не был сохранен.

Я пытался написать эту функцию и очистить ее результат после:

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

Но я думаю, что тогда мы генерируем все возможные комбинации (в большинстве случаев у меня есть списки с большим количеством словами), мы используем много памяти, поэтому я пытаюсь найти решение, которое не будет генерировать комбинации, и после того, как я выберу необходимые перестановки. Я нахожу для ясного решения, без дополнительных преобразований.

Я пишу на Python 3, и я ищу решение этой задачи с наименьшим объемом памяти. Я искал похожие вопросы на этом сайте, но не нашел.

Заранее спасибо за решение этой проблемы.

Answer 1

Краткий рекурсивный подход:

original = ['cat', 'sat', 'on']
def combos(d):
  yield tuple(d)
  yield from ([] if not d else combos(d[1:]))
  yield from ([] if not d else combos(d[:-1]))

result = list(set(filter(None, combos(original))))

Вывод:

[('sat', 'on'), ('sat',), ('cat',), ('on',), ('cat', 'sat'), ('cat', 'sat', 'on')]

Answer 2

Похоже, что вы ищете
набор возможных подсписков, которые вы можете получить с помощью простых циклов.

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']]