使用 LINQ 生成排列

发布于 10-04 21:43 字数 1185 浏览 7 评论 0原文

我有一套必须安排的产品。有 P 个产品,每个产品的索引从 1 到 P。每个产品都可以安排在 0 到 T 的时间段内。我需要构造满足以下约束的产品计划的所有排列:

If p1.Index > p2.Index then p1.Schedule >= p2.Schedule.

我正在努力构造迭代器。我知道当产品数量是已知常量时如何通过 LINQ 执行此操作,但我不确定当产品数量是输入参数时如何生成此查询。

理想情况下,我想使用yield语法来构造这个迭代器。

public class PotentialSchedule()
{
      public PotentialSchedule(int[] schedulePermutation)
      {
             _schedulePermutation = schedulePermutation;
      }
      private readonly int[] _schedulePermutation;
}


private int _numberProducts = ...;
public IEnumerator<PotentialSchedule> GetEnumerator()
{
     int[] permutation = new int[_numberProducts];
     //Generate all permutation combinations here -- how?
     yield return new PotentialSchedule(permutation);
}

编辑:当 _numberProducts = 2 时的示例

public IEnumerable<PotentialSchedule> GetEnumerator()
{
    var query = from p1 in Enumerable.Range(0,T)
                from p2 in Enumerable.Range(p2,T)
                select new { P1 = p1, P2 = p2};

    foreach (var result in query)
          yield return new PotentialSchedule(new int[] { result.P1, result.P2 });
}

I have a set of products that must be scheduled. There are P products each indexed from 1 to P. Each product can be scheduled into a time period 0 to T. I need to construct all permutations of product schedules that satisfy the following constraint:

If p1.Index > p2.Index then p1.Schedule >= p2.Schedule.

I am struggling to construct the iterator. I know how to do this via LINQ when the number of products is a known constant, but am not sure how to generate this query when the number of products is an input parameter.

Ideally I would like to use the yield syntax to construct this iterator.

public class PotentialSchedule()
{
      public PotentialSchedule(int[] schedulePermutation)
      {
             _schedulePermutation = schedulePermutation;
      }
      private readonly int[] _schedulePermutation;
}


private int _numberProducts = ...;
public IEnumerator<PotentialSchedule> GetEnumerator()
{
     int[] permutation = new int[_numberProducts];
     //Generate all permutation combinations here -- how?
     yield return new PotentialSchedule(permutation);
}

EDIT: Example when _numberProducts = 2

public IEnumerable<PotentialSchedule> GetEnumerator()
{
    var query = from p1 in Enumerable.Range(0,T)
                from p2 in Enumerable.Range(p2,T)
                select new { P1 = p1, P2 = p2};

    foreach (var result in query)
          yield return new PotentialSchedule(new int[] { result.P1, result.P2 });
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(8

树深时见影2024-10-11 21:43:37

如果我理解这个问题:您正在寻找长度为 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));
    }
}

它会产生所需的输出:从 0 到 2 绘制长度为 4 的非递减序列。

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 方法中。

If I understand the question: you are looking for all sequences of integers of length P, where each integer in the set is between 0 and T, and the sequence is monotone nondecreasing. Is that correct?

Writing such a program using iterator blocks is straightforward:

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

Which produces the desired output: nondecreasing sequences of length 4 drawn from 0 through 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

Note that the usage of multiply-nested iterators for concatenation is not very efficient, but who cares? You already are generating an exponential number of sequences, so the fact that there's a polynomial inefficiency in the generator is basically irrelevant.

The method M generates all monotone nondecreasing sequences of integers of length p where the integers are between t1 and t2. It does so recursively, using a straightforward recursion. The base case is that there is exactly one sequence of length zero, namely the empty sequence. The recursive case is that in order to compute, say P = 3, t1 = 0, t2 = 2, you compute:

- 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.

And that's the result.

Alternatively, you could use query comprehensions instead of iterator blocks in the main recursive method:

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

That does basically the same thing; it just moves the loops into the SelectMany method.

山川志2024-10-11 21:43:37

注意:比较器完全是可选的。如果您提供一个,排列将按词汇顺序返回。如果不这样做,但原始项目是有序的,它仍然会按词汇顺序枚举。 Ian Griffiths 在 6 年前使用了一个更简单的算法(据我记得,它不进行词汇排序):http://www.interact-sw.co.uk/iangblog/2004/09/16/permuterate

请记住,此代码已有几年历史并且面向 .NET 2.0,因此没有扩展方法等(但修改起来应该很简单)。

