Python: Generating multiple combinations of strings with spaces

Question

I have an array of n words as strings such as:

input: ["just", "a", "test"]

What I need to do is create all possible combinations of these words separated by spaces as well as in combination with the original strings. For example, the above should create:

output: [["just", "a", "test"], ["just a", "test"], ["just a test"], ["just", "a test"]]

I've been using itertools but can't get it to do what I need. What I have at the moment:

iterable = ['just', 'a', 'test']

for n in chain.from_iterable(combinations(iterable, n) for n in range(len(iterable)+1)):
    print(n)

The following almost works as required:

iterable = ['just', 'a', 'test']
L = [''.join(reversed(x)).rstrip()
     for x in product(*[(c, c+' ') for c in reversed(iterable)])]
print(L)

Thank you.

EDIT:

To clarify how this should work for an array of length 4: input: ['an', 'even', 'bigger', 'test']`

output: 
['an', 'even', 'bigger', 'test']
['an even', 'bigger', 'test']
['an even bigger', 'test']
['an even bigger test']

['an', 'even bigger', 'test']
['an even', 'bigger test']
['an', 'even bigger test']
['an', 'even', 'bigger test']

I think the Sage library provides a way to compute the set of non-crossing partitions from `input` that you need. Given that set `intermediate`, you then just need `[map(" ".join, x) for x in intermediate]`. — chepner, Apr 24 '18 at 15:57

jpp · Answer 1 · 2018-04-24T16:16:25.833

This is one solution. The partitions function is courtesy of @Kiwi.

from itertools import combinations

iterable = ['just', 'a', 'test', 'and', 'another']

n = len(iterable)

def partitions(items, k):

    def split(indices):
        i=0
        for j in indices:
            yield items[i:j]
            i = j
        yield items[i:]

    for indices in combinations(range(1, len(items)), k-1):
        yield list(split(indices))

for i in range(1, n+1):
    for x in partitions(iterable, i):
        print([' '.join(y) for y in x])

['just a test and another']
['just', 'a test and another']
['just a', 'test and another']
['just a test', 'and another']
['just a test and', 'another']
['just', 'a', 'test and another']
['just', 'a test', 'and another']
['just', 'a test and', 'another']
['just a', 'test', 'and another']
['just a', 'test and', 'another']
['just a test', 'and', 'another']
['just', 'a', 'test', 'and another']
['just', 'a', 'test and', 'another']
['just', 'a test', 'and', 'another']
['just a', 'test', 'and', 'another']
['just', 'a', 'test', 'and', 'another']

@JPMillward, Ah I understand now, OK. – jpp Apr 24 '18 at 16:01 — jpp, Apr 24 '18 at 16:01
That is perfect. You're a genius. Thank you very much. – Pythonius Apr 24 '18 at 16:16 — Pythonius, Apr 24 '18 at 16:16

Patrick · Answer 2 · 2018-04-24T17:21:09.657

You can try this (compatible for both python 2.x and python 3.x):

s = ["this", "is", "just", "a", "simple", "test"] # the input
sepCount = len(s) - 1 # separator count of the input
output = [] # output

for i in range(0, 2 ** sepCount): # iterate through all possible combinations
    t = s # modified string
    j = i # for converting to binary
    for k in reversed(range(sepCount)):
        if j % 2 == 0:
            t = t[ : k] + [" ".join(t[k : k + 2])] + t [k + 2 :] # replace separator to " "
        j = j // 2
    output.append(t)

print(output)

Output:

[['this is just a simple test'],
['this is just a simple', 'test'],
['this is just a', 'simple test'],
['this is just a', 'simple', 'test'],
['this is just', 'a simple test'],
['this is just', 'a simple', 'test'],
['this is just', 'a', 'simple test'],
['this is just', 'a', 'simple', 'test'],
['this is', 'just a simple test'],
['this is', 'just a simple', 'test'],
['this is', 'just a', 'simple test'],
['this is', 'just a', 'simple', 'test'],
['this is', 'just', 'a simple test'],
['this is', 'just', 'a simple', 'test'],
['this is', 'just', 'a', 'simple test'],
['this is', 'just', 'a', 'simple', 'test'],
['this', 'is just a simple test'],
['this', 'is just a simple', 'test'],
['this', 'is just a', 'simple test'],
['this', 'is just a', 'simple', 'test'],
['this', 'is just', 'a simple test'],
['this', 'is just', 'a simple', 'test'],
['this', 'is just', 'a', 'simple test'],
['this', 'is just', 'a', 'simple', 'test'],
['this', 'is', 'just a simple test'],
['this', 'is', 'just a simple', 'test'],
['this', 'is', 'just a', 'simple test'],
['this', 'is', 'just a', 'simple', 'test'],
['this', 'is', 'just', 'a simple test'],
['this', 'is', 'just', 'a simple', 'test'],
['this', 'is', 'just', 'a', 'simple test'],
['this', 'is', 'just', 'a', 'simple', 'test']]

The motive: there are n-1 separators (,) for a list of length n. There are 2^(n-1) ways of replacing the ,s with an empty space. By iterating all these 2^(n-1) possible ways, you can generate all possible combinations of these words separated by spaces.

This also works perfectly. Very impressive, thank you. – Pythonius Apr 24 '18 at 16:18 — Pythonius, Apr 24 '18 at 16:18

Python: Generating multiple combinations of strings with spaces

2 Answers2