我有一个产品清单,上面有一个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#中只创建所需的置换?

最佳答案

看起来只有两条规则:
一。选择的元素是不同的。
2.所选元素的数量之和必须大于目标,而不仅仅等于目标。
我的示例添加了一些用于排序的接口列出了能达到目标的各种组合。但我试着以独特的形式列出供阅读您可以在每个组合中原始展开作业。
另外,为了订货,我加了一个比较的,不是很重要的。

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

关于c# - 查找对象的唯一排列,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/45293687/

10-13 08:13
查看更多