Рекурсивная перестановка слов в предложении

Question

Я хочу recursively получить перестановки слов в предложении, сохраняя смежные слова в пачках по два, вместе слева направо.

В качестве примера, если я рассмотрю a, B, c, D, это 4 слова, а в главном предложении есть 5 вхождений из 4 слов:

основное предложение: a + B + c + a + D

Я бы получил четыре предложения как

c + a + B + c + a
a + B + c + a + D
a + B + c + a + B
B + c + a + B + c

, длина которых равна длине основного предложения, и следует отметить, что последнее слово в главном предложении, т.е. D, встречается только один раз и только вконец предложения после a, потому что в основном предложении ни одно слово не следует за этим.

Answer 1

Вы можете использовать следующую функцию рекурсивного генератора:

def adjacent_combinations(sentence, target=None, length=0):
    if not target:
        for target in set(sentence):
            for combination in adjacent_combinations(sentence, target, 1):
                yield combination
    elif length == len(sentence):
        yield [target]
    else:
        for a, b in set(zip(sentence, sentence[1:])):
            if a == target:
                for combination in adjacent_combinations(sentence, b, length + 1):
                    yield [a] + combination

, чтобы:

list(adjacent_combinations(['a', 'B', 'c', 'a', 'D']))

вернулось:

[['B', 'c', 'a', 'B', 'c'],
 ['c', 'a', 'B', 'c', 'a'],
 ['a', 'B', 'c', 'a', 'B'],
 ['a', 'B', 'c', 'a', 'D']]

Answer 2

Вы можете использовать генератор с рекурсией:

s = ['a', 'B', 'c', 'a', 'D']
def combinations(d, _c = []):
  if len(_c) == len(d)+1:
     yield _c
  else:
     for i in d:
       if not _c or any(s[c] == _c[-1] and s[c+1] == i for c in range(len(s)-1)):
          for k in combinations(d, _c+[i]):
            yield k

print('\n'.join(' + '.join(i) for i in combinations(set(s))))

Выход:

a + B + c + a + B
a + B + c + a + D
B + c + a + B + c
c + a + B + c + a