[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;
}

답변

당신은 많은 문자열을 얻을 것입니다, 그것은 확실합니다 …

$\ sum_ {i = x} ^ y {\ frac {r!} {{(ri)}!}}$
여기서 x와 y는 그것들을 정의하는 방법이고 r은 우리가 선택하는 문자의 수입니다. 필요에 따라 이것을 생성하고 느슨해지지 말고 파워 세트를 생성 한 다음 문자열 길이를 필터링해야합니다.

다음은 이것들을 생성하는 가장 좋은 방법은 아니지만, 그럼에도 불구하고 흥미 롭습니다.

Knuth (volume 4, fascicle 2, 7.2.1.3)에 따르면 (s, t) 조합은 반복 할 때 한 번에 s + 1을 취한 것과 동일하다는 것을 알려줍니다. (s, t) 조합은 Knuth와 같습니다 ${t \ 선택 {s + t}$ . 먼저 이진 형식 (길이 (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;
        }
    }