Создание перестановок с использованием LINQ

Ответ 1

Если я понимаю вопрос: вы ищете все последовательности целых чисел длины P, где каждое целое число в множестве находится между 0 и T, а последовательность монотонна неубывающая. Это правильно?

Написание такой программы с использованием блоков итератора является простым:

using System;
using System.Collections.Generic;
using System.Linq;

static class Program
{
    static IEnumerable<T> Prepend<T>(T first, IEnumerable<T> rest)
    {
        yield return first;
        foreach (var item in rest)
            yield return item;
    }

    static IEnumerable<IEnumerable<int>> M(int p, int t1, int t2)
    {
        if (p == 0)
            yield return Enumerable.Empty<int>();
        else
            for (int first = t1; first <= t2; ++first)
                foreach (var rest in M(p - 1, first, t2))
                    yield return Prepend(first, rest);
    }

    public static void Main()
    {
        foreach (var sequence in M(4, 0, 2))
            Console.WriteLine(string.Join(", ", sequence));
    }
}

Что дает желаемый результат: неубывающие последовательности длины 4, взятые из 0 до 2.

0, 0, 0, 0
0, 0, 0, 1
0, 0, 0, 2
0, 0, 1, 1
0, 0, 1, 2
0, 0, 2, 2
0, 1, 1, 1
0, 1, 1, 2
0, 1, 2, 2
0, 2, 2, 2
1, 1, 1, 1
1, 1, 1, 2
1, 1, 2, 2
1, 2, 2, 2
2, 2, 2, 2

Обратите внимание, что использование многопоточных итераторов для конкатенации не очень эффективно, но кому это интересно? Вы уже генерируете число последовательностей экспоненциального, поэтому факт отсутствия в генераторе многочлена не имеет значения.

Метод M генерирует все монотонные неубывающие последовательности целых чисел p, где целые числа находятся между t1 и t2. Он делает это рекурсивно, используя прямую рекурсию. Основным случаем является то, что существует ровно одна последовательность нулевой длины, а именно пустая последовательность. Рекурсивный случай состоит в том, что для вычисления, скажем, P = 3, t1 = 0, t2 = 2, вы вычисляете:

- all sequences starting with 0 followed by sequences of length 2 drawn from 0 to 2.
- all sequences starting with 1 followed by sequences of length 2 drawn from 1 to 2.
- all sequences starting with 2 followed by sequences of length 2 drawn from 2 to 2.

И что результат.

В качестве альтернативы вы можете использовать понимание запросов вместо блоков итератора в основном рекурсивном методе:

static IEnumerable<T> Singleton<T>(T first)
{
    yield return first;
}

static IEnumerable<IEnumerable<int>> M(int p, int t1, int t2)
{
    return p == 0 ?

        Singleton(Enumerable.Empty<int>()) : 

        from first in Enumerable.Range(t1, t2 - t1 + 1)
        from rest in M(p - 1, first, t2)
        select Prepend(first, rest);
}

Это в основном то же самое; он просто перемещает петли в метод SelectMany.

Ответ 2

Примечание: Comparer <T> полностью необязательно. Если вы его предоставите, перестановки будут возвращены в лексическом порядке. Если вы этого не сделаете, но исходные элементы упорядочены, он все равно будет перечисляться в лексическом порядке. Иан Гриффитс играл с этим 6 лет назад, используя более простой алгоритм (который, насколько я помню, не выполняет лексическое упорядочение): http://www.interact-sw.co.uk/iangblog/2004/09/16/permuterate.

Имейте в виду, что этот код составляет несколько лет, и он нацелен на .NET 2.0, поэтому никакие методы расширения и тому подобное (но должны быть тривиальными для изменения).

Он использует алгоритм, который Кнут называет "Алгоритм L" . Он нерекурсивный, быстрый и используется в стандартной библиотеке шаблонов С++.

