Permutations that support the order of some elements

Question

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

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

Some examples:

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

Answer 1

, . itertools.combinations ( . ).

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)))

( , ):

>>> 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

combinations ( , ?). , , , :

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)

, . , :

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

Answer 2

, 4 - combinations itertools.

from itertools import combinations

for comb in combinations(range(len("cats    ")), len("cats")):
    # comb is a 4 tuple containing the indices where to insert the letters "cats".

:

empty = [" "]*len("cats    ")

for comb in combinations(range(len("cats    ")), len("cats")):
    newstring = list(empty)  # make a copy
    for idx, letter in zip(comb, "cats"):  # insert the letters
        newstring[idx] = letter
    print(''.join(newstring))  # join and print

cats    
cat s   
cat  s  
cat   s 
cat    s
ca ts   
ca t s  
ca t  s 
ca t   s
ca  ts  
ca  t s 
ca  t  s
[...]

Answer 3

.

n, . k. n-k .

Answer 4

"" (, ). 4 5 , .

: ()

Answer 5

? , :

def check_word(word):
    if word.replace(" ", "") == "cats":
        return True

    return False

Answer 6

If you find permutations, you can filter them by regular expression:

import itertools
import re

string = 'cats    '
pattern = ' *c *a *t *s *'
matcher = re.compile(pattern)

perms = itertools.permutations(string)
se = set([''.join(p) for p in perms])
li = list(filter(matcher.search, se))

Print

['   cats ',
 'c a t  s',
 'ca  t  s',
   ....
 'c   ats ',
 '  ca ts ',
 ' ca t  s',
 ' c at s ',
 'ca t   s',
 'ca  ts  ']

Answer 7

import itertools
str_in = "cats   "
str_in_nospace = str_in.replace(" ", "")
p = itertools.permutations(str_in, r=None)
for itm in p:
    str_curent = ''.join(itm)
    str_curent_nospace = str_curent.replace(" ", "")
    if str_curent_nospace == str_in_nospace:
        print str_curent