查找对象的唯一排列

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

这可能不是最有效的答案，但它确实给出了正确的答案：

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 2

我将根据 Python 讨论解决方案，因为我没有在此 Mac 上安装 C#，但 C# 有迭代器，所以我所说的会起作用。

首先，正如您发现的那样，您不想 return 整个列表。它消耗了大量的内存。取而代之的是 return 一个迭代器，如 https://msdn.microsoft.com/en-us/library/65zzykke(v=vs.100).aspx 中那样，它将依次 return 列表中的每个元素。

其次，您可以从迭代器中构建迭代器。第一个是做子集的那个，其中最后一个元素将您推向您的阈值并超越：

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)

现在您需要一个迭代器，将最小子集转换为该子集的所有排列，其中最后一个元素将您推向阈值。

那个我就不写了，原理很简单。此外，您还必须将其翻译成另一种语言。但我们的想法是提取到达末尾的最后一个元素的每种可能性，其余元素的运行排列，并在产生它之前追加最后一个元素。

这个算法在内存上非常有效（它基本上保留了字典和当前排列）并且在性能上也非常有效（它有很多列表要创建，但创建它不会浪费很少的时间不需要）。但是，确实需要一些时间来了解这种工作方式。

Answer 3

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

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

PS。为了订单目的，我添加了 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();
    }

查找对象的唯一排列

Find unique permutations for object

c#

algorithm

knapsack-problem