C++ STL Next Permutation with Combination

Question

I know that I can use std::next_permutation on some container containing the elements [1, 2, 3] which would generate 6 permutations of this sequence. What I would like to do is given some set [1, 2, 3, 4, 5, 6] generate all possible permutations of size 3. So for this example, [4, 3, 2] would be one of the permutations resulting from this criteria. I'm looking for an STL way of doing this (if possible) rather than writing my own combinations function. Any particular STL implementation I should be reading about ?

Answer 1

There is currently (as of 2016) no single STD function to do that. The closest you have is the proposal from http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2639.pdf

The function you want is called next_partial_permutation and looks like (from N2639):

template  <class  BidirectionalIterator >
bool next_partial_permutation(
  BidirectionalIterator  first ,
  BidirectionalIterator  middle ,
  BidirectionalIterator  last)
{
  std::reverse(middle , last);
  return std::next_permutation(first , last);
}

Answer 2

This is not the most efficient possible algorithm but it's easy. You must start with the elements sorted. To get the next k-permutation, reverse the last n-k elements and then try to get the next permutation. The first k elements are the next k-permutation.