k permutation in c++

Question

I am trying to generate all k permutations of n values without repetition. For example, the permutations of 2 values from 3: 1, 2, 3

The answer is:

1, 2

1, 3

2, 1

2, 3

3, 1

3, 2

I am currently using next_permutation() from STL that generates all permutations. Also, I found a code to generate combinations of size k. Here is the code:

res = new vector<vector<int>>;

vector<int> a;

for(int i = 0; i < n; i++)
    a.push_back(i); 

do {
    vector<int> b;

    for(int i = 0; i < k; i++)
        b.push_back(a[i]);

    do {
        res->push_back(b);          
    } while(next_permutation(b.begin(), b.begin() + k));                

} while(next_combination(a.begin(), a.begin() + k, a.end()));

First, the function finds a new combination and then use next_permutation to generate all permutations of that specific subset.

This code is very time consuming. I wonder if there is better library to produce k permutation in c++ or not?

what is `next_combination`? Effectiveness of your code relies strongly on the effectiveness of this function. — Ivaylo Strandjev, Dec 18 '13 at 11:20
I found the function in the internet that correctly generates all the combinations (subsets) of size k from n. — Maryam, Dec 18 '13 at 11:24
You should be aware that the enumerated list that you are trying to print is of factorial time complexity. What is the size of N and K that you are looking at? — Abhishek Bansal, Dec 18 '13 at 11:25
@IvayloStrandjev It’s a standard library function (and it’s the wrong one for OP’s problem). — Konrad Rudolph, Dec 18 '13 at 11:26
@KonradRudolph really? Could you please send a link to it in the standard library documentation? I am pretty certain there is no such standard library function. — Ivaylo Strandjev, Dec 18 '13 at 11:27
@user2165341 why not make iteration through all the elements using `for`? — Math, Dec 18 '13 at 11:30
Here is the function that I am using. I do not think that it is from a standard library. [link](http://stackoverflow.com/questions/5095407/n-choose-k-implementation) http://stackoverflow.com/questions/5095407/n-choose-k-implementation — Maryam, Dec 18 '13 at 11:33

score 1 · Answer 1 · answered Dec 18 '13 at 11:37

1

The std::next_permutation library function generates the permutations in lexicographic order. It has a complexity of up to half the size of the list.

You can implement the code yourself using recursion. This is not efficient either since the number of such combinations is of factorial complexity. Moreover you run the risk of using up all your stack space.

void recurCombinations( vector<int> &soFar, vector<int> &remaining, int K ) {
  if ( soFar.size() == K ) {
    output( soFar );
    return;
  }

  for ( int j = 0; j < remaining.size(); j++ ) {
    vector<int> newRemaining( remaining );
    vector<int> newSoFar( soFar );
    newSoFar.push_back( remaining[ j ] );
    newRemaining.erase( newRemaining.begin() + j );
    recurCombinations( newSoFar, newRemaining, K );
  }

}

answered Dec 18 '13 at 11:37

Abhishek Bansal

12,589
4
31
46

Thank you for your code. It seems to be time consuming and there might be no better way to reduce complexity. I try both to find better one. – Maryam Dec 18 '13 at 11:46
1

@user2165341 let me point out that any solution will execute number of operations at least of the order of `choose(n, k) * k!` (i.e. in how many ways can we select k elements out of n). This means that k can not be very big(e.g. for `k = 30` you will perform at least `265252859812191058636308480000000` - far more than you will be able to execute in any reasonable time. – Ivaylo Strandjev Dec 18 '13 at 11:49
@AbhishekBansal I did not read your answer carefully. Sorry. I think it is a good solution – Ivaylo Strandjev Dec 18 '13 at 11:50
Yeah, I agree with you. However, in my problem, the k is very small (less than 5), but n is somehow big. So, the next_combination should be more efficient. – Maryam Dec 18 '13 at 11:55

k permutation in c++

1 Answers1