いくつかの要素の順序を維持する順列

Question

Pythonの実装を探していますが、おそらく何かから変換することができます。

私は4つのスペースに続くワード猫であるstring"cats "を、持っている場合は、どのように私は言葉猫の秩序を維持可能な順列のすべてを見つけることができます。つまり、最初の実際の文字、つまりtなどの置換は探していませんが、代わりにcatsにある文字の間の空白の可能な配置のすべてを探します。

いくつかの例：

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

、それぞれの可能な最初の位置のために、それを選択し、残りの位置との組み合わせを完了します。 itertoolsモジュールからcombinationsで - あなたは4つの文字が非常に簡単であるべきな組み合わせを作成することができます

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

あなたは再帰を使用することができます。

nスペースがある場合は、最初に最初の文字の前にスペースがいくつあるかを選択します。それをkと呼んでください。次に、n-kスペースと残りの文字で関数を呼び出します。

Answer 3

文字列「cats」には、スペースを挿入する場所が5つあります（前後、および文字の間にスペースを挿入します）。本質的に、これは、ゼロ部分を含む5の整数部分への4のすべての整数パーティションの生成の問題である。このようなパーティションを生成する最も簡単な方法のオン

再帰的である：再帰挿入空間のあらゆるレベルで現在のプレースホルダに、次のレベルを呼び出し、および（可能の）indertingことなく次のレベルを呼び出す

Answer 4

はありませんこの作品？それは、アルゴリズムではありませんが、それはあなたの目的を果たす必要があります。

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

    return False 

Answer 5

あなたは順列を見つけた場合、あなたは正規表現でそれらをフィルタリングすることができます：

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

プリント：

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

Answer 6

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 

Answer 7

：同様に、あなたは直接、所望の機能を実装することができます。

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