algorithm - 用于为密码破解者提取列表子集的组合算法
问题描述
我一定是生疏了,因为我想不出解决办法。
假设我们有 3 个单词列表:
list1 list2 list3
----- ----- -----
pizza red child
pasta green man
apple blue adult
pear yellow old
我需要从每个列表中选择子集,例如:
- 选择的所有部分的总和将返回整个列表中的所有可能组合(例如 Pizza-red-child 或 Pizza-red-man)
- 没有重复项,因此如果选定的第 1 部分包含一个组合,我不希望任何其他集合包含它
- 所选部分需要具有一定的最小尺寸(定义为元素计数 1 * 计数 2 * 等)
- 我需要最少数量的选定部分
现在,简单的解决方案当然是,假设您必须将此列表分成 4 份,供 4 名工人使用(我称之为上面的选定部分),只需将每个组合从披萨开始发送给工人 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 台机器的方法。问题是,当您无法控制列表中的机器数量/元素数量时,如何以编程方式做到这一点?
解决方案
如果有 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 得到“披萨蓝人”-“意大利面红大人”等。
#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;
}
推荐阅读
- php - 如何修改 WooCommerce 类别小部件以显示子类别(如果它是父类别)并显示兄弟姐妹(如果它是子类别)?
- elixir - 凤凰无效的CSRF
- java - 使用 servlet 上下文从 Spring Boot 应用程序获取资源的路径
- javascript - 异步操作完成后如何退出节点脚本?
- applescript - 从处理应用程序的 finder 中轮询选择
- amazon-web-services - 用于自动扩展的 AWS Codestar 设置 Beanstalk 策略错误
- php - 从重复的 Wordpress 元框创建和显示内容
- android - 即使应用程序在前台运行,onNotificationPosted 方法也不会被调用
- python - Python:虽然不是异常
- assembly - 源和目标的大小必须相同 (8086)