How do I generate all possible combinations of a string with spaces between the characters? Python

Question

How do I generate all possible combinations of a string with spaces between the characters?

[in]: "foobar"

[out]: 
['foobar', 'f oobar', 'fo obar', 'f o obar', 'foo bar', 'f oo bar', 'fo o bar', 
'f o o bar', 'foob ar', 'f oob ar', 'fo ob ar', 'f o ob ar', 'foo b ar', 
'f oo b ar', 'fo o b ar', 'f o o b ar', 'fooba r', 'f ooba r', 'fo oba r', 
'f o oba r', 'foo ba r', 'f oo ba r', 'fo o ba r', 'f o o ba r', 'foob a r', 
'f oob a r', 'fo ob a r', 'f o ob a r', 'foo b a r', 'f oo b a r', 'fo o b a r', 
'f o o b a r', 'foobar', 'f oobar', 'fo obar', 'f o obar', 'foo bar', 
'f oo bar', 'fo o bar', 'f o o bar', 'foob ar', 'f oob ar', 'fo ob ar', 
'f o ob ar', 'foo b ar', 'f oo b ar', 'fo o b ar', 'f o o b ar', 'fooba r', 
'f ooba r', 'fo oba r', 'f o oba r', 'foo ba r', 'f oo ba r', 'fo o ba r', 
'f o o ba r', 'foob a r', 'f oob a r', 'fo ob a r', 'f o ob a r', 'foo b a r', 
'f oo b a r', 'fo o b a r', 'f o o b a r']

Erotica

Hint: you might consider splitting a string at each position, and then recursively doing the same for each substring – Northington

How come you changed your output so much? – Philologian

Answer 1

import itertools as it

def func(s):
   if not s:
       return [s]
   binary = it.product(['',' '], repeat=len(s)-1)
   zipped = (it.izip_longest(s , comb, fillvalue='') for comb in binary)
   return [''.join(it.chain.from_iterable(x)) for x in zipped]

func('foobar')

output:

['foobar',
 'fooba r',
 'foob ar',
 'foob a r',
 'foo bar',
 'foo ba r',
 'foo b ar',
 'foo b a r',
 'fo obar',
 'fo oba r',
 'fo ob ar',
 'fo ob a r',
 'fo o bar',
 'fo o ba r',
 'fo o b ar',
 'fo o b a r',
 'f oobar',
 'f ooba r',
 'f oob ar',
 'f oob a r',
 'f oo bar',
 'f oo ba r',
 'f oo b ar',
 'f oo b a r',
 'f o obar',
 'f o oba r',
 'f o ob ar',
 'f o ob a r',
 'f o o bar',
 'f o o ba r',
 'f o o b ar',
 'f o o b a r']

Jefferey

@Philologian -- no it doesn't. – Jefferey

you have 32 combinations as opposed to OP's 64. Also your combos are backwards. Something like for x in product(('', ' '), repeat=len(text)): L.append(''.join(chain.from_iterable(izip(text, reversed(x)))).rstrip()) should fix it – Philologian

@Philologian - it does give all the possible combinations - not with duplicates though. set(myres) == set(OPres) :) – Jefferey

you could add if not s: return [s] to support empty strings. @jamylak: It is easy to see that the solution is correct by replacing ['', ' '] with "01" and counting in binary (2) base from 0 to 2**(len(s)-1) - 1 (note: -1 in the power because to get 3 peaces of a rope we need only 2 cuts). – Umbilicate

great solution, but with new version, izip_longest is no longer support, use zip_longest instead. – Kelsey

Answer 2

Here's an implementation of my recursive idea above:

def string_spaces(s):
    ret = set([s])  # use a set rather than a list to prevent duplicates
    for i in range(1, len(s)):
        for fst in string_spaces(s[:i]):
            for snd in string_spaces(s[i:]):
                ret.add(fst + ' ' + snd)
    return ret

Example:

In [11]: string_spaces('foo')
Out[11]: set(['foo', 'f o o', 'f oo', 'fo o'])

NB: Python has a recursion limit of 1000 stack frames, so this will crash for very long strings (longer than 1000 characters).

Northington

Answer 3

from itertools import product

text = "foobar"
L = [''.join(reversed(x)).rstrip()
     for x in product(*[(c, c+' ') for c in reversed(text)])]
print L

---

