[string] 문자열의 가능한 모든 순열 목록 생성
변수 문자 목록을 포함하여 x와 y 문자 사이의 문자열의 가능한 모든 순열 목록을 생성하는 방법은 무엇입니까?
모든 언어가 작동하지만 이식 가능해야합니다.
답변
이를 수행하는 몇 가지 방법이 있습니다. 일반적인 방법은 재귀, 메모 또는 동적 프로그래밍을 사용합니다. 기본 아이디어는 길이가 1 인 모든 문자열의 목록을 생성 한 다음 각 반복에서 마지막 반복에서 생성 된 모든 문자열에 대해 문자열의 각 문자와 개별적으로 연결된 해당 문자열을 추가하는 것입니다. (아래 코드의 변수 인덱스는 마지막 반복의 시작과 다음 반복을 추적합니다)
일부 의사 코드 :
list = originalString.split('')
index = (0,0)
list = [""]
for iteration n in 1 to y:
index = (index[1], len(list))
for string s in list.subset(index[0] to end):
for character c in originalString:
list.add(s + c)
그런 다음 길이가 x보다 작은 모든 문자열을 제거해야합니다. 이는 목록에서 첫 번째 (x-1) * len (originalString) 항목입니다.
답변
역 추적을 사용하는 것이 좋습니다
#include <stdio.h>
#include <string.h>
void swap(char *a, char *b) {
char temp;
temp = *a;
*a = *b;
*b = temp;
}
void print(char *a, int i, int n) {
int j;
if(i == n) {
printf("%s\n", a);
} else {
for(j = i; j <= n; j++) {
swap(a + i, a + j);
print(a, i + 1, n);
swap(a + i, a + j);
}
}
}
int main(void) {
char a[100];
gets(a);
print(a, 0, strlen(a) - 1);
return 0;
}답변
당신은 많은 문자열을 얻을 것입니다, 그것은 확실합니다 …
여기서 x와 y는 그것들을 정의하는 방법이고 r은 우리가 선택하는 문자의 수입니다. 필요에 따라 이것을 생성하고 느슨해지지 말고 파워 세트를 생성 한 다음 문자열 길이를 필터링해야합니다.
다음은 이것들을 생성하는 가장 좋은 방법은 아니지만, 그럼에도 불구하고 흥미 롭습니다.
Knuth (volume 4, fascicle 2, 7.2.1.3)에 따르면 (s, t) 조합은 반복 할 때 한 번에 s + 1을 취한 것과 동일하다는 것을 알려줍니다. (s, t) 조합은 Knuth와 같습니다 . 먼저 이진 형식 (길이 (s + t))으로 각 (s, t) 조합을 생성하고 각 1의 왼쪽에있는 0의 수를 세어이를 알아낼 수 있습니다.
10001000011101->는 순열이됩니다 : {0, 3, 4, 4, 4, 1}
답변
Python의 Knuth에 따른 비 재귀 솔루션 :
def nextPermutation(perm):
k0 = None
for i in range(len(perm)-1):
if perm[i]<perm[i+1]:
k0=i
if k0 == None:
return None
l0 = k0+1
for i in range(k0+1, len(perm)):
if perm[k0] < perm[i]:
l0 = i
perm[k0], perm[l0] = perm[l0], perm[k0]
perm[k0+1:] = reversed(perm[k0+1:])
return perm
perm=list("12345")
while perm:
print perm
perm = nextPermutation(perm)
답변
원하는 세트의 일부를 수행하는 알고리즘을 설명하는 ” 세트의 서브 세트를 효율적으로 열거 “를 볼 수 있습니다 . 길이 x에서 y까지 N 문자의 모든 서브 세트를 신속하게 생성합니다. C로 구현되어 있습니다.
각 부분 집합에 대해 여전히 모든 순열을 생성해야합니다. 예를 들어 “abcde”에서 3자를 원하면이 알고리즘은 “abc”, “abd”, “abe”를 제공하지만 “acb”, “bac”, “bca”등
답변
Sarp의 답변을 기반으로 작동하는 일부 Java 코드 :
public class permute {
static void permute(int level, String permuted,
boolean used[], String original) {
int length = original.length();
if (level == length) {
System.out.println(permuted);
} else {
for (int i = 0; i < length; i++) {
if (!used[i]) {
used[i] = true;
permute(level + 1, permuted + original.charAt(i),
used, original);
used[i] = false;
}
}
}
}
public static void main(String[] args) {
String s = "hello";
boolean used[] = {false, false, false, false, false};
permute(0, "", used, s);
}
}
답변
다음은 C #의 간단한 솔루션입니다.
주어진 문자열의 고유 한 순열 만 생성합니다.
static public IEnumerable<string> permute(string word)
{
if (word.Length > 1)
{
char character = word[0];
foreach (string subPermute in permute(word.Substring(1)))
{
for (int index = 0; index <= subPermute.Length; index++)
{
string pre = subPermute.Substring(0, index);
string post = subPermute.Substring(index);
if (post.Contains(character))
continue;
yield return pre + character + post;
}
}
}
else
{
yield return word;
}
}
