代码之家 › 专栏 › 技术社区 › Sasha

你能用C语言写一个置换函数吗?

algorithm python c#

Sasha · 技术社区 · 16 年前

我非常喜欢这个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

4 回复 | 直到 16 年前

Marc Gravell 16 年前

嗯,可能不是我写的方式,但是:

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

是你的意见,我不是 完全地 清楚地回答这个问题;如果你的意思是“为什么这个有用?”-除此之外,还有一系列蛮力的场景,你想尝试不同的排列方式-例如,对于诸如差旅销售人员之类的小订单问题(这些问题不够大,不足以保证有更复杂的解决方案),你可能想检查是否最好去基地、A、B、C、基地、基地、A、C、B、基地、基地、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 )本身是一个复杂的主题-乔恩有一个自由的章节(6) in his book 但是。代码的其余部分非常类似于您最初的问题——只是使用LINQ提供 + (数组)。

Joel Coehoorn 16 年前

C有一个yield关键字,我认为它的工作原理与您的python代码的工作原理基本相同,所以要得到一个基本上直接的翻译不太难。

然而,这是一个递归的解决方案,所以尽管它很简单,但它是次优的。我个人并不理解所有涉及的数学,但对于高效的数学排列,你需要用到 factoradics . 这篇文章应该有助于:
http://msdn.microsoft.com/en-us/library/aa302371.aspx

[更新]:另一个答案提出了一个很好的观点:如果你只是使用排列来进行无序排列,还有更好的选择。具体来说, Knuth/Fisher-Yates shuffle .

Samuel 16 年前

虽然您不能在保持简洁的同时移植它,但是您可以非常接近它。

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

-6

Ronald Wildenberg 16 年前

不完全到我必须承认的程度后,一些评论,但下面的代码可以用来生成一个随机排列的有限序列。它是 Fisher-Yates shuffle algorithm . 该示例使用 int 但是你可以用任何 Enumerable<T> 当然。

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

按随机值排序(在本例中是 Guid )基本上是排列你的列表。是否 NewGuid 随机性的一个好来源是有争议的,但它是一个优雅而紧凑的解决方案(尽管对于另一个问题,那么问题实际上是关于)。

取自 Jeff Atwood (Coding Horror) .