为密码破解者提取列表子集的组合算法

Question

我一定是生疏了，想不出办法

假设我们有 3 个单词列表：

list1   list2   list3
-----   -----   -----
pizza   red     child
pasta   green   man
apple   blue    adult
pear    yellow  old

我需要从每个列表中 select 个子集，这样：

所有部分 selected 的总和将 return 整个列表中的每个可能组合（例如 pizza-red-child 或 pizza-red-man）
没有重复项，所以如果 selected 第 1 节包含一个组合，我不希望任何其他集合包含它
selected 部分需要有一定的最小大小（定义为元素计数 1 * 计数 2 * 等）
我需要有最少数量的 selected 版块

现在简单的解决方案当然是，假设您必须将此列表分成 4 份，供 4 名工人使用（我称之为上面的 selected 部分），只需将以披萨开头的每个组合发送给工人 1 , 意大利面到 2 等等。但是，如果您的工作人员数量多于最长列表中的元素数量，那么这将不起作用，并且事情会变得复杂。

编辑 - 示例

所以给出的目标是列表，找到所有的组合。但是你需要把主要的工作拆分成更多的机器。

上面解释的简单解决方案是，最长列表中有 4 个元素，只需使用 4 台机器。在这种情况下，它看起来像这样：

机器 1：

list1   list2   list3
-----   -----   -----
pizza   red     child
        green   man
        blue    adult
        yellow  old

机器 2：

list1   list2   list3
-----   -----   -----
        red     child
pasta   green   man
        blue    adult
        yellow  old

机器 3：

list1   list2   list3
-----   -----   -----
        red     child
        green   man
apple   blue    adult
        yellow  old

机器 4：

list1   list2   list3
-----   -----   -----
        red     child
        green   man
        blue    adult
pear    yellow  old

但是，如果您必须将工作分配给比最长列表中的元素数量更多的机器，这将不起作用。在那种情况下，假设您需要将工作拆分到 8 台机器上（或每台机器分两轮 4 台机器），它必须看起来像这样（我使用 8 是因为它使示例更简单，但实际数量并非如此不错）。

机器 1：

list1   list2   list3
-----   -----   -----
pizza   red     child
        green   man
                adult
                old

机器 2：

list1   list2   list3
-----   -----   -----
        red     child
pasta   green   man
                adult
                old

机器 3：

list1   list2   list3
-----   -----   -----
        red     child
        green   man
apple           adult
                old

机器 4：

list1   list2   list3
-----   -----   -----
        red     child
        green   man
                adult
pear            old

机器 5：

list1   list2   list3
-----   -----   -----
pizza           child
                man
        blue    adult
        yellow  old

机器 6：

list1   list2   list3
-----   -----   -----
                child
pasta           man
        blue    adult
        yellow  old

机器 7：

list1   list2   list3
-----   -----   -----
                child
                man
apple   blue    adult
        yellow  old

机器 8：

list1   list2   list3
-----   -----   -----
                child
                man
        blue    adult
pear    yellow  old

如您所见，这是一种将最大元素为 4 的原始列表拆分为 8 台机器的方法。问题是，当您无法控制列表中 machines/number 元素的数量时，如何以编程方式做到这一点？

Answer 1

如果我做对了，也许你可以尝试替换你在所选部分中选择的元素。例如;

披萨-红色-儿童

然后；

意大利面-红色-儿童

。 . .

等等...

因此，您可以在完成后尝试为每种可能的组合操纵一个选定部分，而不是为每种可能的组合创建新的选定部分。

Answer 2

如果有 1 个工人，则按顺序排列：

pizza red child
pizza red man
pizza red adult
pizza red old
pizza green child
pizza green man
pizza green adult
pizza green old
pizza blue child
pizza blue man
pizza blue adult
pizza blue old
pizza yellow child
pizza yellow man
pizza yellow adult
pizza yellow old
pasta red child
pasta red man
pasta red adult
pasta red old
pasta green child
pasta green man
pasta green adult
pasta green old
pasta blue child
pasta blue man
pasta blue adult
pasta blue old
pasta yellow child
pasta yellow man
pasta yellow adult
pasta yellow old
apple red child
apple red man
apple red adult
apple red old
apple green child
apple green man
apple green adult
apple green old
apple blue child
apple blue man
apple blue adult
apple blue old
apple yellow child
apple yellow man
apple yellow adult
apple yellow old
pear red child
pear red man
pear red adult
pear red old
pear green child
pear green man
pear green adult
pear green old
pear blue child
pear blue man
pear blue adult
pear blue old
pear yellow child
pear yellow man
pear yellow adult
pear yellow old

如果您有更多工人，请按范围拆分。例如Worker1 获得 "pizza red child" - "pizza blue child"。工人 2 获得 "pizza blue man" - "pasta red adult" 等

#include <vector>
#include <thread>
#include <cstdio>
using namespace std;

vector<vector<string>> lists = {{"apple", "pasta", "pear", "pizza"}, {"red", "green", "blue", "yellow"}, {"child", "man", "adult", "old"}};
const int K = 7;
long long N = 1;

std::vector<long long>  calc_vector(int k){
    long long remain_all = N;
    long long remain_cur = N * k / K;
    std::vector<long long>  ret;
    for(int i=0; i<lists.size(); ++i){
        long long sz = lists[i].size();
        long long i1 = remain_cur * sz / remain_all;
        ret.push_back(i1);
        remain_all /= sz;
        remain_cur -= remain_all * i1;
    }
    return ret;
}


void work(int k){
    auto v1 = calc_vector(k);
    auto v2 = calc_vector(k+1);
    while(v1 != v2){
        printf("%d: %s-%s-%s\n", k, lists[0][v1[0]].c_str(), lists[1][v1[1]].c_str(), lists[2][v1[2]].c_str());
        for(int i=v1.size()-1; i>=0; --i){
            v1[i]++;
            if(v1[i] != lists[i].size() || i==0) break;
            else v1[i] = 0;
        }
    }
}

int main(){
    for(auto &list : lists) N *= list.size();
    vector<thread> threads;
    for(int i=0; i<K; ++i) threads.push_back(thread(work, i));
    for(auto &thread : threads) thread.join();
    return 0;
}

为密码破解者提取列表子集的组合算法

Combinatorics algorithm for extracting subsets of lists for a password cracker

passwords

algorithm

math

combinatorics

编辑 - 示例