static partial class Permutation
{
    /// <summary>
    /// Generates permutations.
    /// </summary>
    /// <typeparam name="T">Type of items to permute.</typeparam>
    /// <param name="items">Array of items. Will not be modified.</param>
    /// <param name="comparer">Optional comparer to use.
    /// If a <paramref name="comparer"/> is supplied, 
    /// permutations will be ordered according to the 
    /// <paramref name="comparer"/>
    /// </param>
    /// <returns>Permutations of input items.</returns>
    public static IEnumerable<IEnumerable<T>> Permute<T>(T[] items, IComparer<T> comparer)
    {
        int length = items.Length;
        IntPair[] transform = new IntPair[length];
        if (comparer == null)
        {
            //No comparer. Start with an identity transform.
            for (int i = 0; i < length; i++)
            {
                transform[i] = new IntPair(i, i);
            };
        }
        else
        {
            //Figure out where we are in the sequence of all permutations
            int[] initialorder = new int[length];
            for (int i = 0; i < length; i++)
            {
                initialorder[i] = i;
            }
            Array.Sort(initialorder, delegate(int x, int y)
            {
                return comparer.Compare(items[x], items[y]);
            });
            for (int i = 0; i < length; i++)
            {
                transform[i] = new IntPair(initialorder[i], i);
            }
            //Handle duplicates
            for (int i = 1; i < length; i++)
            {
                if (comparer.Compare(
                    items[transform[i - 1].Second], 
                    items[transform[i].Second]) == 0)
                {
                    transform[i].First = transform[i - 1].First;
                }
            }
        }

        yield return ApplyTransform(items, transform);

        while (true)
        {
            //Ref: E. W. Dijkstra, A Discipline of Programming, Prentice-Hall, 1997
            //Find the largest partition from the back that is in decreasing (non-icreasing) order
            int decreasingpart = length - 2;
            for (;decreasingpart >= 0 && 
                transform[decreasingpart].First >= transform[decreasingpart + 1].First;
                --decreasingpart) ;
            //The whole sequence is in decreasing order, finished
            if (decreasingpart < 0) yield break;
            //Find the smallest element in the decreasing partition that is 
            //greater than (or equal to) the item in front of the decreasing partition
            int greater = length - 1;
            for (;greater > decreasingpart && 
                transform[decreasingpart].First >= transform[greater].First; 
                greater--) ;
            //Swap the two
            Swap(ref transform[decreasingpart], ref transform[greater]);
            //Reverse the decreasing partition
            Array.Reverse(transform, decreasingpart + 1, length - decreasingpart - 1);
            yield return ApplyTransform(items, transform);
        }
    }

    #region Overloads

    public static IEnumerable<IEnumerable<T>> Permute<T>(T[] items)
    {
        return Permute(items, null);
    }

    public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> items, IComparer<T> comparer)
    {
        List<T> list = new List<T>(items);
        return Permute(list.ToArray(), comparer);
    }

    public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> items)
    {
        return Permute(items, null);
    }

    #endregion Overloads

    #region Utility

    public static IEnumerable<T> ApplyTransform<T>(
        T[] items, 
        IntPair[] transform)
    {
        for (int i = 0; i < transform.Length; i++)
        {
            yield return items[transform[i].Second];
        }
    }

    public static void Swap<T>(ref T x, ref T y)
    {
        T tmp = x;
        x = y;
        y = tmp;
    }

    public struct IntPair
    {
        public IntPair(int first, int second)
        {
            this.First = first;
            this.Second = second;
        }
        public int First;
        public int Second;
    }

    #endregion
}

class Program
{

    static void Main()
    {
        int pans = 0;
        int[] digits = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        Stopwatch sw = new Stopwatch();
        sw.Start();
        foreach (var p in Permutation.Permute(digits))
        {
            pans++;
            if (pans == 720) break;
        }
        sw.Stop();
        Console.WriteLine("{0}pcs, {1}ms", pans, sw.ElapsedMilliseconds);
        Console.ReadKey();
    }
}

Ответ 3

Я использовал эту библиотеку для комбинаций и нашел, что она работает хорошо. Пример программы немного запутан, но в статье объясняется, что необходимо для использования кода.

• Перестановки, комбинации и вариации с использованием общих возможностей С#
• Адриан Акисон | 23 мая 2008 г.
• Обсуждает шесть основных типов комбинаторных коллекций с примерами и формулами для подсчета. Расширяется с помощью набора классов на основе С# Generics для перечисления каждой мета-коллекции.
• Вставка из http://www.codeproject.com/KB/recipes/Combinatorics.aspx

