문자열 목록 순열 알고리즘

Question

순열 알고리즘을 작성하는 방법을 이해하는 데 도움이 필요합니다. (이것이 순열이라면, 그들은 순서대로 있어야하고 같은 값을 사용해야한다).

List<string> str = new List<string>{"a", "b", "c", "d"}; 

이 목록에서 사용 가능한 각 순열의 목록을 어떻게 얻을 수 있습니까? 예를 들면.

1. a, b, c, d
2. ab, c, d
3. ab, cd
4. abc, d
5. abcd
6. a, bc, d
7. a, bcd
8. a, b, cd

어떤 이유로 나는 처음부터 패턴을 찾을 수 없습니다. 또한 조인 된 문자열에 X 문자와 같은 개수가있는 경우 순열을 무시할 수 있기를 바랍니다. 그래서 X가 4라면, 그 목록에서 5가 존재하지 않을 것이고 7 개의 순열이있을 것입니다.

private List<string> permute(List<string> values, int maxPermutation) 
{ 
    //alittle help on starting it would be great :) 
} 

나는 this을보고 읽었지만 순서를 유지하지 않습니다.

Answer 1

이것은 다소 간단합니다. 쉼표를 붙이거나 아무 것도 입력 할 수없는 곳이 세 곳 있습니다. 2^3 2 진수에 해당하는 8 개의 조합이 있습니다.

0부터 7까지의 각 숫자에 대해 이진 표현을 생성하십시오. 이진 표현이 1 인 각 위치에 쉼표를 넣으십시오. 0이있는 곳에 쉼표를 넣지 마십시오.

for (int m = 0 ; m != 8 ; m++) { 
    string s = "a"; 
    if ((m & 1) != 0) s += ","; 
    s += "b"; 
    if ((m & 2) != 0) s += ","; 
    s += "c"; 
    if ((m & 4) != 0) s += ","; 
    s += "d"; 
    Console.WriteLine(s);  
} 

Answer 2

재귀 적 접근법을 취할 수 있습니다. 첫 번째 문자를 사용하고 두 번째 문자부터 시작하여 가능한 모든 조합을 만듭니다 (이것은 재귀 ...). 각 문자에 첫 문자를 앞에 추가합니다. 그런 다음 처음 두 글자를 함께 사용하고 세 번째 글자부터 모든 조합을 재귀 적으로 작성합니다. 등등 ...

추가 요구 사항 : X 자로 된 문자열을 포함하는 모든 "조합"을 제외하려면 첫 번째 문자열을 구성 할 때이 번호를 건너 뛰십시오.

Answer 3

("분할 문제"가 아닌)가 아닌 순열 문제 위에 이진 방법은 정확하고이 실제로 분할 문제이다. 파티션의 수는 기하 급수적으로보다 더 빨리 성장의 (E^E^n)은 그래서 큰 문자열 정말 느려질 수 있기 때문에

http://en.wikipedia.org/wiki/Partition_of_a_set

은 조심.

Answer 4

다음 코드를 시도해보십시오. 나는 그것을 테스트하지 않았지만 그것이 당신이 찾고있는 것이라고 생각합니다.

List<string> str = new List<string>{ "a", "h", "q", "z", "b", "d" }; 
List<List<string>> combinations = combine(str.OrderBy(s=>s).ToList()); 

List<List<string>> combine(List<string> items) 
{ 
    List<List<string>> all = new List<List<string>>(); 

    // For each index item in the items array 
    for(int i = 0; i < items.Length; i++) 
    { 
     // Create a new list of string 
     List<string> newEntry = new List<string>(); 
     // Take first i items 
     newEntry.AddRange(items.Take(i)); 
     // Concatenate the remaining items 
     newEntry.Add(String.concat(items.Skip(i))); 
     // Add these items to the main list 
     all.Add(newEntry); 

     // If this is not the last string in the list 
     if(i + 1 < items.Length) 
     { 
      // Process sub-strings 
      all.AddRange(combine(items.Skip(i + 1).ToList())); 
     } 
    } 
    return all; 
} 

는 조합 (또는 치환 또는 변형)을 생성해야하는 경우는 다음 Combinatorics 환상적인 라이브러리입니다.