나는 문자열이 있습니다. 문자열의 문자 순서를 변경하여 해당 문자열에서 모든 순열을 생성하고 싶습니다. 예를 들면 다음과 같습니다.
x='stack'
내가 원하는 것은 이와 같은 목록입니다.
l=['stack','satck','sackt'.......]
현재 나는 문자열의 목록 캐스트를 반복하고, 무작위로 2 개의 문자를 선택하고이를 조옮김하여 새 문자열을 형성하고 l의 캐스트를 설정하기 위해 추가합니다. 문자열의 길이에 따라 가능한 순열 수를 계산하고 설정된 크기가 한계에 도달 할 때까지 반복을 계속합니다. 더 나은 방법이 있어야합니다.
답변
itertools 모듈에는 permutations ()라는 유용한 메소드가 있습니다. 문서 는 다음과 같이 말합니다.
itertools.permutations (iterable [, r])
반복 가능한 요소의 연속 r 길이 순열을 반환합니다.
r이 지정되지 않았거나 None이면 r은 기본적으로 iterable의 길이로 설정되고 가능한 모든 전체 길이 순열이 생성됩니다.
순열은 사전 식 정렬 순서로 생성됩니다. 따라서 입력 iterable이 정렬되면 순열 튜플이 정렬 된 순서로 생성됩니다.
하지만 순열 된 문자를 문자열로 결합해야합니다.
>>> from itertools import permutations
>>> perms = [''.join(p) for p in permutations('stack')]
>>> perms
[ ‘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 ‘]
중복으로 인해 문제가 발생하면 set다음 과 같은 중복이없는 구조에 데이터를 맞추십시오 .
>>> perms = [''.join(p) for p in permutations('stacks')]
>>> len(perms)
720
>>> len(set(perms))
360
이것이 우리가 전통적으로 타입 캐스트라고 생각하는 것이 아니라 set()생성자 에 대한 호출에 더 가깝다는 것을 지적 해준 @pst에게 감사드립니다 .
답변
모든 N을 얻을 수 있습니다! 많은 코드가없는 순열
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)
답변
다음은 최소한의 코드로 문자열 순열을 수행하는 또 다른 방법입니다. 우리는 기본적으로 루프를 만든 다음 한 번에 두 문자를 계속 교체합니다. 루프 내부에는 재귀가 있습니다. 인덱서가 문자열 길이에 도달 할 때만 인쇄합니다. 예 : 시작점을위한 ABC i와 루프를위한 재귀 매개 변수 j
여기에 왼쪽에서 오른쪽으로 위에서 아래로 어떻게 작동하는지 시각적 인 도움말이 있습니다 (순열 순서).
코드 :
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)
답변
Stack Overflow 사용자는 이미 강력한 솔루션을 게시했지만 또 다른 솔루션을 보여주고 싶었습니다. 이건 더 직관적 인 것 같아요
아이디어는 주어진 문자열에 대해 알고리즘 (의사 코드)에 의해 재귀 할 수 있다는 것입니다.
순열 = char + 문자열의 char에 대한 순열 (문자열-문자)
누군가에게 도움이되기를 바랍니다!
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
답변
다음은 고유 한 순열을 반환하는 간단한 함수입니다.
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)
답변
@Adriano 및 @illerucis가 게시 한 것과 다른 접근 방식이 있습니다. 이것은 더 나은 런타임을 가지고 있으며 시간을 측정하여 직접 확인할 수 있습니다.
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
임의의 문자열 “dadffddxcf”의 경우 순열 라이브러리의 경우 1.1336 초,이 구현의 경우 9.125 초, @Adriano 및 @illerucis 버전의 경우 16.357 초가 소요되었습니다. 물론 여전히 최적화 할 수 있습니다.
답변
itertools.permutations좋지만 반복되는 요소를 포함하는 시퀀스를 잘 처리하지 못합니다. 내부적으로 시퀀스 인덱스를 순열하고 시퀀스 항목 값을 알지 못하기 때문입니다.
물론, itertools.permutations세트를 통해 출력을 필터링하여 중복을 제거 할 수 있지만 여전히 중복을 생성하는 데 시간을 낭비하고 기본 시퀀스에 여러 반복 요소가있는 경우 많은 중복이 있습니다. 또한 컬렉션을 사용하여 결과를 보관하면 RAM이 낭비되어 처음부터 반복기를 사용하는 이점이 무효화됩니다.
다행히 더 효율적인 접근 방식이 있습니다. 아래 코드는 14 세기 인도의 수학자 Narayana Pandita의 알고리즘을 사용합니다.이 알고리즘은 Permutation 에 대한 Wikipedia 기사에서 찾을 수 있습니다 . 이 고대 알고리즘은 순서대로 순열을 생성하는 가장 빠른 방법 중 하나이며 반복되는 요소를 포함하는 순열을 적절하게 처리한다는 점에서 매우 강력합니다.
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)
산출
aadt
aatd
adat
adta
atad
atda
daat
data
dtaa
taad
tada
tdaa
물론 산출 된 문자열을 목록으로 수집하려면 다음을 수행 할 수 있습니다.
list(lexico_permute_string('data'))
또는 최신 Python 버전 :
[*lexico_permute_string('data')]