Ответ 4

• создать еще один массив длины 2 ^ n, где n - количество продуктов
• рассчитывать в двоичном формате от 0 до 2 ^ n и заполнять массив каждым количеством. например, если n = 3 массив будет выглядеть следующим образом:

000 001 010 011 100 101 110 111

• пройдите через двоичный массив и найдите их в каждом номере, затем добавьте продукт с тем же индексом:

 for each binaryNumber in ar{
   for i = 0 to n-1{
     if binaryNumber(i) = 1
       permunation.add(products(i))
   }
  permunations.add(permutation) 
}

Пример: если binaryNumber = 001, то permunation1 = product1 если binaryNumber = 101, то permunation1 = product3, product1

Ответ 5

Здесь используется простой метод расширения подстановок для С# 7 (значения кортежей и внутренние методы). Он получен из @AndrasVaas answer, но использует только один уровень лень (предотвращая ошибки из-за мутирующих элементов с течением времени), теряет функцию IComparer (я didn ' это нужно), и это будет немного короче.

public static class PermutationExtensions
{
    /// <summary>
    /// Generates permutations.
    /// </summary>
    /// <typeparam name="T">Type of items to permute.</typeparam>
    /// <param name="items">Array of items. Will not be modified.</param>
    /// <returns>Permutations of input items.</returns>
    public static IEnumerable<T[]> Permute<T>(this T[] items)
    {
        T[] ApplyTransform(T[] values, (int First, int Second)[] tx)
        {
            var permutation = new T[values.Length];
            for (var i = 0; i < tx.Length; i++)
                permutation[i] = values[tx[i].Second];
            return permutation;
        }

        void Swap<U>(ref U x, ref U y)
        {
            var tmp = x;
            x = y;
            y = tmp;
        }

        var length = items.Length;

        // Build identity transform
        var transform = new(int First, int Second)[length];
        for (var i = 0; i < length; i++)
            transform[i] = (i, i);

        yield return ApplyTransform(items, transform);

        while (true)
        {
            // Ref: E. W. Dijkstra, A Discipline of Programming, Prentice-Hall, 1997
            // Find the largest partition from the back that is in decreasing (non-increasing) order
            var decreasingpart = length - 2;
            while (decreasingpart >= 0 && transform[decreasingpart].First >= transform[decreasingpart + 1].First)
                --decreasingpart;

            // The whole sequence is in decreasing order, finished
            if (decreasingpart < 0)
                yield break;

            // Find the smallest element in the decreasing partition that is
            // greater than (or equal to) the item in front of the decreasing partition
            var greater = length - 1;
            while (greater > decreasingpart && transform[decreasingpart].First >= transform[greater].First)
                greater--;

            // Swap the two
            Swap(ref transform[decreasingpart], ref transform[greater]);

            // Reverse the decreasing partition
            Array.Reverse(transform, decreasingpart + 1, length - decreasingpart - 1);

            yield return ApplyTransform(items, transform);
        }
    }
}

Ответ 6

Сегодня я наткнулся на это и подумал, что могу поделиться своей реализацией.

Для всех целых чисел между N и M сначала необходимо создать массив:

IEnumerable<int> Range(int n, int m) {
    for(var i = n; i < m; ++i) {
        yield return i;
    }
}

