CODEWITHSUNDEEP
pythonalgorithm
stumpbeard
stumpbeard

Reputation: 61

Permutations maintaining order of some elements

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"

Upvotes: 4

Views: 2452

Answers (7)

rici
rici

Reputation: 241761

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

Upvotes: 5

MSeifert
MSeifert

Reputation: 152667

You can create the combinations where the 4 letters should be quite easily - with combinations from the itertools module.

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

Then you simply need to insert them at the correct place and join it:

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
[...]

Upvotes: 2

Hum4n01d
Hum4n01d

Reputation: 1370

Wouldn’t this work? It’s not an algorithm but it should serve your purpose:

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

    return False

Upvotes: 0

Roman Fursenko
Roman Fursenko

Reputation: 688

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

Upvotes: 0

kingstante
kingstante

Reputation: 716

If you find the permutations, you can filter them out by regex:

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

Prints:

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

Upvotes: 0

MBo
MBo

Reputation: 80197

For string "cats" you have five places to insert spaces (before, after and between letters). Essentially this is problem of generation of all integer partitions of number 4 into 5 integer parts, including zero parts.

On of the simplest methods to generate such partitions is recursive: at every level of recursion insert space into the current placeholder, and call next level, and call next level without inderting (of possible)

Upvotes: 0

Julien
Julien

Reputation: 15071

You can use recursion.

If you have n spaces, first choose how many spaces come before the first letter. Call it k. Then call your function with n-k spaces and the remaining letters.

Upvotes: 0

Related Questions