Generate all unique combinations of 0-9 for X amount of digits

Question

I'm having trouble coming up with logic to generate all the possible unique combinations of 0-9 for X amount of digits.

For example, if I wanted all the unique combinations for a total of 5 digits, it would generate them using 0-9. (01234, 01235, etc.)

If you have any easy and creative solutions to my question, I would love to hear them. I have to implement it in MASM, but any solutions using C++ should not be an issue.

Combinations or permutations? Maybe you are looking for [std::next_permutation](https://en.cppreference.com/w/cpp/algorithm/next_permutation) ? — Jesper Juhl, Jun 15 '18 at 15:54
@Sani: Oh wait, [Generating permutations of a set (most efficiently)](https://stackoverflow.com/q/11208446) is *permutations*, and the OP here is asking for *combinations*. So not an exact duplicate, but it does have explicit algorithms for next_permutation that you could implement in asm. I haven't looked into this problem in enough detail, but Jarod's answer appears to be a way to get combinations given a permutation algo. (IDK if I should reopen this right away, or leave it to edit into another dup target; sorry I should have read more carefully the first time.) — Peter Cordes, Jun 15 '18 at 16:09
@Richard: found a duplicate for the combinations part, too. Printing every *sorted* permutation does the trick, done by permuting true/false values. You may want to implement it with an array of bytes instead of a packed bitmap (like actual `vector`). Then if you want to do it the fun way, use that bitmap with SSSE3 `pshufb` or bmi2 `pdep` to left-pack the integers. Maybe you can adapt [AVX2 what is the most efficient way to pack left based on a mask?](https://stackoverflow.com/q/36932240) for bytes instead of 32-bit int, if you have a machine with BMI2. Otherwise use a scalar loop! — Peter Cordes, Jun 15 '18 at 18:20

score 0 · Answer 1 · answered Jun 15 '18 at 16:00

In C++, you may use something like that:

template <typename T>
void Combination(const std::vector<T>& v, std::size_t count)
{
    assert(count <= v.size());
    std::vector<bool> bitset(v.size() - count, 0);
    bitset.resize(v.size(), 1);

    do {
        for (std::size_t i = 0; i != v.size(); ++i) {
            if (bitset[i]) {
                std::cout << v[i] << " ";
            }
        }
        std::cout << std::endl;
    } while (std::next_permutation(bitset.begin(), bitset.end()));
}

Demo

Generate all unique combinations of 0-9 for X amount of digits

1 Answers1