Find unique permutations for object

Question

I have a list of products that have an ID and a Quantity, and I need to find a list of combinations of products that will fill a certain quantity.

E.g.

ProductID | Quantity
1         | 5
2         | 5
3         | 8
4         | 15

If I require a quantity of 15 then I want to get a list with the following combinations:

Products: {1, 2, 3}, {1, 3, 2}, {1, 2, 4}, {1, 3, 4}, {1, 4}
          {2, 1, 3}, {2, 1, 4}, {2, 3, 1}, {2, 3, 4}, {2, 4}
          {3, 1, 2}, {3, 1, 4}, {3, 2, 1}, {3, 2, 4}, {3, 4}
          {4}

It's almost a permutation, but it's filtered out entries that sum up to more than what is required. I need to stop taking further items, if at any point, the current total sum of values goes beyond 15. Doing this way, if I had all permutations then I would have 24 results, but I only have 16.

E.g. if I take product 4 then I don't need to combine it with anything to make 15. Similarly, if I take product 1 then take product 4, I don't need to pick up anymore item since the sum is already beyond 15 (5 + 15 = 20).

I was able to get the code working by getting all Permutations (e.g. here) and then filtering that down to the ones I care about, however once you start getting a large number of products (e.g. 30) then you end up with 4.3 Billion combinations which causes out of memory exceptions.

How can I create only the required permutations in C#?

Answer 1

looks like only two rule:
1. elements picked are distinct.
2. sum of picked elements' qty must greater then goal, not just only equal to goal.

My example add some interface for sorting. Every kind of combination that can reach goal are listed. But I trying to list in unique form for reading. You can to oringinal expand job within each combination.

PS. for order purpose I add IComparable, not very important.

class Product: IComparable
{
    public int ID { get; set; }
    public uint Qty { get; set; }

    public int CompareTo(object obj)
    {
        if (obj is Product)
            return this.ID.CompareTo(((Product)obj).ID);
        else
            return -1;
    }

    public override string ToString()
    {
        return string.Format("Product: {0}", this.ID);
    }
}

class Combination : List<Product>, IComparable
{
    public int Goal { get; private set; }

    public bool IsCompleted
    {
        get
        {
            return this.Sum(product => product.Qty) >= Goal;
        }
    }

    public Combination(int goal)
    {
        Goal = goal;
    }

    public Combination(int goal, params Product[] firstProducts)
        : this(goal)
    {
        AddRange(firstProducts);
    }

    public Combination(Combination inheritFrom)
        : base(inheritFrom)
    {
        Goal = inheritFrom.Goal;
    }

    public Combination(Combination inheritFrom, Product firstProduct)
        : this(inheritFrom)
    {
        Add(firstProduct);
    }

    public int CompareTo(object obj)
    {
        if (obj is Combination)
        {
            var destCombination = (Combination)obj;
            var checkIndex = 0;
            while (true)
            {
                if (destCombination.Count - 1 < checkIndex && this.Count - 1 < checkIndex)
                    return 0;
                else if (destCombination.Count - 1 < checkIndex)
                    return -1;
                else if (this.Count - 1 < checkIndex)
                    return 1;
                else
                {
                    var result = this[checkIndex].CompareTo(destCombination[checkIndex]);
                    if (result == 0)
                        checkIndex++;
                    else
                        return result;
                }
            }
        }
        else
            return this.CompareTo(obj);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            return this.Select((item, idx) => item.ID * (10 ^ idx)).Sum();
        }
    }

    public override bool Equals(object obj)
    {
        if (obj is Combination)
            return ((Combination)obj).GetHashCode() == this.GetHashCode();
        else
            return base.Equals(obj);
    }
}

the testing part provide product list and the goal.

public static void Test()
    {
        var goal = 25;
        var products = new[]
        {
            new Product() { ID = 1, Qty = 5 },
            new Product() { ID = 2, Qty = 5 },
            new Product() { ID = 3, Qty = 8 },
            new Product() { ID = 4, Qty = 15 },
            new Product() { ID = 5, Qty = 17 },
            new Product() { ID = 6, Qty = 1 },
            new Product() { ID = 7, Qty = 4 },
            new Product() { ID = 8, Qty = 6 },
        };

        var orderedProducts = products.OrderBy(prod => prod.ID);

        //one un-completed combination, can bring back muliple combination..
        //that include completed or next-staged-uncompleted combinations
        Func<Combination, IEnumerable<Combination>> job = null;

        job = (set) =>
        {
            if (set.IsCompleted)
                return new[] { set }.ToList();
            else
            {
                return orderedProducts
                    .Where(product => set.Contains(product) == false && product.ID >= set.Last().ID)
                    .Select(product => new Combination(set, product))
                    .SelectMany(combination => job(combination));
            }
        };

        var allPossibility = orderedProducts
            .Select(product => new Combination(goal, product))
            .SelectMany(combination => job(combination))
            .Where(combination => combination.IsCompleted)
            .Select(combination => new Combination(goal, combination.OrderBy(product => product.ID).ToArray()))
            .OrderBy(item => item)
            .ToList();

        foreach (var completedCombination in allPossibility)
        {
            Console.WriteLine(string.Join<int>(", ", completedCombination.Select(prod => prod.ID).ToArray()));
        }
        Console.ReadKey();
    }

