c# - 查找对象的唯一排列

Question

我有一个包含 ID 和数量的产品列表，我需要找到一个将填充特定数量的产品组合列表。

例如

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

如果我需要 15 个数量，那么我想得到一个包含以下组合的列表:

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}

这几乎是一个排列，但它过滤掉了总和超过要求的条目。如果在任何时候当前值的总和超过 15，我需要停止获取更多项。这样做，如果我有所有排列，那么我将有 24 个结果，但我只有 16 个。

例如如果我拿产品 4 那么我不需要将它与任何东西结合起来得到 15。同样，如果我拿产品 1 然后拿产品 4，我不需要再拿起任何元素，因为总和已经超过 15( 5 + 15 = 20)。

我能够通过获取所有排列(例如 here)然后将其过滤到我关心的那些来使代码正常工作，但是一旦您开始获得大量产品(例如 30 个)，您就结束了多达 43 亿个组合导致内存不足异常。

如何在 C# 中只创建所需的排列？

Answer 1

看起来只有两条规则:
1. 选取的元素是不同的。
2. 选取的元素数量之和必须大于目标，不能只等于目标。

我的示例添加了一些用于排序的接口(interface)。每一种可以达到目标的组合都被列出来了。但我试图以独特的形式列出以供阅读。您可以在每个组合中原始扩展作业。

附言。出于订单目的，我添加了 IComparable，这不是很重要。

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

测试部分提供产品列表和目标。

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