Iterating through all possible combinations

Question

My objective is to iterate through all combinations of a given amount of 1's and 0's. Say, if I am given the number 5, what would be a sufficiently fast way to list

1110100100, 1011000101, etc. (Each different combination of 5 1's and 5 0's)

I am attempting to avoid iterating through all possible permutations and checking if 5 1's exist as 2^n is much greater than (n choose n/2). Thanks.

UPDATE

The answer can be calculated efficiently (recurses 10 deep) with:

// call combo() to have calculate(b) called with every valid bitset combo exactly once
combo(int index = 0, int numones = 0) {
    static bitset<10> b;
    if( index == 10 ) {
        calculate(b); // can't have too many zeroes or ones, it so must be 5 zero and 5 one
    } else {
        if( 10 - numones < 5 ) { // ignore paths with too many zeroes
            b[index] = 0;
            combo(b, index+1, numones);
        }
        if( numones < 5 ) { // ignore paths with too many ones
            b[index] = 1;
            combo(b, index+1, numones++);
        }
    }
}

(Above code is not tested)

I have to use them, but if I can list them that's fine because I can simply replace wherever cout is with the functions I plan on executing on each of them. — Nicholas Pipitone, Apr 05 '15 at 17:59

score 0 · Accepted Answer · answered Apr 05 '15 at 18:08

0

You can transform the problem. If you fix the 1s (or vice versa) then it's simply a matter of where you put the 0s. For 5 1s, there are 5+1 bins, and you want to put 5 elements (0s) in the bins.

This can be solved with a recursion per bin and a loop for each bin (put 0...reaming elements in the bin - except for the last bin, where you have to put all the remaning elements).

answered Apr 05 '15 at 18:08

Karoly Horvath

94,607
11
117
176

Old question, I don't even remember asking it, but this is definitely the correct answer so I'll mark it as so. I probably didn't mark it before because this answer seems like it would've been rather confusing for me 3 years ago. For those interested, the algo would be: perm(bitset<10> b, int index) { if( index == 10 ) { calculate(b); } else { b[index] = 0; perm(b, index+1); b[index] = 1; perm(b, index+1); } } b can be global for better performance. – Nicholas Pipitone Jul 18 '18 at 19:23
Er, that's permutations, didn't pay attention to my own question. only call `b[index] = 1; perm...` if the number of ones is < 5, and verify that the final calculate has the proper amount of ones. SO messed up the formatting so i'll put it in my question. – Nicholas Pipitone Jul 18 '18 at 19:32

score 0 · Answer 2 · edited May 23 '17 at 12:28

0

Another way to think about it is as a variant of the the string permutation question - just build a vector of length 2n (e.g. 111000) and then use the same algorithm for string permutation to build the result.

Note that the naive algorithm will print duplicate results. However, the algorithm can be easily adapted to ignore such duplicates by keeping a bool array in the recursive function that keeps the values set for the specific bit.

edited May 23 '17 at 12:28

Community

1
1

answered Apr 05 '15 at 18:13

Amnon Shochot

8,998
4
24
30

The duplicates are the problem because there are going to be millions of duplicates for high enough 'n', but without duplicates the most that ever need checking are a few thousand (Assuming the n isn't extremely large, in my case it doesn't get that big). I'm not sure what bool array you want to implement, the for loops iterates too many times – Nicholas Pipitone Apr 05 '15 at 18:18
If all the characters (bit) had different values then the complexity of the algorithm would be (2n)!. However, this is definitely not the case here. In the optimized algorithm you choose a char (bit), fix it on the x'th place and remember that you used this bit. Then if you're choosing another char (bit) that was already used for this location then you simply return. Therefore, while this may not be the optimal algorithm for this question it's complexity is expected to be reasonable. – Amnon Shochot Apr 05 '15 at 18:24

Iterating through all possible combinations

2 Answers2