Permutations maintaining order of some elements

Question

Looking for an implementation in Python but I can probably translate from anything.

If I have the string "cats ", which is the word cats followed by four spaces, how can I find all of the possible permutations that maintain the order of the word cats. That is I'm not looking for any permutations where a is the first actual letter, or t, etc., but instead all of the possible arrangements of white space in between the letters in cats.

Some examples:

"cats    "
"c ats   "
"  cat  s"
"c a t s "
" c a t s"

Answer 1

This is a solution, not an algorithm :) The algorithm is buried in the implementation of itertools.combinations (but see below for an implementation without builtin library functions).

from functools import reduce
from itertools import combinations

def assign(v, p):
  v[p[0]] = p[1]
  return v

def interp(word, letter, size):
  return (''.join(reduce(assign, zip(comb, word), [letter] * size))
          for comb in combinations(range(size), len(word)))

Example (using dots instead of spaces to make them more visible):

>>> print('\n'.join(interp("cats", ".", 6)))
cats..
cat.s.
cat..s
ca.ts.
ca.t.s
ca..ts
c.ats.
c.at.s
c.a.ts
c..ats
.cats.
.cat.s
.ca.ts
.c.ats
..cats

It's actually pretty easy to implement combinations (but why bother, since it is already defined?). Here's one solution which does way too much tuple concatenation to be efficient, but demonstrates the algorithm:

def combs(vec, count, start=0):
  if count == 0:
    yield ()
  else:
    for i in range(start, len(vec) + 1 - count):
      for c in combs(vec, count - 1, i + 1):
        yield((i,) + c)

In other words, for each possible first position, choose that and complete the combination with the remaining positions. Similarly, you could directly implement the desired function:

def interp(word, letter, size):
  if len(word) == 0:
    yield letter * size
  else:
    for i in range(size + 1 - len(word)):
      for comb in interp(word[1:], letter, size - i - 1):
        yield letter * i + word[0] + comb