Комбинаторный алгоритм для извлечения подмножеств списков для взломщика паролей

Question

Я должен быть ржавым, потому что не могу найти решение.

Скажем, у нас есть 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 машин. Вопрос в том, как программно сделать это, когда вы не можете контролировать количество машин / количество элементов в списке?

Answer 1

, если бы был 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 получает «пиццу красного ребенка» - «пиццу голубого ребенка». Работник 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;
}

Answer 2

Если я правильно понял, возможно, вы можете попробовать заменить элементы, выбранные вами в выбранных разделах.Например:

пицца - красный - ребенок

затем;

макароны - красный - ребенок

.,.

и т. Д. ...

, поэтому вместо создания новых выбранных разделов для каждой возможной комбинации вы можете попытаться манипулировать одним выбранным разделом для каждой возможной комбинации, как только вы закончите с ним.