从重叠的池中挑选无序组合

Question

我有值池，我想通过从某些池中进行选择来生成每种可能的无序组合。

例如，我想从池0，池0和池1中进行选择：

>>> pools = [[1, 2, 3], [2, 3, 4], [3, 4, 5]]

>>> part = (0, 0, 1)

>>> list(product(*(pools[i] for i in part)))

[(1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 3), (1, 3, 4), (2, 1, 2), (2, 1, 3), (2, 1, 4), (2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 3, 2), (2, 3, 3), (2, 3, 4), (3, 1, 2), (3, 1, 3), (3, 1, 4), (3, 2, 2), (3, 2, 3), (3, 2, 4), (3, 3, 2), (3, 3, 3), (3, 3, 4)]

这通过从池0，池0和池1中进行选择来生成每种可能的组合。

但是顺序对我来说并不重要，因此许多组合实际上都是重复的。例如，由于我使用了笛卡尔乘积，所以(1, 2, 4)和(2, 1, 4)都生成了。

我想出了一种简单的方法来缓解此问题。对于从单个池中挑选的成员，我选择时不进行排序combinations_with_replacement。我计算从每个池中抽奖的次数。代码如下：

cnt = Counter()

for ind in part: cnt[ind] += 1

blocks = [combinations_with_replacement(pools[i], cnt[i]) for i in cnt]

return [list(chain(*combo)) for combo in product(*blocks)]

如果我碰巧多次从同一个池中进行选择，这将减少对重复项的排序。但是，所有池都有很多重叠，并且combinations_with_replacement在合并的多个池上使用会产生一些无效的组合。有没有更有效的方法来生成无序组合？

编辑：有关输入的额外信息：零件和池的数量很小（〜5和〜20），为简单起见，每个元素都是一个整数。我已经解决了实际的问题，因此这只是出于学术目的。假设每个池中有成千上万个整数，但有些池很小，只有几十个。因此，某种结合或相交似乎是可行的方法。

Answer 1

一种节省工作的方法可能是生成前k个选定池的重复数据消除组合，然后将其扩展到前k + 1个池的重复数据消除组合。这样可以避免单独生成和拒绝所有长度为20的组合，2, 1而不是1, 2从前两个池中选择的组合：def combinations_from_pools(pools):    # 1-element set whose one element is an empty tuple.    # With no built-in hashable multiset type, sorted tuples are probably the most efficient    # multiset representation.    combos = {()}    for pool in pools:        combos = {tuple(sorted(combo + (elem,))) for combo in combos for elem in pool}    return combos但是，使用您要讨论的输入大小，无论生成组合的效率如何，您将永远无法处理所有组合。即使有20个相同的1000个元素池，也将有496432432432489450355564471512635900731810050组合（1019按星条形图选择20），或大约5e41。如果您征服了地球，并将全人类所有计算设备的所有处理能力都投入到了这项任务中，那么您仍然无法屈服。您需要找到一种更好的方法来解决基础任务。

Answer 2