['foobar', 'f oobar', 'fo obar', 'f o obar', 'foo bar', 'f oo bar', 'fo o bar', 'f o o bar', 'foob ar', 'f oob ar', 'fo ob ar', 'f o ob ar', 'foo b ar', 'f oo b ar', 'fo o b ar', 'f o o b ar', 'fooba r', 'f ooba r', 'fo oba r', 'f o oba r', 'foo ba r', 'f oo ba r', 'fo o ba r', 'f o o ba r', 'foob a r', 'f oob a r', 'fo ob a r', 'f o ob a r', 'foo b a r', 'f oo b a r', 'fo o b a r', 'f o o b a r', 'foobar', 'f oobar', 'fo obar', 'f o obar', 'foo bar', 'f oo bar', 'fo o bar', 'f o o bar', 'foob ar', 'f oob ar', 'fo ob ar', 'f o ob ar', 'foo b ar', 'f oo b ar', 'fo o b ar', 'f o o b ar', 'fooba r', 'f ooba r', 'fo oba r', 'f o oba r', 'foo ba r', 'f oo ba r', 'fo o ba r', 'f o o ba r', 'foob a r', 'f oob a r', 'fo ob a r', 'f o ob a r', 'foo b a r', 'f oo b a r', 'fo o b a r', 'f o o b a r']

Philologian

very elegant. i've never thought of using product with reversed this way =) – Erotica

Answer 4

This probably isn't the most efficient way, but I would make two lists. One has a letter as each element, and the other has each letter followed by a space. (Skip the last letter each time, since it always has no space.) A possible spacing is generated by choosing between the two lists for each letter (which can be modeled as a binary number, where 0 = no space and 1 = space)

def spacify(word):
    no_space = list(word[:-1])
    spaced = [lt + ' ' for lt in no_space]
    for i in range(2 ** (len(word) - 1)):
        spaced_word = ""
        for j in range(len(word) - 1):
            if i % 2 == 0:
                spaced_word += no_space[j]
            else:
                spaced_word += spaced[j]
            i = i // 2 # Or use bit shifting to be fancy
    print spaced_word + word[-1]

Jospeh

Not a generic solution. Neither an efficient one. – Scribbler

actually, you only need to go up to 2 ** 4 (16 combinations), because you have to strip the first and last letter of the word. – Bopp

The solution isn't totally correct, because there should be no space following the last letter. This also cuts down on the number of possibilities. Fixing now. – Jospeh

Actually, it's really not correct. This generates all possible ways to add a space, but the problem doesn't actually ask for this. For instance, fo ob ar is not listed as an example. – Jospeh

@Jospeh I think OP wants those too. But has missed those in the example provided. – Scribbler

Answer 5

from itertools import combinations

def gen_spaces(data):
    return_value = []
    size = len(data)-1
    for num_spaces in range(size):
        for comb in combinations(range(size), num_spaces+1):
            data_as_list = list(data)
            for i in comb:
                data_as_list[i] +=' '
            return_value.append(''.join(data_as_list))
    return return_value

from pprint import pprint

pprint(gen_spaces("foobar"))

Output:

['f oobar',
 'fo obar',
 'foo bar',
 'foob ar',
 'fooba r',
 'f o obar',
 'f oo bar',
 'f oob ar',
 'f ooba r',
 'fo o bar',
 'fo ob ar',
 'fo oba r',
 'foo b ar',
 'foo ba r',
 'foob a r',
 'f o o bar',
 'f o ob ar',
 'f o oba r',
 'f oo b ar',
 'f oo ba r',
 'f oob a r',
 'fo o b ar',
 'fo o ba r',
 'fo ob a r',
 'foo b a r',
 'f o o b ar',
 'f o o ba r',
 'f o ob a r',
 'f oo b a r',
 'fo o b a r',
 'f o o b a r']

Update:

You mentioned you need "all possible combinations of a string with spaces between the characters", but at the same time the example you provided in [Out] does not reflect that (i.e. you have "f o o bar" twice, "f ooba r" is missing, etc.)

In this answer I'm assuming you really want "all possible combinations of a string with spaces between the characters"

Hyper

Answer 6

Recursive solution. ( May need the use of sys.setrecursionlimit() for longer strings ):

def gen_perm(my_str):
    if len(my_str) <= 1 :
        return [my_str]
    rest_perms = gen_perm(my_str[1:])
    all_perms = [my_str[0] + perm  for perm in rest_perms ] + [my_str[0] + ' ' + perm for perm in rest_perms]
    return all_perms

print(gen_perm("foobar"))

Cobbett

Answer 7

Using itertools library (but it is pretty much the same as Titandrake) :

import itertools

foobar = "foobar"
foobar_r = range(len(foobar))


for integer in range(2**5):
    binary_mask = [ bit for bit in itertools.ifilter(lambda x: ( integer >>x)&0x01, foobar_r ) ] 
    spaces_mask = [ " " if i in binary_mask else ""  for i in foobar_r ]

    # Zip-it Crash-it Melt-it Upgrade-it
    print integer, "".join([ "".join([str(char) for char in zip_char ]) for zip_char in itertools.izip(foobar,spaces_mask)])

Bopp

Answer 8

See this is a problem of backtracking.

pseudo solution for this will be:

Traverse(given_string, new_string + given_string[idx] ,idx+1)
Traverse(given_string, new_string + ' ' + given_string[idx] ,idx+1)

Soy