c# - 列表中的每个项目组合

问题描述

我的问题如下：对于每种类型的产品，我都有一个 N 类型的产品列表，我可以有一个最小值和一个最大值。

举个例子：

产品1（最小：1，最大：2）
产品 2（最小：2，最大：3）
产品3（最小：1，最大：2）

谁会给出这样的清单：

[
  {Product1}, 
  {Product1, Product1}, 
  {Product2, Product2}, 
  {Product2, Product2, Product2}, 
  {Product3}, 
  {Product3, Product3}
]

我现在需要对可能的输出进行所有组合，以满足所有产品的约束。

获取第一个列表并运行组合函数很简单。我取列表中的第一项，检查它是否可以与列表中的其他项目合并，如果可以，我将其合并，否则什么都不做。运行完成后，我会递归地调用该函数，并再次计算新列表，直到我没有剩余的有效组合。

例如第一次运行会做这样的事情：

产品 1、产品 1、产品 1（无效）
产品 1、产品 2、产品 2（有效）
产品 1、产品 2、产品 2、产品 2（有效）
...

第二次运行：

产品 1、产品 1、产品 1、产品 1、产品 2、产品 2（无效）
产品 1、产品 2、产品 2、产品 3（有效）
...

使用这个解决方案，我可以正确计算我所有可能的产品组合，但是大量可能性的性能并不是那么好，我知道我的解决方案涉及很多无效组合的循环，以获得大约 1000 个有效组合我测试周围其中 400000 个。

有没有办法改进算法来限制测试组合的数量？或者您是否看到了另一种完全不同的方式？

标签： c#algorithm

解决方案

这是我对如何迭代具有不同长度的列表以查找所有排列的问题给出的答案的变体？，它本身是 Michael Liu 在IEnumerable and Recursion using yield return中给出的答案的变体

它通过创建一个枚举器来工作，该枚举器在 foreach 循环中返回所有允许的组合字符串的列表。

使用 Enumerator 就像这样简单：

using System;
using System.Collections.Generic;

namespace SO69209314_list_combinations
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Product> productList = new List<Product>()
            {
                new Product("Product1", 1,2),
                new Product("Product2", 2,3),
                new Product("Product3", 1,2),
            };
            ProductPermuter permuter = new ProductPermuter(productList);
            int i = 0;
            foreach (IEnumerable<string> list in permuter)
            {
                Console.WriteLine("{0}:{1}", i, string.Join(",", list));
                i++;
            }
            Console.ReadKey();
        }
    }
}

这是 Enumerator（包括存储字符串以及最小和最大限制的 Product 类）。它的工作原理是跟踪每种类型的产品数量（在每个级别），迭代每个产品的数量。当一个产品完成时，它会重置其迭代器并再次迭代前一个产品，等等，直到所有级别都完成。所以它最终会返回所有允许的组合。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SO69209314_list_combinations

