你能在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).其余代码非常类似于您原来的问题 - 只需使用LINQ来提供+(对于数组)的道德等价物.