C# 에서처럼 우아하게 순열 함수를 작성할 수 있습니까?

Question

나는이 6 라인 솔루션을 많이 좋아하고 C#에서 그것을 복제하려고합니다. 나는 몇 가지 의견 후에 인정해야하는 점에 안 전체

def permute(xs, pre=[]): 
    if len(xs) == 0: 
    yield pre 
    for i, x in enumerate(xs): 
    for y in permute(xs[:i] + xs[i+1:], pre + [x]): 
     yield y 

Answer 1

글쎄, 아마 내가 그것을 쓸 줄 방법이 아니라 : 귀하의 코멘트를 다시

static IEnumerable<T[]> Permute<T>(this T[] xs, params T[] pre) { 
    if (xs.Length == 0) yield return pre; 
    for (int i = 0; i < xs.Length; i++) { 
     foreach (T[] y in Permute(xs.Take(i).Union(xs.Skip(i+1)).ToArray(), pre.Union(new[] { xs[i] }).ToArray())) { 
      yield return y; 
     } 
    } 
} 

---

; 나는 전체가 인 질문에 명확하지 않다; "왜 이것이 유용할까요?" - 다른 것들 중에서도 다른 순열을 시도하려는 무차별 대폭의 시나리오가 있습니다. 예를 들어, 여행자와 같은 작은 주문 문제 (더 정교한 솔루션을 보증하기에 충분히 크지 않음), {base, A, B, C, base}, {base, A, C, B, base}, {base, B, A, C, base} 등을 확인하는 것이 가장 좋습니다.

"이 방법을 어떻게 사용합니까?" - 테스트되지는 않았지만 다음과 같은 문구가 있습니다.

int[] values = {1,2,3}; 
foreach(int[] perm in values.Permute()) { 
    WriteArray(perm); 
} 

void WriteArray<T>(T[] values) { 
    StringBuilder sb = new StringBuilder(); 
    foreach(T value in values) { 
     sb.Append(value).Append(", "); 
    } 
    Console.WriteLine(sb); 
} 

"어떻게 작동합니까?" - 반복자 블록 (yield return)은 복잡한 주제입니다. Jon은 무료 챕터 (6) in his book을 가지고 있습니다. 나머지 코드는 원래 질문과 매우 비슷합니다. LINQ를 사용하여 도덕적으로 등가 인 + (배열의 경우)을 제공하기 만하면됩니다.

Answer 2

을하지만, 아래의 코드는 유한 시퀀스의 임의의 순열을 생성하는 데 사용할 수 있습니다 : 기본적으로, 배열의 요소 순서를 무작위로 바꾸어 넣습니다. 이는 Fisher-Yates shuffle algorithm의 변형입니다. 이 예제에서는 int의 시퀀스를 사용하지만 임의의 Enumerable<T>을 사용할 수 있습니다. 기본적으로 목록을 permutates (이 경우 Guid에서) 임의의 값으로

var ints = Enumerable.Range(0, 51); 
var shuffledInts = ints.OrderBy(a => Guid.NewGuid()); 

당신의 순서. NewGuid이 임의성의 좋은 출처인지 여부는 논란의 여지가 있지만, 우아하고 컴팩트 한 솔루션입니다. (다른 문제에도 불구하고 그 질문은 사실입니다).

취지 : Jeff Atwood (Coding Horror).

Answer 3

C#은 귀하의 파이썬 코드가 수행하는 것과 거의 동일하게 작동하는 것으로 보이는 상상력 키워드를 가지고 있으므로 대부분 직접적인 번역을 얻는 것이 어렵지 않습니다.

그러나 이것은 반복적 인 솔루션이므로 모든 것이 간결하기 때문에 차선책입니다. 저는 개인적으로 관련된 모든 수학을 이해하지 못하지만, 좋은 효율적인 수학적 치환을 위해서는 factoradics을 사용하고 싶습니다. 이 기사는 도움이 될 것입니다
http://msdn.microsoft.com/en-us/library/aa302371.aspx

[업데이트] : 다른 대답은 좋은 지적을 제공합니다 : 당신은 단지 더 나은 옵션을 사용할 수는 아직 없습니다 셔플을 할 순열을 사용하는 경우. 특히 Knuth/Fisher-Yatesshuffle입니다.

Answer 4

간결함을 유지하면서 포트를 포팅 할 수는 없지만 거의 닫을 수 있습니다.

public static class IEnumerableExtensions 
{ 
    public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> source) 
    { 
    if (source == null) 
     throw new ArgumentNullException("source"); 

    return PermutationsImpl(source, new T[0]); 
    } 

    private static IEnumerable<IEnumerable<T>> PermutationsImpl<T>(IEnumerable<T> source, IEnumerable<T> prefix) 
    { 
    if (source.Count() == 0) 
     yield return prefix; 

    foreach (var x in source) 
     foreach (var permutation in PermutationsImpl(source.Except(new T[] { x }), 
                prefix.Union(new T[] { x })))) 
     yield return permutation; 
    } 
}