순열/변형

Question

나는 순열과 변형을 생성 할 수있는 C# 방법을 고안하려고합니다. 나는 그것을 예제에서 가장 잘 설명한다고 생각한다. 이 작업을 수행하는 가장 좋은 방법을 찾고 있습니다. 이것이 내 머리 속에서 어떻게 생각하고 있는지.

이 방법에 대한 제안을 찾고 있는데요, 아마도 의사 코드입니까? |

ABC 
ACB 
BAC 
BCA 
CAB 
CBA 

단계 2)와 편차 :

ABC는 반복없이

단계 1) 치환된다

ABC 
    A|BC 
    AB|C 

ACB 
    A|CB 
    AC|B 

BAC 
    B|AC 
    BA|C 

BCA 
    B|CA 
    BC|A 

CAB 
    C|AB 
    CA|B 

CBA 
    C|BA 
    CB|A 

그래서 당신은

A|BC 
    AB|C 
    A|CB 
    AC|B 
    B|AC 
    BA|C 
    B|CA 
    BC|A 
    C|AB 
    CA|B 
    C|BA 
    CB|A 

업데이트의 최종 세트와 끝까지 : 내가 쓴 그냥 빨리 구현, 내가 의견 오신 것을 환영합니다, 그것은 끔찍한 알고있다.

 var perms = Permuter.Permute(new Char[] {'a', 'b', 'c'}).ToList(); 
     DisplayResult(perms); 

     foreach (var permutation in perms.ToList()) 
     { 
      var p = permutation.ToList(); 

      int splitPos = 1; 
      do 
      { 
       for (int i = 0; i < splitPos; i++) 
       { 
        Console.Write(p[i]); 
       } 

       Console.Write("|"); 

       for (int j = splitPos; j < p.Count; j++) 
       { 
        Console.Write(p[j]); 
       } 

       Console.WriteLine(""); 
       splitPos++; 
      } while (splitPos < p.Count); 
     } 

Answer 1

먼저 순열을 생성하십시오. Lexicographic 순서는 구현하기가 가장 간단합니다. Wikipedia 및 크 누스의 The Art of Computer Programming을 참조하십시오. 또한 조금 더 빨리이다 Steinhaus–Johnson–Trotter algorithm를 사용할 수

def permutations_of(seq): 
    yield seq 
    seqlen = len(seq) 
    while True: 
     j = seqlen - 2 
     while j >= 0 and seq[j] >= seq[j+1]: 
      j -= 1 

     if j < 0: break 

     i= seqlen - 1 
     while i > j and seq[i] < seq[j]: 
      i -= 1 

     seq[j],seq[i] = seq[i],seq[j] 
     seq[j+1:] = seq[-1:j:-1] 
     yield seq 

: 여기 파이썬 (source)의 하나의 구현입니다.

변형을 생성하려면 문자열을 반복하고 문자열 내의 가능한 각 위치에 해당 위치에 |을 삽입하십시오.

Answer 2

교육 목적을 찾고 그냥 permtations과 세트와 사물에서 흥미로운, 이러한 것들을 함께 넣어하는 방법을 이해하려고.

순열을 수행하는 데는 여러 가지 방법이 있으며, 그 중 많은 수가 교훈을주고 있습니다. 여기에 하나의 스케치가 당신을 생각하게합니다.

0에서 31까지의 정수 집합의 부분 집합에 대한 모든 순열을 찾는 것을 고려하십시오. 따라서 집합 {2, 3, 5}으로 선택하고 순열 (2, 3, 5) , (2, 5, 3), (3, 2, 5), (3,5,2), (5,2,3) 및 (5,3,2) 그렇게하는 방법?

변경 불가능한 단일 32 비트 정수를 포함하는 구조체를 정의하십시오. struct를 IEnumerable<int>으로 구현하고 그 안에 설정된 모든 비트에 해당하는 숫자를 열거하십시오. 또한 주어진 비트가 제거 된 구조체 구조체를 다시 가져 오는 "제거"메서드를 만듭니다.

• 이 설정이 비어 :

  이제이 같은 재귀 알고리즘을 만들 수 있습니까? 그런 다음 하나의 순열, 빈 시퀀스가 ​​있습니다.

• 집합이 비어 있지 않습니까?그런 다음 집합의 각 항목에 대해 항목없이 항목을 원래 집합으로 만들고, 작은 집합의 모든 시퀀스를 반복적으로 만들고, 각 시퀀스에 항목을 추가합니다.

즉, 세트가 {2, 3, 5}라고 가정합니다. 너 뭐하니? 각 항목 2, 3, 5의 경우 :

Remove the item 2. That leaves 3 and 5. Permute 3, 5. How? 
    Remove item 3. That leaves 5. Permute that. 
     Remove item 5. That leaves nothing. Permute that. 
      The result is the empty sequence. 
     Append 5 to the empty sequence. That's (5). 
    Append 3. That's (5, 3). 
    Remove 5. That leaves 3. Permute that. 
     Remove 3. That leaves nothing. Permute that. 
      The result is the empty sequence. 
     Append 3 to the empty sequence. That's (3). 
    Append 5. That's (3, 5). 
Append 2 to each of those results. That's (2, 5, 3) and (2, 3, 5). 
Remove 3. That leaves 2 and 5. Permute that.... 

코드로 그 선반 조금 까다로운하지만 매우 교화 될 것입니다.