它使用Knuth 称为“算法 L” 的算法。它是非递归的、快速的,并在 C++ 标准模板库中使用。

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

Note: the Comparer<T> is entirely optional. If you provide one, the permutations will be returned in lexical order. If you don't, but the original items are ordered, it will still enumerate in lexical order. Ian Griffiths played with this 6 years ago, using a simpler algo (that does not do lexical ordering, as far as I remember): http://www.interact-sw.co.uk/iangblog/2004/09/16/permuterate.

Keep in mind that this code is a few years old and targets .NET 2.0, so no extension methods and the like (but should be trivial to modify).

It uses the algorithm that Knuth calls "Algorithm L". It is non-recursive, fast, and is used in the C++ Standard Template Library.

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();
    }
}
谁的新欢旧爱2024-10-11 21:43:37

我使用这个库进行组合,发现它效果很好。示例程序有点令人困惑,但文章解释了使用代码需要什么。

  • 使用 C# 泛型进行排列、组合和变体
  • 作者:Adrian Akison | 2008 年 5 月 23 日
  • 讨论组合集合的六种主要类型,并提供示例和计数公式。使用基于 C# 泛型的类集进行扩展,用于枚举每个元集合。
  • 插入自 http://www.codeproject.com/KB/recipes/Combinatorics.aspx

I used this library for the combinations and found it works well. The sample program is a little confusing, but the article explains what is needed to use the code.

  • Permutations, Combinations, and Variations using C# Generics
  • By Adrian Akison | 23 May 2008
  • Discusses the six major types of combinatorial collections, with examples and formulas for counting. Expands with a C# Generics-based set of classes for enumerating each meta-collection.
  • Inserted from http://www.codeproject.com/KB/recipes/Combinatorics.aspx
音栖息无2024-10-11 21:43:37

这是 C# 7 的简单排列扩展方法(值元组和内部方法)。它源自@AndrasVaas的答案,但仅使用单一级别的惰性(防止由于随着时间的推移而改变项目而导致的错误),失去了 IComparer 功能(我不需要它),并且长度要短一些。

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

Here's a simple permutation extension method for C# 7 (value tuples and inner methods). It's derived from @AndrasVaas's answer, but uses only a single level of laziness (preventing bugs due to mutating items over time), loses the IComparer feature (I didn't need it), and is a fair bit shorter.

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);
        }
    }
}
素罗衫2024-10-11 21:43:37
  1. 创建另一个长度为 2^n 的数组,其中 n 是从 0 到 2^n 的二进制产品计数
  2. ,并用每个计数填充数组。例如,如果 n=3
    该数组将如下所示:

000 001 010 011 100 101 110 111

  1. 循环遍历二进制数组并找到每个数字中的数字,然后将具有相同索引的乘积相加:
 对于 ar{ 中的每个二进制数
   对于 i = 0 到 n-1{
     如果二进制数(i) = 1
       排列.add(产品(i))
   }
  permunations.add(排列) 
}

例子:
如果 binaryNumber= 001 则排列 1 = 产品 1
如果 binaryNumber= 101 则排列 1 = 产品 3,产品 1

  1. create another array of length 2^n where n is the number of products
  2. count in binary from 0 to 2^n and fill in the array with each count. for example if n=3
    the array will look like this :

000 001 010 011 100 101 110 111

  1. loop through the binary array and find the ones in each number then add the product with the same index:
 for each binaryNumber in ar{
   for i = 0 to n-1{
     if binaryNumber(i) = 1
       permunation.add(products(i))
   }
  permunations.add(permutation) 
}

example:
if binaryNumber= 001 then permunation1 = product1
if binaryNumber= 101 then permunation1 = product3,product1

墨离汐2024-10-11 21:43:37

今天我偶然发现了这一点,并认为我可以分享我的实现。

对于 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)));
    }

Today I stumbled upon this and figured I could share my implementation.

For all integers between N and M you have to make an array first:

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

and run it through 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)));
    }
简单2024-10-11 21:43:37

Lippert先生的答案的输出可以看作是4个槽中0和2之间元素的所有可能分布。
例如
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();
  }
}

The output from the answer of Mr Lippert can be seen as all the possible distributions of elements among 0 and 2 in 4 slots.
For instance
0 3 1
reads as "no 0, three 1 and one 2"
This is nowhere near as elegant as the answer of Mr Lippert, but at least not less efficient

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();
  }
}
南汐寒笙箫2024-10-11 21:43:37
    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);
        }
    }
    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);
        }
    }
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文