Permutations Aufrechterhaltung der Reihenfolge einiger Elemente

Question

Auf der Suche nach einer Implementierung in Python, aber ich kann wahrscheinlich von allem übersetzen.

Wenn ich die string"cats ", die das Wort Katzen von vier Leerzeichen gefolgt ist, wie kann ich alle möglichen Permutationen , die die Reihenfolge der Wort Katzen halten. Das heißt, ich suche keine Permutationen, bei denen a der erste tatsächliche Buchstabe oder t usw. ist, sondern stattdessen alle möglichen Anordnungen von Leerzeichen zwischen den Buchstaben in cats.

Einige Beispiele:

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

Answer 1

Dies ist eine Lösung, kein Algorithmus :) Der Algorithmus ist in der Implementierung von itertools.combinations begraben (aber siehe unten) für eine Implementierung ohne eingebaute Bibliotheksfunktionen).

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

Beispiel (Punkte anstelle von Leerzeichen verwenden, damit sie besser sichtbar):

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

Es ist eigentlich ziemlich einfach combinations zu implementieren (aber warum die Mühe, da es bereits definiert ist?). Hier ist eine Lösung, die funktioniert viel zu viel Tupel Verkettung effizient zu sein, sondern zeigt den Algorithmus:

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) 

Mit anderen Worten, für jede mögliche erste Position, wählen Sie das und vervollständigen die Kombination mit den übrigen Positionen. Ebenso können Sie direkt die gewünschte Funktion implementieren:

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

können Sie Rekursion verwenden.

Wenn Sie n Leerzeichen haben, wählen Sie zuerst aus, wie viele Leerzeichen vor dem ersten Buchstaben stehen. Nennen Sie es k. Dann rufe deine Funktion mit n-k Leerzeichen und den restlichen Buchstaben auf.

Answer 3

Für die Zeichenfolge "Katzen" haben Sie fünf Stellen zum Einfügen von Leerzeichen (vor, nach und zwischen Buchstaben). Im Wesentlichen ist dies das Problem der Erzeugung aller Ganzzahl-Partitionen von Nummer 4 in 5 Integer-Teile, einschließlich Nullteilen.

Auf der einfachsten Methoden, wie Partitionen zu erzeugen, ist rekursiv: auf jeder Ebene der Rekursion Einsatzraum in den aktuellen Platzhalter, und nächste Ebene nennen, und nächste Ebene aufrufen, ohne (möglicher) inderting

Answer 4

Würde nicht diese Arbeit? Es ist nicht ein Algorithmus, aber es sollte Ihren Zweck dienen:

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

    return False 

Answer 5

Wenn Sie die Permutationen zu finden, Sie können sie herausfiltern durch 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)) 

Drucke:

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

Sie können die Kombinationen schaffen, in dem die vier Buchstaben ganz leicht sein sollte - mit combinations vom itertools Modul.

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

Dann müssen Sie sie einfach an der richtigen Stelle einzusetzen und verbinden es:

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