Answer 2

This probably isn't the most efficient answer, but it does give the right answer:

void Main()
{
    List<Product> products = new List<Product> {    new Product { ProductID = 1, Quantity = 5 },
                                                    new Product { ProductID = 2, Quantity = 5 },
                                                    new Product { ProductID = 3, Quantity = 8 },
                                                    new Product { ProductID = 4, Quantity = 15 },
                                                    };


    decimal requiredQuantity = 15;
    if (requiredQuantity < products.Sum(p => p.Quantity))
    {
        var output = Permutations(products, requiredQuantity);

        output.Dump();
    }
    else
    {
        products.Dump();
    }
}

// Define other methods and classes here
private List<Queue<Product>> Permutations(List<Product> list, decimal requiredValue, Stack<Product> currentList = null)
{
    if (currentList == null)
    {
        currentList = new Stack<Product>();
    }
    List<Queue<Product>> returnList = new List<System.Collections.Generic.Queue<Product>>();

    foreach (Product product in list.Except(currentList))
    {
        currentList.Push(product);
        decimal currentTotal = currentList.Sum(p => p.Quantity);
        if (currentTotal >= requiredValue)
        {
            //Stop Looking. You're Done! Copy the contents out of the stack into a queue to process later. Reverse it so First into the stack is First in the Queue
            returnList.Add(new Queue<Product>(currentList.Reverse()));
        }
        else
        {
            //Keep looking, the answer is out there
            var result = Permutations(list, requiredValue, currentList);
            returnList.AddRange(result);
        }
        currentList.Pop();  
    }


    return returnList;
}


struct Product
{
    public int ProductID;
    public int Quantity;
}

Answer 3

I'll discuss the solution in terms of Python because I don't have C# installed on this Mac, but C# has iterators, so what I'm talking about will work.

First of all, as you discovered, you DO NOT want to return the whole list. It consumes a tremendous amount of memory. Instead return an iterator as in https://msdn.microsoft.com/en-us/library/65zzykke(v=vs.100).aspx that will return each element of your list in turn.

Secondly, you can build iterators out of iterators. The first one is the one that does subsets where the last element pushes you to your threshold and beyond:

def minimal_subset_iter (product, threshold):
    # Sort smallest to the front so that we skip no combinations that
    # will lead to our threshold in any order.
    ids = list(sorted(product.keys(), key=lambda key: (product[key], key)))

    # Figure out the size of the trailing sums.
    remaining_sum = []
    total_sum = sum(product.values())
    for i in range(len(ids)):
        remaining_sum.append(
            total_sum - sum(product[ids[j]] for j in range(i)))
    remaining_sum.append(0)

    # We modify this in place and yield it over and over again.
    # DO NOT modify it in the return, make a copy of it there.
    chosen_set = []
    def _choose (current_sum, i):
        if threshold <= current_sum:
            yield chosen_set
        elif threshold <= current_sum + remaining_sum[i]:
            # Can I finish without this element?
            for x in _choose(current_sum, i+1):
                yield x

            # All of the ways to finish with this element.
            chosen_set.append(ids[i])
            current_sum = current_sum + product[ids[i]]
            for x in _choose(current_sum, i+1):
                yield x
            # Cleanup!
            chosen_set.pop()

    return _choose(0, 0)


for x in minimal_subset_iter({1: 5, 2: 5, 3: 8, 4: 15}, 15):
    print(x)

And now you need an iterator that turns a minimal subset into all permutations of that subset where the last element pushes you to the threshold.

I won't write that one since the principle is straightforward. And besides you have to translate it into a different language. But the idea is to pull out each possibility for that last element that reaches the end, run permutations of the rest, and append the last element back before yielding it.

This algorithm will be very efficient on memory (it basically keeps the dictionary and the current permutation) and also quite efficient on performance (it has a lot of lists to create, but will waste little time creating ones that it doesn't need). It does, however, take some time to wrap your head around this way of working.