Combinatorics algorithm for extracting subsets of lists for a password cracker

Question

I must be rusty because I can't come up with a solution.

Say we have 3 lists of words:

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

I need to select subsets from each lists, such that:

• The sum of all of the sections selected will return every possible combination from the whole list (eg pizza-red-child or pizza-red-man)
• There are no duplicates, so if selected section 1 contains one combination I don't want any other set to include it
• The selected sections need to have a certain minimum size (as defined as element count 1 * count 2 * etc)
• I need to have a minimum number of selected sections

Now the trivial solution is of course, say you had to split this list in 4 for 4 workers (what I call a selected section above), just send every combination starting with pizza to worker 1, pasta to 2 and so on. But that doesn't work if you have more workers than elements in your longest list, and things get complicated.

Edit - Example

So the goal is given the list, find all combinations. But you need to split the main job into more machines.

The trivial solution explained above is, you have 4 elements in the longest list, just use 4 machines. In this case, it would look like this:

Machine 1:

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

Machine 2:

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

Machine 3:

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

Machine 4:

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

However this doesn't work if you have to split the work over more machines than the number of elements in the longest list. In that case, say you need to split the work over 8 machines (or 4 machines in two rounds per machine), it would have to look like this (I used 8 as it makes the example simpler, but the actual number is not that nice).

Machine 1:

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

Machine 2:

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

Machine 3:

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

Machine 4:

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

Machine 5:

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

Machine 6:

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

Machine 7:

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

Machine 8:

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

As you can see that's a way to split the original list whose max element is 4 into 8 machines. The question is, how to programmatically do that, when you can't control the number of machines/number of elements in the list?

Answer 1

if there was 1 worker, it would go in the order:

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

If you have more workers, split by range. e.g. Worker1 gets "pizza red child" - "pizza blue child". Worker 2 gets "pizza blue man" - "pasta red adult" , etc.

#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

If I get it right, maybe you can try replacing elements that you pick in your selected sections. For example;

pizza - red - child

then;

pasta - red - child

. . .

and so on...

so instead of creating new selected sections for every possible combination, you can try to manipulate one selected section for every possible combination once you are done with it.