Можете ли вы так же элегантно написать функцию перестановки в 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;
        }
    }
}

---

Re ваш комментарий; Я не полностью ясно понимаю вопрос; если вы имеете в виду "почему это полезно?" - среди прочего, существует целый ряд сценариев «грубой силы», в которых вы хотели бы попробовать разные варианты - например, для небольших задач заказа, таких как коммивояжер (которые недостаточно велики, чтобы требовать более сложного решения), Возможно, вы захотите проверить, лучше ли идти {база, А, В, С, база}, {база, А, С, В, база}, {база, В, А, С, база} и т. д.

Если вы имеете в виду "как бы я использовал этот метод?" - не проверено, но что-то вроде:

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) в его книге . Остальная часть кода очень похожа на ваш первоначальный вопрос - просто используйте LINQ, чтобы обеспечить моральный эквивалент + (для массивов).

Answer 2

C # имеет ключевое слово yield, которое, как мне кажется, работает почти так же, как и ваш код на Python, поэтому не должно быть слишком сложно получить в основном прямой перевод.

Однако это рекурсивное решение, поэтому для краткости оно не оптимально. Я лично не понимаю всей математики, но для хороших эффективных математических перестановок вы хотите использовать factoradics . Эта статья должна помочь:
http://msdn.microsoft.com/en-us/library/aa302371.aspx

[Обновление]: другой ответ поднимает хороший вопрос: если вы просто используете перестановки для перемешивания, есть еще лучшие варианты. В частности, Кнут / Фишер-Йейтс shuffle .

Answer 3

Хотя вы не можете перенести его, сохраняя краткость, вы можете подойти довольно близко.

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

Answer 4

Не совсем так, как я должен признать после некоторых комментариев, но приведенный ниже код можно использовать для генерации случайной перестановки конечной последовательности. Это вариация алгоритма Фишера-Йейтса . В примере используется последовательность int, но вы можете использовать любой Enumerable<T>, конечно.

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

Вы заказываете случайное значение (в данном случае Guid), которое по существу переставляет ваш список. Вопрос о том, является ли NewGuid хорошим источником случайности, является спорным, но это элегантное и компактное решение (хотя и для другой проблемы, тогда вопрос был фактически о).

Взято из Джефф Этвуд (Кодирующий ужас) .