从大小为K的对象组中生成所有大小为N的集合

-1

给定一组K对象，生成所有大小为N的集合（其中N> K）。例如，从集合{1,2}（K = 2）开始，生成所有大小为N = 3的集合将导致以下输出集合：{1,1,1} {1,1,2}，{ 1,2,1}，{2,1,1}，{2,2,1}，{2,1,2}，{1,2,2}，{2,2,2}什么是高效算法来生成这样的集合？从大小为K的对象组中生成所有大小为N的集合

注意Ken White：我的研究只发现了处理C（mn）的算法，其中n < m;给定集合中项目的排列和组合的算法。我正在尝试这样做，因为如果没有算法，我会尝试让我的代码完成什么？

也许我之前的发帖不清楚，但您的回复 - “请原谅我完全缺乏努力，但是有人可以为我写这段代码吗？稍后再回来捡起来，Tx再见 - Ken White 6月27日22:54“真的很专业，乐于助人。

来源

2016-07-02 user1930297

这是一个不可能的目标，因为'{2,2,2}'不是一个可能的集合。如果你正在处理列表问题，那么问题是很难处理的，但是还不清楚哪些工作还有待完成。从一组M个项目中进行N次取样非常简单，只需更换即可。 – amalloy

你正在计算基数'K'数字'0'到'（K^N） - 1'。 – beaker

您可以为套件分配订单，因此您不会重新访问您已经处理的任何订单。从K[0]发生的所有集合开始0次，K[1]发生0次，最后K[last]出现N次。然后考虑当K[last-1]出现1次，等等，每次你已经分配的元素的总和达到N短路你的搜索。

伪代码：

addAllSets(N, K, 0, new int[K], new Set()) //Initial call 

addAllSets(int targetCount, int K, int index, int[] prefix, Set allSets){ 
    if (index < k): //We still have the rest of the elements to consider 
     for i in range 0 to targetCount - 1: 
      prefix[index] = i //Try it with i of this element 
      addAllSets(targetCount - i, K, index + 1, prefix.copy, allSets) //Recursively check remaining elements 
    prefix[index] = targetCount //Or just fill in the rest of the set with copies of this element 
    allSets.add(prefix) //Add this to the set of sets

前缀店计数对于一些数量的元素（总数永远是K - targetCount被调用函数时。）每次我们“补起来”，我们把它添加到所有集合的集合。

来源

2016-07-02 00:24:41

从大小为K的对象组中生成所有大小为N的集合

回答

相关问题