这是一个困难的问题。我认为一般情况下，您最好的选择是实现a hash table，其中键为a multiset，值为实际组合。这类似于@ErikWolf提到的内容，但是此方法避免了首先产生重复项，因此不需要过滤。当我们遇到时，它还会返回正确的结果multisets。我现在正在嘲笑一种更快的解决方案，但可以保存以备后用。忍受我。如评论中所述，一种可行的方法是合并所有池，并简单地生成此合并池的组合，然后选择池的数量。您将需要一种能够生成多集组合的工具，据我所知，该工具可以在中使用python。在sympy图书馆里from sympy.utilities.iterables import multiset_combinations。问题在于，我们仍然会产生重复的值，更糟糕的是，我们会产生用类似的set和product组合的方法无法获得的结果。例如，如果我们要进行排序和合并OP中的所有池之类的操作，并应用以下内容：list(multiset_permutations([1,2,2,3,3,4,4,5]))有两个结果将是[1 2 2]，[4 4 5]而从都无法获得这两个结果[[1, 2, 3], [2, 3, 4], [3, 4, 5]]。除了特殊情况，我看不出如何避免检查所有可能的产品。我希望我错了。算法概述主要思想是将向量乘积的组合映射为唯一组合，而不必过滤出重复项。OP给出的示例（即(1, 2, 3)和(1, 3, 2)）应仅映射到一个值（因为顺序无关紧要，所以可以是两个值之一）。我们注意到，两个向量是相同的集合。现在，我们也遇到类似这样的情况：vec1 = (1, 2, 1)vec2 = (2, 1, 1)vec3 = (2, 2, 1)我们需要vec1并vec2映射到相同的值，而vec3需要映射到其自身的值。这是集合的问题，因为所有这些都是等效集合（对于集合，元素因此是唯一的{a, b, b}并且{a, b}是等效的）。这是多集起作用的地方。对于多集，(2, 2, 1)和(1, 2, 1)是不同的，但是(1, 2, 1)并且(2, 1, 1)是相同的。很好 现在，我们有了一种生成唯一密钥的方法。由于我不是python程序员，因此我将继续C++。如果我们尝试按原样实施以上所有内容，将会遇到一些问题。据我所知，您不能将std::multiset<int>用作关键部分std::unordered_map。但是，我们可以进行常规std::map。它的性能不如下面的哈希表（实际上是一棵红黑树），但是它仍然可以提供不错的性能。这里是：void cartestionCombos(std::vector<std::vector<int> > v, bool verbose) {&nbsp; &nbsp; std::map<std::multiset<int>, std::vector<int> > cartCombs;&nbsp; &nbsp; unsigned long int len = v.size();&nbsp; &nbsp; unsigned long int myProd = 1;&nbsp; &nbsp; std::vector<unsigned long int> s(len);&nbsp; &nbsp; for (std::size_t j = 0; j < len; ++j) {&nbsp; &nbsp; &nbsp; &nbsp; myProd *= v[j].size();&nbsp; &nbsp; &nbsp; &nbsp; s[j] = v[j].size() - 1;&nbsp; &nbsp; }&nbsp; &nbsp; unsigned long int loopLim = myProd - 1;&nbsp; &nbsp; std::vector<std::vector<int> > res(myProd, std::vector<int>());&nbsp; &nbsp; std::vector<unsigned long int> myCounter(len, 0);&nbsp; &nbsp; std::vector<int> value(len, 0);&nbsp; &nbsp; std::multiset<int> key;&nbsp; &nbsp; for (std::size_t j = 0; j < loopLim; ++j) {&nbsp; &nbsp; &nbsp; &nbsp; key.clear();&nbsp; &nbsp; &nbsp; &nbsp; for (std::size_t k = 0; k < len; ++k) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; value[k] = v[k][myCounter[k]];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; key.insert(value[k]);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; cartCombs.insert({key, value});&nbsp; &nbsp; &nbsp; &nbsp; int test = 0;&nbsp; &nbsp; &nbsp; &nbsp; while (myCounter[test] == s[test]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; myCounter[test] = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ++test;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; ++myCounter[test];&nbsp; &nbsp; }&nbsp; &nbsp; key.clear();&nbsp; &nbsp; // Get last possible combination&nbsp; &nbsp; for (std::size_t k = 0; k < len; ++k) {&nbsp; &nbsp; &nbsp; &nbsp; value[k] = v[k][myCounter[k]];&nbsp; &nbsp; &nbsp; &nbsp; key.insert(value[k]);&nbsp; &nbsp; }&nbsp; &nbsp; cartCombs.insert({key, value});&nbsp; &nbsp; if (verbose) {&nbsp; &nbsp; &nbsp; &nbsp; int count = 1;&nbsp; &nbsp; &nbsp; &nbsp; for (std::pair<std::multiset<int>, std::vector<int> > element : cartCombs) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; std::string tempStr;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (std::size_t k = 0; k < len; ++k)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tempStr += std::to_string(element.second[k]) + ' ';&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; std::cout << count << " : " << tempStr << std::endl;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ++count;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}使用长度从4到8的8个向量的测试用例填充从1到15的随机整数，上述算法在我的计算机上运行约5秒钟。考虑到我们正在从我们的产品中获得近250万个总结果，这还不错，但是我们可以做得更好。但是如何？最好的性能是由std::unordered_map恒定时间内建立的键提供的。我们上面的键是建立在对数时间（多集，映射和哈希映射复杂度）中的。所以问题是，我们如何克服这些障碍？最棒的表演我们知道我们必须放弃std::multiset。我们需要某种具有可交换类型属性，同时又能提供独特结果的对象。输入算术基本定理它指出，每个数字都可以用质数的乘积唯一表示（按因子的顺序）。有时称为素分解。因此，现在，我们可以像以前一样简单地进行操作，而不是构造多集，而是将每个索引映射到素数并将结果相乘。这将为我们的密钥提供恒定的时间构造。这是一个示例，显示了此技术在我们之前创建的示例中的强大功能（P下面的NB是素数的列表... (2, 3, 5, 7, 11, etc.)：&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Maps to&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Maps to&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; productvec1 = (1, 2, 1)&nbsp; &nbsp; -->>&nbsp; &nbsp; P[1], P[2], P[1]&nbsp; &nbsp;--->>&nbsp; &nbsp;3, 5, 3&nbsp; &nbsp; -->>&nbsp; &nbsp; 45vec2 = (2, 1, 1)&nbsp; &nbsp; -->>&nbsp; &nbsp; P[2], P[1], P[1]&nbsp; &nbsp;--->>&nbsp; &nbsp;5, 3, 3&nbsp; &nbsp; -->>&nbsp; &nbsp; 45vec3 = (2, 2, 1)&nbsp; &nbsp; -->>&nbsp; &nbsp; P[2], P[2], P[1]&nbsp; &nbsp;--->>&nbsp; &nbsp;5, 5, 3&nbsp; &nbsp; -->>&nbsp; &nbsp; 75这太棒了！！vec1并vec2映射到相同的数字，而vec3正如我们所希望的那样映射到不同的值。void cartestionCombosPrimes(std::vector<std::vector<int> > v,&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; std::vector<int> primes,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; bool verbose) {&nbsp; &nbsp; std::unordered_map<int64_t, std::vector<int> > cartCombs;&nbsp; &nbsp; unsigned long int len = v.size();&nbsp; &nbsp; unsigned long int myProd = 1;&nbsp; &nbsp; std::vector<unsigned long int> s(len);&nbsp; &nbsp; for (std::size_t j = 0; j < len; ++j) {&nbsp; &nbsp; &nbsp; &nbsp; myProd *= v[j].size();&nbsp; &nbsp; &nbsp; &nbsp; s[j] = v[j].size() - 1;&nbsp; &nbsp; }&nbsp; &nbsp; unsigned long int loopLim = myProd - 1;&nbsp; &nbsp; std::vector<std::vector<int> > res(myProd, std::vector<int>());&nbsp; &nbsp; std::vector<unsigned long int> myCounter(len, 0);&nbsp; &nbsp; std::vector<int> value(len, 0);&nbsp; &nbsp; int64_t key;&nbsp; &nbsp; for (std::size_t j = 0; j < loopLim; ++j) {&nbsp; &nbsp; &nbsp; &nbsp; key = 1;&nbsp; &nbsp; &nbsp; &nbsp; for (std::size_t k = 0; k < len; ++k) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; value[k] = v[k][myCounter[k]];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; key *= primes[value[k]];&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; cartCombs.insert({key, value});&nbsp; &nbsp; &nbsp; &nbsp; int test = 0;&nbsp; &nbsp; &nbsp; &nbsp; while (myCounter[test] == s[test]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; myCounter[test] = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ++test;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; ++myCounter[test];&nbsp; &nbsp; }&nbsp; &nbsp; key = 1;&nbsp; &nbsp; // Get last possible combination&nbsp; &nbsp; for (std::size_t k = 0; k < len; ++k) {&nbsp; &nbsp; &nbsp; &nbsp; value[k] = v[k][myCounter[k]];&nbsp; &nbsp; &nbsp; &nbsp; key *= primes[value[k]];&nbsp; &nbsp; }&nbsp; &nbsp; cartCombs.insert({key, value});&nbsp; &nbsp; std::cout << cartCombs.size() << std::endl;&nbsp; &nbsp; if (verbose) {&nbsp; &nbsp; &nbsp; &nbsp; int count = 1;&nbsp; &nbsp; &nbsp; &nbsp; for (std::pair<int, std::vector<int> > element : cartCombs) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; std::string tempStr;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (std::size_t k = 0; k < len; ++k)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tempStr += std::to_string(element.second[k]) + ' ';&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; std::cout << count << " : " << tempStr << std::endl;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ++count;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}在上面的示例中，该示例将产生近250万个产品，上述算法在不到0.3秒的时间内返回了相同的结果。对于后一种方法，有两个警告。我们必须让素数产生先验，并且如果我们在笛卡尔乘积中有许多向量，则密钥可能会超出的范围int64_t。由于存在许多可用于生成质数的资源（库，查找表等），第一个问题应该不会那么难克服。我不太确定，但是我读到，python由于整数具有任意精度（Python整数范围），因此后一个问题不应该是一个问题。我们还必须处理这样一个事实，即我们的源向量可能不是具有较小值的好的整数向量。在继续进行之前，可以通过对所有向量中的所有元素进行排名来解决此问题。例如，给定以下向量：vec1 = (12345.65, 5, 5432.11111)vec2 = (2222.22, 0.000005, 5)vec3 = (5, 0.5, 0.8)对它们进行排名，我们将获得：rank1 = (6, 3, 5)rank2 = (4, 0, 3)rank3 = (3, 1, 2)现在，可以使用这些值代替实际值来创建密钥。代码中唯一会更改的部分是用于构建密钥的for循环（当然还有rank需要创建的对象）：for (std::size_t k = 0; k < len; ++k) {&nbsp; &nbsp; value[k] = v[k][myCounter[k]];&nbsp; &nbsp; key *= primes[rank[k][myCounter[k]]];}编辑：正如一些评论者所指出的，上述方法掩盖了必须生成所有产品的事实。我应该说是第一次。就个人而言，鉴于许多不同的演示，我看不出如何避免这种情况。另外，万一有人好奇，这是我上面使用的测试用例：[1 10 14&nbsp; 6],[7&nbsp; 2&nbsp; 4&nbsp; 8&nbsp; 3 11 12],[11&nbsp; 3 13&nbsp; 4 15&nbsp; 8&nbsp; 6&nbsp; 5],[10&nbsp; 1&nbsp; 3&nbsp; 2&nbsp; 9&nbsp; 5&nbsp; 7],[1&nbsp; 5 10&nbsp; 3&nbsp; 8 14],[15&nbsp; 3&nbsp; 7 10&nbsp; 4&nbsp; 5&nbsp; 8&nbsp; 6],[14&nbsp; 9 11 15],[7&nbsp; 6 13 14 10 11&nbsp; 9&nbsp; 4]它应该返回162295唯一的组合。