Every combination of items in lists-CodePudding

My problem is the following : I have a list of N type of product for each type of product I can have a min and a max.

For exemple :

Product1 (min: 1, max: 2)
Product2 (min: 2, max: 3)
Product3 (min: 1, max: 2)

Whould give a list like this :

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

I now need to do all the combinaison of the possible outputs that will satisfy the constraints of all the products.

It is straightforward to get the first list and to run the combination function. I take the first item in the list, check if it can be merge with the other items in the list, if yes I merge it otherwise nothing is done. Once the run is done I call the function recursively with the new list to be computed again until I have no valid combination left.

For exemple First run would do something like this :

Product1, Product1, Product1 (invalid)
Product1, Product2, Product2 (valid)
Product1, Product2, Product2, Product2 (valid)
...

Second run :

Product1, Product1, Product1, Product1, Product2, Product2 (invalid)
Product1, Product2, Product2, Product3 (valid)
...

With this solution I can correctly compute all my possible combination of products but the perfs for a large amount of possibilities are not that great, I know that my solution involve a lot of loops for invalid combination, to get around 1000 valid combination I test around 400000 of them.

Is there a way to improve the algorithm to limit the number of test combination ? Or do you see an other way of doing it completly differently ?

CodePudding user response：

I think something like this is what you're looking for. A recursive Combine<T>() method that combines your sets of allowed products.

(Note: Because each set can be empty we also have to include an empty array for each input combination, hence the use of none below.)

using System;
using System.Linq;

namespace Demo
{
    static class Program
    {
        public static void Main()
        {
            var none = Array.Empty<string>();

            string[][][] sets = 
            {
                new[] {none, new[] {"Product1"},             new[] {"Product1", "Product1"}},
                new[] {none, new[] {"Product2", "Product2"}, new[] {"Product2", "Product2", "Product2"}},
                new[] {none, new[] {"Product3"},             new[] {"Product3", "Product3"}},
            };

            Combine(sets, print);
        }

        static void print(string[][] strings)
        {
            bool emptySet = true; // Exactly one combination of products will contain zero of each; this will detect it.

            foreach (var set in strings.Where(set => set.Length > 0))
            {
                emptySet = false;
                Console.Write(string.Join(", ", set)   "; ");
            }

            if (!emptySet) // No need to write a new line if there were zero of each product.
                Console.WriteLine();
        }

        public static void Combine<T>(T[][] sets, Action<T[]> output)
        {
            combine(sets, 0, new T[sets.Length], output);
        }

        static void combine<T>(T[][] sets, int set, T[] combination, Action<T[]> output)
        {
            for (int i = 0; i < sets[set].Length;   i)
            {
                combination[set] = sets[set][i];

                if (set < (sets.Length - 1))
                    combine(sets, set   1, combination, output);
                else 
                    output(combination);
            }
        }
    }
}

Output is:

Product3;
Product3, Product3;
Product2, Product2;
Product2, Product2; Product3;
Product2, Product2; Product3, Product3;
Product2, Product2, Product2;
Product2, Product2, Product2; Product3;
Product2, Product2, Product2; Product3, Product3;
Product1;
Product1; Product3;
Product1; Product3, Product3;
Product1; Product2, Product2;
Product1; Product2, Product2; Product3;
Product1; Product2, Product2; Product3, Product3;
Product1; Product2, Product2, Product2;
Product1; Product2, Product2, Product2; Product3;
Product1; Product2, Product2, Product2; Product3, Product3;
Product1, Product1;
Product1, Product1; Product3;
Product1, Product1; Product3, Product3;
Product1, Product1; Product2, Product2;
Product1, Product1; Product2, Product2; Product3;
Product1, Product1; Product2, Product2; Product3, Product3;
Product1, Product1; Product2, Product2, Product2;
Product1, Product1; Product2, Product2, Product2; Product3;
Product1, Product1; Product2, Product2, Product2; Product3, Product3;

Try it on .net Fiddle

CodePudding user response：

This is a variation of an answer I gave to question How to iterate lists with different lengths to find all permutations?, which itself was a variant of on an answer given by Michael Liu's in IEnumerable and Recursion using yield return

It works by creating an Enumerator which returns lists of all the allowed combinations strings in a foreach loop.

Using the Enumerator is as easy as this:

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

This is the Enumerator (including a Product class storing the string and min and max limits). It works by keeping track of the number of Products of each type (at each level), iterating the number of each product. When a product is finished, it resets its iterator and iterates the previous product again, etc. until all levels are finished. So it will eventually return all the allowed combinations.

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

This is the output:

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

If you modify the input to have 0 of Product 3

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

then the output is

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

If zero elements are always allowed, even if min is 1 or 2, then the Enumerator of Product can be changed as follows:

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

and the output becomes:

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