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

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] += 1blocks = [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) {

    std::map<std::multiset<int>, std::vector<int> > cartCombs;

    unsigned long int len = v.size();

    unsigned long int myProd = 1;

    std::vector<unsigned long int> s(len);

    for (std::size_t j = 0; j < len; ++j) {

        myProd *= v[j].size();

        s[j] = v[j].size() - 1;

    }

    unsigned long int loopLim = myProd - 1;

    std::vector<std::vector<int> > res(myProd, std::vector<int>());

    std::vector<unsigned long int> myCounter(len, 0);

    std::vector<int> value(len, 0);

    std::multiset<int> key;

    for (std::size_t j = 0; j < loopLim; ++j) {

        key.clear();

        for (std::size_t k = 0; k < len; ++k) {

            value[k] = v[k][myCounter[k]];

            key.insert(value[k]);

        }

        cartCombs.insert({key, value});

        int test = 0;

        while (myCounter[test] == s[test]) {

            myCounter[test] = 0;

            ++test;

        }

        ++myCounter[test];

    }

    key.clear();

    // Get last possible combination

    for (std::size_t k = 0; k < len; ++k) {

        value[k] = v[k][myCounter[k]];

        key.insert(value[k]);

    }

    cartCombs.insert({key, value});

    if (verbose) {

        int count = 1;

        for (std::pair<std::multiset<int>, std::vector<int> > element : cartCombs) {

            std::string tempStr;

            for (std::size_t k = 0; k < len; ++k)

                tempStr += std::to_string(element.second[k]) + ' ';

            std::cout << count << " : " << tempStr << std::endl;

            ++count;

        }

    }

}

使用长度从4到8的8个向量的测试用例填充从1到15的随机整数，上述算法在我的计算机上运行约5秒钟。考虑到我们正在从我们的产品中获得近250万个总结果，这还不错，但是我们可以做得更好。但是如何？

最好的性能是由std::unordered_map恒定时间内建立的键提供的。我们上面的键是建立在对数时间（多集，映射和哈希映射复杂度）中的。所以问题是，我们如何克服这些障碍？

最棒的表演

我们知道我们必须放弃std::multiset。我们需要某种具有可交换类型属性，同时又能提供独特结果的对象。

输入算术基本定理

它指出，每个数字都可以用质数的乘积唯一表示（按因子的顺序）。有时称为素分解。

因此，现在，我们可以像以前一样简单地进行操作，而不是构造多集，而是将每个索引映射到素数并将结果相乘。这将为我们的密钥提供恒定的时间构造。这是一个示例，显示了此技术在我们之前创建的示例中的强大功能（P下面的NB是素数的列表... (2, 3, 5, 7, 11, etc.)：

                   Maps to                    Maps to            product

vec1 = (1, 2, 1)    -->>    P[1], P[2], P[1]   --->>   3, 5, 3    -->>    45

vec2 = (2, 1, 1)    -->>    P[2], P[1], P[1]   --->>   5, 3, 3    -->>    45

vec3 = (2, 2, 1)    -->>    P[2], P[2], P[1]   --->>   5, 5, 3    -->>    75

这太棒了！！vec1并vec2映射到相同的数字，而vec3正如我们所希望的那样映射到不同的值。

void cartestionCombosPrimes(std::vector<std::vector<int> > v, 

                        std::vector<int> primes,

                        bool verbose) {

    std::unordered_map<int64_t, std::vector<int> > cartCombs;

    unsigned long int len = v.size();

    unsigned long int myProd = 1;

    std::vector<unsigned long int> s(len);

    for (std::size_t j = 0; j < len; ++j) {

        myProd *= v[j].size();

        s[j] = v[j].size() - 1;

    }

    unsigned long int loopLim = myProd - 1;

    std::vector<std::vector<int> > res(myProd, std::vector<int>());

    std::vector<unsigned long int> myCounter(len, 0);

    std::vector<int> value(len, 0);

    int64_t key;

    for (std::size_t j = 0; j < loopLim; ++j) {

        key = 1;

        for (std::size_t k = 0; k < len; ++k) {

            value[k] = v[k][myCounter[k]];

            key *= primes[value[k]];

        }

        cartCombs.insert({key, value});

        int test = 0;

        while (myCounter[test] == s[test]) {

            myCounter[test] = 0;

            ++test;

        }

        ++myCounter[test];

    }

    key = 1;

    // Get last possible combination

    for (std::size_t k = 0; k < len; ++k) {

        value[k] = v[k][myCounter[k]];

        key *= primes[value[k]];

    }

    cartCombs.insert({key, value});

    std::cout << cartCombs.size() << std::endl;

    if (verbose) {

        int count = 1;

        for (std::pair<int, std::vector<int> > element : cartCombs) {

            std::string tempStr;

            for (std::size_t k = 0; k < len; ++k)

                tempStr += std::to_string(element.second[k]) + ' ';

            std::cout << count << " : " << tempStr << std::endl;

            ++count;

        }

    }

}

在上面的示例中，该示例将产生近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) {

    value[k] = v[k][myCounter[k]];

    key *= primes[rank[k][myCounter[k]]];

}

编辑：

正如一些评论者所指出的，上述方法掩盖了必须生成所有产品的事实。我应该说是第一次。就个人而言，鉴于许多不同的演示，我看不出如何避免这种情况。

另外，万一有人好奇，这是我上面使用的测试用例：

[1 10 14  6],

[7  2  4  8  3 11 12],

[11  3 13  4 15  8  6  5],

[10  1  3  2  9  5  7],

[1  5 10  3  8 14],

[15  3  7 10  4  5  8  6],

[14  9 11 15],

[7  6 13 14 10 11  9  4]

它应该返回162295唯一的组合。