CODEWITHSUNDEEP
c++algorithmpermutation
Arne
Arne

Reputation: 20245

Computing permutations using a number of elements

I am trying to generate all possible permutations of a set of elements. The order doesn't matter, and elements may be present multiple times. The number of elements in each permutation is equal to the total number of elements.

A basic recursive algorithm for computing permutations following the schema (as I am writing in C++, the code will look similar to it):

elems = [0, 1, .., n-1];    // n unique elements. numbers only exemplary.
current = [];               // array of size n
perms(elems, current, 0);   // initial call

perms(array elems, array current, int depth) {
    if(depth == elems.size) print current;
    else {
        for(elem : elems) {
            current[depth] = elem;
            perms(elems, current, depth+1);
        }
    }
}

Would produce a large number of redundant sequences, e.g.:

0, 0, .., 0, 0
0, 0, .., 0, 1    // this
0, 0, .., 0, 2
.  .  .   .  . 
.  .  .   .  .
0, 0, .., 0, n-1
0, 0, .., 1, 0    // is the same as this
.  .  .   .  .    // many more redundant ones to follow

I tried to identify when exactly generating values can be skipped, but have so far not found nothing useful. I am sure I can find a way to hack around this, but I am also sure, that there is a rule behind this which I just haven't managed to see.

Edit: Possible solution+

elems = [0, 1, .., n-1];       // n unique elements. numbers only exemplary.
current = [];                  // array of size n
perms(elems, current, 0, 0);   // initial call

perms(array elems, array current, int depth, int minimum) {
    if(depth == elems.size) print current;
    else {
        for(int i=minimum; i<elems.size; i++) {
            current[depth] = elems[i];
            perms(elems, current, depth+1, i);
        }
    }
}

Upvotes: 2

Views: 129

Answers (2)

Luc Berthiaume
Luc Berthiaume

Reputation: 316

Make your first position varies from 0 to n. Then make your second position to 1. Then make your first position varies from 1 to n. Then set second at 2 --> first from 2 to n and so on.

Upvotes: 2

Scott Hunter
Scott Hunter

Reputation: 49920

I believe one such rule is to have the elements in each sequence be in non-decreasing order (or non-increasing, if you prefer).

Upvotes: 2

Related Questions