{
    public class Product : IEnumerable<int>
    {
        public Product(string name, int min, int max)
        {
            this.name = name ?? throw new ArgumentNullException(nameof(name));
            if ((min > max) || (min < 0) || (max < 0)) { throw new InvalidOperationException("Bad min or max"); }
            this.min = min;
            this.max = max;
        }

        public string name { get; private set; }
        public int min { get; private set; }
        public int max { get; private set; }

        public IEnumerator<int> GetEnumerator()
        {
            for (int i = min; i <= max; i++)
            {
                yield return i;
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }

    public class ProductPermuter : IEnumerable<IEnumerable<string>>
    {
        private int count;
        private Product[] products;

        public ProductPermuter(IEnumerable<Product> products_)
        {
            if (object.ReferenceEquals(products_, null))
            {
                throw new ArgumentNullException(nameof(products_));
            }
            products = products_.ToArray();
            count = products.Length;
            for (int i = 0; i < count; i++)
            {
                if (object.ReferenceEquals(products[i], null))
                {
                    throw new NullReferenceException(string.Format("{0}[{1}] is null.", nameof(products_), i));
                }
            }
        }

        // A variant of Michael Liu's answer in StackOverflow
        // https://stackoverflow.com/questions/2055927/ienumerable-and-recursion-using-yield-return
        public IEnumerator<IEnumerable<string>> GetEnumerator()
        {
            IEnumerable<string>[] currentList = new IEnumerable<string>[count];
            int level = 0;
            var enumerators = new Stack<IEnumerator<int>>();
            IEnumerator<int> enumerator = products[level].GetEnumerator();
            try
            {
                while (true)
                {
                    if (enumerator.MoveNext())
                    {
                        int n = enumerator.Current;
                        currentList[level] = Enumerable.Repeat(products[level].name, n).ToList();
                        level++;
                        if (level >= count)
                        {
                            level--;
                            List<string> list = new List<string>();
                            for (int i = 0; i < count; i++)
                            {
                                list.AddRange(currentList[i]);
                            }
                            yield return list;
                        }
                        else
                        {
                            enumerators.Push(enumerator);
                            enumerator = products[level].GetEnumerator();
                        }
                    }
                    else
                    {
                        if (level == 0)
                        {
                            yield break;
                        }
                        else
                        {
                            enumerator.Dispose();
                            enumerator = enumerators.Pop();
                            level--;
                        }
                    }
                }
            }
            finally
            {
                // Clean up in case of an exception.
                enumerator?.Dispose();
                while (enumerators.Count > 0)
                {
                    enumerator = enumerators.Pop();
                    enumerator.Dispose();
                }
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }
}

这是输出：

0:Product1,Product2,Product2,Product3
1:Product1,Product2,Product2,Product3,Product3
2:Product1,Product2,Product2,Product2,Product3
3:Product1,Product2,Product2,Product2,Product3,Product3
4:Product1,Product1,Product2,Product2,Product3
5:Product1,Product1,Product2,Product2,Product3,Product3
6:Product1,Product1,Product2,Product2,Product2,Product3
7:Product1,Product1,Product2,Product2,Product2,Product3,Product3

如果将输入修改为 Product 3 的 0

...
new Product("Product3", 0, 2),
...

那么输出是

0:Product1,Product2,Product2
1:Product1,Product2,Product2,Product3
2:Product1,Product2,Product2,Product3,Product3
3:Product1,Product2,Product2,Product2
4:Product1,Product2,Product2,Product2,Product3
5:Product1,Product2,Product2,Product2,Product3,Product3
6:Product1,Product1,Product2,Product2
7:Product1,Product1,Product2,Product2,Product3
8:Product1,Product1,Product2,Product2,Product3,Product3
9:Product1,Product1,Product2,Product2,Product2
10:Product1,Product1,Product2,Product2,Product2,Product3
11:Product1,Product1,Product2,Product2,Product2,Product3,Product3

如果总是允许零个元素，即使 min 是 1 或 2，那么 Product 的 Enumerator 可以更改如下：

        public IEnumerator<int> GetEnumerator()
        {
            // 0 is always allowed
            yield return 0;
            int minForLoop = Math.Max(1, min);
            for (int i = minForLoop; i <= max; i++)
            {
                yield return i;
            }
        }

输出变为：

0:
1:Product3
2:Product3,Product3
3:Product2,Product2
4:Product2,Product2,Product3
5:Product2,Product2,Product3,Product3
6:Product2,Product2,Product2
7:Product2,Product2,Product2,Product3
8:Product2,Product2,Product2,Product3,Product3
9:Product1
10:Product1,Product3
11:Product1,Product3,Product3
12:Product1,Product2,Product2
13:Product1,Product2,Product2,Product3
14:Product1,Product2,Product2,Product3,Product3
15:Product1,Product2,Product2,Product2
16:Product1,Product2,Product2,Product2,Product3
17:Product1,Product2,Product2,Product2,Product3,Product3
18:Product1,Product1
19:Product1,Product1,Product3
20:Product1,Product1,Product3,Product3
21:Product1,Product1,Product2,Product2
22:Product1,Product1,Product2,Product2,Product3
23:Product1,Product1,Product2,Product2,Product3,Product3
24:Product1,Product1,Product2,Product2,Product2
25:Product1,Product1,Product2,Product2,Product2,Product3
26:Product1,Product1,Product2,Product2,Product2,Product3,Product3

c# - 列表中的每个项目组合

问题描述

解决方案

推荐阅读