Recursive permutation of words in a sentence

Question

I want to recursively get permutations of the words in sentence keeping adjacent words in packs of two, together from left to right.

So as an example if I consider a, B, c, D are 4 words and the main sentence has 5 occurrences of the 4 words as:

main sentence: a + B + c + a + D

I would get four sentences as

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

which all have the same length as the main sentence, and it should be noted that the last word in the main sentence i.e. D only comes once and only at the end of the sentence after a because in the main sentence no word follows that.

Answer 1

You can use the following recursive generator function:

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

so that:

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

would return:

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