找到对象的唯一排列

Question

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

E.g.

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个结果，如果我拿产品4，那么我就不需要把它和任何东西结合起来。同样，如果我拿到产品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

这里是我的C++代码（可以很容易地将其转换为C＃代码）

您的输入输出应该是。你错过了{4,2,1}，{ 4,1,2} ... { 1,2,3,4} .....喜欢组合和排列。

const int sz = 50, wmx = 50; 
int qua[sz], fac[sz], dp[sz][sz][wmx], vst[sz][sz][wmx], prs = 0, n, reqQ; 

int rec(int now, int taken, int wTaken) { 

    if (now < 0) { 
     return 0; 
    } 

    if (vst[now][taken][wTaken] == prs) { 
     return dp[now][taken][wTaken]; 
    } 
    vst[now][taken][wTaken] = prs; 

    dp[now][taken][wTaken] = rec(now-1, taken, wTaken) + rec(now-1, taken + 1, wTaken + qua[now]); 
    if ((wTaken + qua[now]) >= reqQ) { 
     dp[now][taken][wTaken] += fac[taken + 1]; 
    } 
    return dp[now][taken][wTaken]; 
} 

int main() { 
    fac[0] = 1; 
    for (int i = 1; i <= sz; i++) { 
     fac[i] = fac[i-1] * i; 
    } 

    while (cin >> n >> reqQ) { 
     for (int i = 0; i < n; i++) { 
      cin >> qua[i]; 
     } 
     prs++; 
     cout << rec(n-1, 0, 0) << endl; 
    } 

    return 0; 
} 

Answer 3

我将讨论在Python方面的解决方案，因为我没有安装这台Mac上的C＃，但是C＃有迭代器，所以我正在谈论将工作。

首先，你发现，你不想要返回整个列表。它消耗了大量的内存。而是返回一个迭代器，如https://msdn.microsoft.com/en-us/library/65zzykke(v=vs.100).aspx，它将依次返回列表中的每个元素。其次，你可以用迭代器构建迭代器。第一个是一个没有子集，其中的最后一个元素会使你得到你的门槛及以后：

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 4

貌似只有两条规则：
1.摘取的元素是不同的。
2.挑选元素的数量总和必须大于目标，而不仅仅是等于目标。

我的例子添加一些接口进行排序。列出所有可达到目标的组合。但我试图以独特的形式列出来阅读。您可以在每个组合中对oringinal扩展作业。

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