и запустите его через Permutations(Range(1, 10)):

    enum PermutationsOption {
        None,
        SkipEmpty,
        SkipNotDistinct
    }

    private IEnumerable<IEnumerable<T>> Permutations<T>(IEnumerable<T> elements, PermutationsOption option = PermutationsOption.None, IEqualityComparer<T> equalityComparer = default(IEqualityComparer<T>)) {
        var elementsList = new List<IEnumerable<T>>();
        var elementsIndex = 0;
        var elementsCount = elements.Count();
        var elementsLength = Math.Pow(elementsCount + 1, elementsCount);

        if (option.HasFlag(PermutationsOption.SkipEmpty)) {
            elementsIndex = 1;
        }

        if (elements.Count() > 0) {
            do {
                var elementStack = new Stack<T>();

                for (var i = 0; i < elementsCount; ++i) {
                    var ind = (int)(elementsIndex / Math.Pow(elementsCount + 1, i) % (elementsCount + 1));
                    if (ind == 0) {
                        continue;
                    }
                    elementStack.Push(elements.ElementAt(ind - 1));
                }

                var elementsCopy = elementStack.ToArray() as IEnumerable<T>;

                if (option.HasFlag(PermutationsOption.SkipNotDistinct)) {
                    elementsCopy = elementsCopy.Distinct();
                    elementsCopy = elementsCopy.ToArray();

                    if (elementsList.Any(p => CompareItemEquality(p, elementsCopy, equalityComparer))) {
                        continue;
                    }
                }

                elementsList.Add(elementsCopy);
            } while (++elementsIndex < elementsLength);
        }

        return elementsList.ToArray();
    }

    private bool CompareItemEquality<T>(IEnumerable<T> elements1, IEnumerable<T> elements2, IEqualityComparer<T> equalityComparer = default(IEqualityComparer<T>)) {
        if (equalityComparer == null) {
            equalityComparer = EqualityComparer<T>.Default;
        }

        return (elements2.Count() == elements2.Count()) && (elements2.All(p => elements1.Contains(p, equalityComparer)));
    }

Ответ 7

Результат ответа г-на Липперта можно рассматривать как все возможные распределения элементов среди 0 и 2 в 4 слотах.
Например
0 3 1
читается как "нет 0, три 1 и один 2"
Это нигде не столь изящно, как ответ г-на Липперта, но по крайней мере не менее эффективный

public static void Main()
{
  var distributions = Distributions(4, 3);
  PrintSequences(distributions);
}

/// <summary>
/// Entry point for the other recursive overload
/// </summary>
/// <param name="length">Number of elements in the output</param>
/// <param name="range">Number of distinct values elements can take</param>
/// <returns></returns>
static List<int[]> Distributions(int length, int range)
{
  var distribution = new int[range];
  var distributions = new List<int[]>();
  Distributions(0, length, distribution, 0, distributions);
  distributions.Reverse();
  return distributions;
}

/// <summary>
/// Recursive methode. Not to be called directly, only from other overload
/// </summary>
/// <param name="index">Value of the (possibly) last added element</param>
/// <param name="length">Number of elements in the output</param>
/// <param name="distribution">Distribution among element distinct values</param>
/// <param name="sum">Exit condition of the recursion. Incremented if element added from parent call</param>
/// <param name="distributions">All possible distributions</param>
static void Distributions(int index,
                          int length,
                          int[] distribution,
                          int sum,
                          List<int[]> distributions)
{
  //Uncomment for exactness check
  //System.Diagnostics.Debug.Assert(distribution.Sum() == sum);
  if (sum == length)
  {
    distributions.Add(distribution.Reverse().ToArray());

    for (; index < distribution.Length; index++)
    {
      sum -= distribution[index];
      distribution[index] = 0;
    }
    return;
  }
  if (index < distribution.Length)
  {
    Distributions(index + 1, length, distribution, sum, distributions);
    distribution[index]++;
    Distributions(index, length, distribution, ++sum, distributions);
  }
}

static void PrintSequences(List<int[]> distributions)
{
  for (int i = 0; i < distributions.Count; i++)
  {
    for (int j = distributions[i].Length - 1; j >= 0; j--)
      for (int k = 0; k < distributions[i][j]; k++)
        Console.Write("{0:D1} ", distributions[i].Length - 1 - j);
    Console.WriteLine();
  }
}

Ответ 8

    public static IList<IList<T>> Permutation<T>(ImmutableList<ImmutableList<T>> dimensions)
    {
        IList<IList<T>> result = new List<IList<T>>();
        Step(ImmutableList.Create<T>(), dimensions, result);
        return result;
    }

    private static void Step<T>(ImmutableList<T> previous, 
        ImmutableList<ImmutableList<T>> rest, 
        IList<IList<T>> result)
    {
        if (rest.IsEmpty)
        {
            result.Add(previous);
            return;
        }

        var first = rest[0];
        rest = rest.RemoveAt(0);

        foreach (var label in first)
        {
            Step(previous.Add(label), rest, result);
        }
    }