c++ combinatorics

Question

I need c++ code which will generate all possible combinations (n,k) with repitions where n - num of integers in the input array. k - num of positions

for example Input:

n = [1 2 3];
k = 2;

Output:

Thanks.

i have found code for combinations without repitions, of course it is possible to edit this code, or maybe even to code from scratch. But i search for quick solution, may be implemented in some kind of standard library, i don't want to dig into the implementation details. — Alex Hoppus, Apr 07 '12 at 12:13
did you search on stack overflow ? I found this which seems to be what you want : http://stackoverflow.com/questions/9430568/generating-combinations-in-c — , Apr 07 '12 at 12:48

Hauleth · Answer 1 · 2020-06-16T17:11:55.883

3

Use standard library:

do {
    for(int i = 0; i < k; i++){
        std::cout << n[i];
    }
    std::cout << '\n';
} while (std::next_permutation(n, n + k));

edited Jun 16 '20 at 17:11

answered Apr 07 '12 at 13:16

Hauleth

22,873
4
61
112

@Rahat.Zamhan what is not working? It worked for me. Can you give an example of code where it doesn't work as expected? – Hauleth Jun 09 '20 at 11:43
You are not initializing the variable `i`. – Rahat Zaman Jun 12 '20 at 07:44

Anthales · Answer 2 · 2012-04-07T14:49:55.377

1

This is basically counting in base n-1 (where every digit is shifted by 1), try the following:

Edit: Used vector instead of new[], delete[]

#include <vector>

void generatePerms(int n, int k)
{
    vector<int> perms(k, 1);

    //iterate through all permutations
    bool done;
    do {
        //Do something with the current permutation, for example print it:
        for (int i = 0; i < k-1; i++)
            cout << perms[i] << ", ";
        cout << perms[k-1] << endl;

        /*
         * Increment last digit first - if it's to big, reset to 1 and
         * carry one (increment next digit), which may also carry one etc.
         *
         * If all digits caused a carry, then the permutation was n, n, ..., n,
         * which means, that we can stop.
         */
        done = true;
        for (int i = k-1; i >= 0; i--) {
            if (++perms[i] > n) {
                perms[i] = 1;
                continue;
            } else {
                done = false; //not all digits caused carry
                break;
            }
        }
    } while (!done);
}

edited Apr 07 '12 at 14:49

answered Apr 07 '12 at 12:50

Anthales

1,158
6
10

@DeadMG Could you explain why this is bad and what should be done instead? – Anthales Apr 07 '12 at 13:35
@DeadMG Because you can't use `int perms[k]` when `k` is not constant (C++ doesn't have VLAs) and using `vector` for this is overkill. Also working inplace is arguably also not desireable - Sorry, but I don't get your downvote :/ – Anthales Apr 07 '12 at 13:46
@Anthales, `new[]` and `delete[]` are NEVER better than `std::vector`, which is used even in code that requires to execute fast and without much overhead. – Griwes Apr 07 '12 at 13:54
@Griwes Hm.. I think I got your point; `vector` will automatically clean up after itself, even when (_especially_ when) an exception is raised. Coming from Java and C it still doesn't feel "right" to me to use vector for _everything_, especially in very small code pieces like this, where errors can be spotted with a single glimpse. – Anthales Apr 07 '12 at 14:42
@Anthales, but it doesn't really cost you anything. And `vector` is both superior to both VLAs and dynamic arrays and is there just to be used, even in very small code pieces like this... – Griwes Apr 07 '12 at 15:03
@Griwes Yes, I agree with you, even the method calls can (and will) be optimized out by a good compiler and the dependency is really small. I edited my answer and probably won't do it again - But I'm still bugged about the -2 rep for a working solution.. – Anthales Apr 07 '12 at 15:17

score 1 · Accepted Answer · edited May 23 '17 at 11:47

1

See my answer here :

PHP take all combinations

It's PHP; but the concept (recursion, etc) should be easily "translateable"...

edited May 23 '17 at 11:47

Community

1
1

answered Apr 07 '12 at 12:56

Dr.Kameleon

22,532
20
115
223

c++ combinatorics

3 Answers3