Musisz jednak połączyć swoje permutowane litery jako ciągi znaków.
[„stack”, „stakc”, „stcak”, „stcka”, „stkac”, „stkca”, „satck”, „satkc”, „sactk”, „sackt”, „saktc”, „sakct”, „ sctak ”,„ sctka ”,„ scatk ”,„ scakt ”,„ sckta ”,„ sckat ”,„ sktac ”,„ sktca ”,„ skatc ”,„ skact ”,„ skcta ”,„ skcat ”,„ tsack ” , „tsakc”, „tscak”, „tscka”, „tskac”, „tskca”, „tasck”, „taskc”, „tacsk”, „tacks”, „taksc”, „takcs”, „tcsak”, „ tcska ”,„ tcask ”,„ tcaks ”,„ tcksa ”,„ tckas ”,„ tksac ”,„ tksca ”,„ tkasc ”,„ tkacs ”,„ tkcsa ”,„ tkcas ”,„ astck ”,„astkc ”,„ asctk ”,„ asckt ”,„ asktc ”,„ askct ”,„ atsck ”,„ atskc ”,„ atcsk ”,„ atcks ”,„ atksc ”,„ atkcs ”,„ acstk ”,„ acskt ” , „actsk”, „actks”, „ACKst”, „Ackts”, „akstc”, „aksct”, „aktsc”, „aktcs”, „akcst”, „akcts”, „cstak”, „cstka”, „ csatk ”,„ csakt ”,„ cskta ”,„ cskat ”,„ ctsak ”,„ ctska ”,„ ctask ”,„ ctaks ”,„ ctksa ”,„ ctkas ”,„ castk ”,„ caskt ”,„ catsk ” , „catks”, „cakst”, „cakts”, „cksta”, „cksat”, „cktsa”, „cktas”, „ckast”, „ckats”, „kstac”, „kstca”, „ksatc”,„ksact”, „kscta”, „kscat”, „ktsac”, „ktsca”, „ktasc”, „ktacs”, „ktcsa”, „ktcas”, „kastc”, „kasct”, „katsc”, „katcs „,„ kacst ”,„ kacts ”,„ kcsta ”,„ kcsat ”,„ kctsa ”,„ kctas ”,„ kcast ”,„ kcats ”]
Jeśli masz problem z duplikatami, spróbuj dopasować dane do struktury bez duplikatów, takich jak set
:
Podziękowania dla @pst za wskazanie, że to nie jest to, co tradycyjnie myślelibyśmy o rzutowaniu typu, ale raczej o wywołaniu set()
konstruktora.
set(...)
nie "rzuca". Raczej generuje (i zwraca) zbiór reprezentujący kolekcję wejściową: raz wygenerowany nie ma powiązania z kolekcją wejściową (i jest innym obiektem, a nie tylko innym widokiem).bool
jest to funkcja, która ocenia do bool (prawda / fałsz) w zależności od sygnału wejściowego. Uważam, że użycie słowa „cast” jest fałszywe i wprowadzające w błąd ...Możesz zdobyć wszystkie N! permutacje bez dużej ilości kodu
def permutations(string, step = 0): # if we've gotten to the end, print the permutation if step == len(string): print "".join(string) # everything to the right of step has not been swapped yet for i in range(step, len(string)): # copy the string (store as array) string_copy = [character for character in string] # swap the current index with the step string_copy[step], string_copy[i] = string_copy[i], string_copy[step] # recurse on the portion of the string that has not been swapped yet (now it's index will begin with step + 1) permutations(string_copy, step + 1)
źródło
step == len(string)
zamiaststep == len(string) - 1
?Oto inny sposób przeprowadzania permutacji łańcucha przy minimalnym kodzie. Zasadniczo tworzymy pętlę, a następnie wymieniamy dwa znaki na raz. Wewnątrz pętli będziemy mieć rekursję. Zauważ, że drukujemy tylko wtedy, gdy indeksatory osiągną długość naszego ciągu. Przykład: ABC i jako punkt początkowy i parametr j rekursji dla naszej pętli
oto pomoc wizualna, jak to działa od lewej do prawej od góry do dołu (jest to kolejność permutacji)
kod :
def permute(data, i, length): if i==length: print(''.join(data) ) else: for j in range(i,length): #swap data[i], data[j] = data[j], data[i] permute(data, i+1, length) data[i], data[j] = data[j], data[i] string = "ABC" n = len(string) data = list(string) permute(data, 0, n)
źródło
Użytkownicy Stack Overflow opublikowali już kilka mocnych rozwiązań, ale chciałem pokazać jeszcze inne. Ten uważam za bardziej intuicyjny
Chodzi o to, że dla danego ciągu: możemy powtórzyć algorytm (pseudokod):
Mam nadzieję, że to komuś pomoże!
def permutations(string): """ Create all permutations of a string with non-repeating characters """ permutation_list = [] if len(string) == 1: return [string] else: for char in string: [permutation_list.append(char + a) for a in permutations(string.replace(char, "", 1))] return permutation_list
źródło
Oto prosta funkcja zwracająca unikalne permutacje:
def permutations(string): if len(string) == 1: return string recursive_perms = [] for c in string: for perm in permutations(string.replace(c,'',1)): revursive_perms.append(c+perm) return set(revursive_perms)
źródło
revursive_perms
->recursive_perms
. 2. Oszczędziłoby to pamięć RAM i czas, gdybyrecursive_perms
był to zestaw, a nie lista, którą konwertujesz na zestaw w instrukcji return. 3. Bardziej wydajne byłoby użycie cięcia ciągów znaków zamiast.replace
konstruowania argumentu do rekurencyjnego wywołaniapermutations
. 4. Używaniestring
jako nazwy zmiennej nie jest dobrym pomysłem, ponieważ zasłania to nazwę standardowegostring
modułu.Oto inne podejście, różniące się od tego, co opublikowali @Adriano i @illerucis. Ma to lepszy czas działania, możesz to sprawdzić, mierząc czas:
def removeCharFromStr(str, index): endIndex = index if index == len(str) else index + 1 return str[:index] + str[endIndex:] # 'ab' -> a + 'b', b + 'a' # 'abc' -> a + bc, b + ac, c + ab # a + cb, b + ca, c + ba def perm(str): if len(str) <= 1: return {str} permSet = set() for i, c in enumerate(str): newStr = removeCharFromStr(str, i) retSet = perm(newStr) for elem in retSet: permSet.add(c + elem) return permSet
W przypadku dowolnego ciągu znaków „dadffddxcf” zajęło to 1,1336 sek. Dla biblioteki permutacji, 9,125 sek. Dla tej implementacji i 16,357 sek. Dla wersji @ Adriano i @illerucis. Oczywiście nadal możesz to zoptymalizować.
źródło
itertools.permutations
jest dobry, ale nie radzi sobie dobrze z sekwencjami zawierającymi powtarzające się elementy. Dzieje się tak, ponieważ wewnętrznie permutuje indeksy sekwencji i nie zwraca uwagi na wartości elementów sekwencji.Jasne, możliwe jest przefiltrowanie wyjścia
itertools.permutations
przez zbiór w celu wyeliminowania duplikatów, ale nadal marnuje się czas na generowanie tych duplikatów, a jeśli w sekwencji podstawowej jest kilka powtarzających się elementów, będzie dużo duplikatów. Ponadto użycie kolekcji do przechowywania wyników marnuje pamięć RAM, co w pierwszej kolejności neguje korzyści płynące z używania iteratora.Na szczęście istnieją bardziej wydajne podejścia. Poniższy kod wykorzystuje algorytm XIV-wiecznego indyjskiego matematyka Narayana Pandita, który można znaleźć w artykule Wikipedii na temat permutacji . Ten starożytny algorytm jest nadal jednym z najszybszych znanych sposobów generowania permutacji w kolejności i jest dość solidny, ponieważ prawidłowo obsługuje permutacje zawierające powtarzające się elementy.
def lexico_permute_string(s): ''' Generate all permutations in lexicographic order of string `s` This algorithm, due to Narayana Pandita, is from https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order To produce the next permutation in lexicographic order of sequence `a` 1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, the permutation is the last permutation. 2. Find the largest index k greater than j such that a[j] < a[k]. 3. Swap the value of a[j] with that of a[k]. 4. Reverse the sequence from a[j + 1] up to and including the final element a[n]. ''' a = sorted(s) n = len(a) - 1 while True: yield ''.join(a) #1. Find the largest index j such that a[j] < a[j + 1] for j in range(n-1, -1, -1): if a[j] < a[j + 1]: break else: return #2. Find the largest index k greater than j such that a[j] < a[k] v = a[j] for k in range(n, j, -1): if v < a[k]: break #3. Swap the value of a[j] with that of a[k]. a[j], a[k] = a[k], a[j] #4. Reverse the tail of the sequence a[j+1:] = a[j+1:][::-1] for s in lexico_permute_string('data'): print(s)
wynik
Oczywiście, jeśli chcesz zebrać otrzymane ciągi na listę, możesz to zrobić
list(lexico_permute_string('data'))
lub w ostatnich wersjach Pythona:
[*lexico_permute_string('data')]
źródło
dlaczego nie jesteś prosty:
from itertools import permutations perms = [''.join(p) for p in permutations(['s','t','a','c','k'])] print perms print len(perms) print len(set(perms))
nie otrzymujesz duplikatu, jak widzisz:
['stack', 'stakc', 'stcak', 'stcka', 'stkac', 'stkca', 'satck', 'satkc', 'sactk', 'sackt', 'saktc', 'sakct', 'sctak', 'sctka', 'scatk', 'scakt', 'sckta', 'sckat', 'sktac', 'sktca', 'skatc', 'skact', 'skcta', 'skcat', 'tsack', 'tsakc', 'tscak', 'tscka', 'tskac', 'tskca', 'tasck', 'taskc', 'tacsk', 'tacks', 'taksc', 'takcs', 'tcsak', 'tcska', 'tcask', 'tcaks', 'tcksa', 'tckas', 'tksac', 'tksca', 'tkasc', 'tkacs', 'tkcsa', 'tkcas', 'astck', 'astkc', 'asctk', 'asckt', 'asktc', 'askct', 'atsck', 'atskc', 'atcsk', 'atcks', 'atksc', 'atkcs', 'acstk', 'acskt', 'actsk', 'actks', 'ackst', 'ackts', 'akstc', 'aksct', 'aktsc', 'aktcs', 'akcst', 'akcts', 'cstak', 'cstka', 'csatk', 'csakt', 'cskta', 'cskat', 'ctsak', 'ctska', 'ctask', 'ctaks', 'ctksa', 'ctkas', 'castk', 'caskt', 'catsk', 'catks', 'cakst', 'cakts', 'cksta', 'cksat', 'cktsa', 'cktas', 'ckast', 'ckats', 'kstac', 'kstca', 'ksatc', 'ksact', 'kscta', 'kscat', 'ktsac', 'ktsca', 'ktasc', 'ktacs', 'ktcsa', 'ktcas', 'kastc', 'kasct', 'katsc', 'katcs', 'kacst', 'kacts', 'kcsta', 'kcsat', 'kctsa', 'kctas', 'kcast', 'kcats'] 120 120 [Finished in 0.3s]
źródło
def permute(seq): if not seq: yield seq else: for i in range(len(seq)): rest = seq[:i]+seq[i+1:] for x in permute(rest): yield seq[i:i+1]+x print(list(permute('stack')))
źródło
Widzieć
itertools.combinations
lubitertools.permutations
.źródło
Oto nieco ulepszona wersja kodu illerucis do zwracania listy wszystkich permutacji łańcucha
s
z różnymi znakami (niekoniecznie w leksykograficznej kolejności sortowania), bez używania itertools:def get_perms(s, i=0): """ Returns a list of all (len(s) - i)! permutations t of s where t[:i] = s[:i]. """ # To avoid memory allocations for intermediate strings, use a list of chars. if isinstance(s, str): s = list(s) # Base Case: 0! = 1! = 1. # Store the only permutation as an immutable string, not a mutable list. if i >= len(s) - 1: return ["".join(s)] # Inductive Step: (len(s) - i)! = (len(s) - i) * (len(s) - i - 1)! # Swap in each suffix character to be at the beginning of the suffix. perms = get_perms(s, i + 1) for j in range(i + 1, len(s)): s[i], s[j] = s[j], s[i] perms.extend(get_perms(s, i + 1)) s[i], s[j] = s[j], s[i] return perms
źródło
Kolejna inicjatywa i rekurencyjne rozwiązanie. Chodzi o to, aby wybrać literę jako oś, a następnie utworzyć słowo.
# for a string with length n, there is a factorial n! permutations alphabet = 'abc' starting_perm = '' # with recursion def premuate(perm, alphabet): if not alphabet: # we created one word by using all letters in the alphabet print(perm + alphabet) else: for i in range(len(alphabet)): # iterate over all letters in the alphabet premuate(perm + alphabet[i], alphabet[0:i] + alphabet[i+1:]) # chose one letter from the alphabet # call it premuate(starting_perm, alphabet)
Wynik:
źródło
Oto naprawdę prosta wersja generatora:
def find_all_permutations(s, curr=[]): if len(s) == 0: yield curr else: for i, c in enumerate(s): for combo in find_all_permutations(s[:i]+s[i+1:], curr + [c]): yield "".join(combo)
Myślę, że nie jest tak źle!
źródło
def f(s): if len(s) == 2: X = [s, (s[1] + s[0])] return X else: list1 = [] for i in range(0, len(s)): Y = f(s[0:i] + s[i+1: len(s)]) for j in Y: list1.append(s[i] + j) return list1 s = raw_input() z = f(s) print z
źródło
from itertools import permutations perms = [''.join(p) for p in permutations('ABC')] perms = [''.join(p) for p in permutations('stack')]
źródło
def perm(string): res=[] for j in range(0,len(string)): if(len(string)>1): for i in perm(string[1:]): res.append(string[0]+i) else: return [string]; string=string[1:]+string[0]; return res; l=set(perm("abcde"))
Jest to jeden ze sposobów generowania permutacji z rekurencją. Kod można łatwo zrozumieć, przyjmując ciągi „a”, „ab” i „abc” jako dane wejściowe.
Masz wszystkie N! permutacje z tym, bez duplikatów.
źródło
Każdy kocha zapach własnego kodu. Po prostu dzielę się tym, który uważam za najprostszy:
def get_permutations(word): if len(word) == 1: yield word for i, letter in enumerate(word): for perm in get_permutations(word[:i] + word[i+1:]): yield letter + perm
źródło
Ten program nie eliminuje duplikatów, ale myślę, że jest to jedno z najbardziej wydajnych podejść:
s=raw_input("Enter a string: ") print "Permutations :\n",s size=len(s) lis=list(range(0,size)) while(True): k=-1 while(k>-size and lis[k-1]>lis[k]): k-=1 if k>-size: p=sorted(lis[k-1:]) e=p[p.index(lis[k-1])+1] lis.insert(k-1,'A') lis.remove(e) lis[lis.index('A')]=e lis[k:]=sorted(lis[k:]) list2=[] for k in lis: list2.append(s[k]) print "".join(list2) else: break
źródło
def permute_all_chars(list, begin, end): if (begin == end): print(list) return for current_position in range(begin, end + 1): list[begin], list[current_position] = list[current_position], list[begin] permute_all_chars(list, begin + 1, end) list[begin], list[current_position] = list[current_position], list[begin] given_str = 'ABC' list = [] for char in given_str: list.append(char) permute_all_chars(list, 0, len(list) -1)
źródło
Prostsze rozwiązanie wykorzystujące permutacje.
from itertools import permutations def stringPermutate(s1): length=len(s1) if length < 2: return s1 perm = [''.join(p) for p in permutations(s1)] return set(perm)
źródło
Wszystkie możliwe słowa ze stosem
from itertools import permutations for i in permutations('stack'): print(''.join(i))
permutations(iterable, r=None)
Zwraca kolejne permutacje długości r elementów w iterowalnej.
Jeśli r nie jest określony lub ma wartość Brak, to r przyjmuje domyślnie długość elementu iterowalnego i generowane są wszystkie możliwe permutacje o pełnej długości.
Permutacje są emitowane w porządku leksykograficznym. Tak więc, jeśli iterowalne wejście jest posortowane, krotki permutacji zostaną utworzone w kolejności posortowanej.
Elementy są traktowane jako niepowtarzalne na podstawie ich pozycji, a nie wartości. Więc jeśli elementy wejściowe są unikalne, w każdej permutacji nie będzie powtarzających się wartości.
źródło
Jest to rozwiązanie rekurencyjne,
n!
które akceptuje zduplikowane elementy w ciąguimport math def getFactors(root,num): sol = [] # return condition if len(num) == 1: return [root+num] # looping in next iteration for i in range(len(num)): # Creating a substring with all remaining char but the taken in this iteration if i > 0: rem = num[:i]+num[i+1:] else: rem = num[i+1:] # Concatenating existing solutions with the solution of this iteration sol = sol + getFactors(root + num[i], rem) return sol
Rozwiązanie sprawdziłem biorąc pod uwagę dwa elementy, liczba kombinacji jest,
n!
a wynik nie może zawierać duplikatów. Więc:inpt = "1234" results = getFactors("",inpt) if len(results) == math.factorial(len(inpt)) | len(results) != len(set(results)): print("Wrong approach") else: print("Correct Approach")
źródło
Oto prosta i nieskomplikowana rekurencyjna implementacja;
def stringPermutations(s): if len(s) < 2: yield s return for pos in range(0, len(s)): char = s[pos] permForRemaining = list(stringPermutations(s[0:pos] + s[pos+1:])) for perm in permForRemaining: yield char + perm
źródło
stringPermutations
liście - możesz iterować bezpośrednio po nim, npfor perm in stringPermutations(s[:pos] + s[pos+1:]):
. Ponadto, można uprościćfor
pętlę używającenumerate
zamiastrange
, i wyeliminowaćchar = s[pos]
zadanie:for pos, char in enumerate(s):
.# swap ith and jth character of string def swap(s, i, j): q = list(s) q[i], q[j] = q[j], q[i] return ''.join(q) # recursive function def _permute(p, s, permutes): if p >= len(s) - 1: permutes.append(s) return for i in range(p, len(s)): _permute(p + 1, swap(s, p, i), permutes) # helper function def permute(s): permutes = [] _permute(0, s, permutes) return permutes # TEST IT s = "1234" all_permute = permute(s) print(all_permute)
# swap ith and jth character of string def swap(s, i, j): q = list(s) q[i], q[j] = q[j], q[i] return ''.join(q) # iterative function def permute_using_stack(s): stk = [(0, s)] permutes = [] while len(stk) > 0: p, s = stk.pop(0) if p >= len(s) - 1: permutes.append(s) continue for i in range(p, len(s)): stk.append((p + 1, swap(s, p, i))) return permutes # TEST IT s = "1234" all_permute = permute_using_stack(s) print(all_permute)
# swap ith and jth character of string def swap(s, i, j): q = list(s) q[i], q[j] = q[j], q[i] return ''.join(q) # finds next lexicographic string if exist otherwise returns -1 def next_lexicographical(s): for i in range(len(s) - 2, -1, -1): if s[i] < s[i + 1]: m = s[i + 1] swap_pos = i + 1 for j in range(i + 1, len(s)): if m > s[j] > s[i]: m = s[j] swap_pos = j if swap_pos != -1: s = swap(s, i, swap_pos) s = s[:i + 1] + ''.join(sorted(s[i + 1:])) return s return -1 # helper function def permute_lexicographically(s): s = ''.join(sorted(s)) permutes = [] while True: permutes.append(s) s = next_lexicographical(s) if s == -1: break return permutes # TEST IT s = "1234" all_permute = permute_lexicographically(s) print(all_permute)
źródło