C++ STL Next Permutation with Combination

问题:

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 ?

回答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);
}

回答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.

回答3:

Here is an algorithm written in Smalltalk.

The idea of the algorithm is to consider the lexicographic order of arrays of length m with elements between 1 and n. Given any such array, the method next replaces array with its next partial permutation in said order.

I've created a class with three instance variables

array       the current permutation of length m
m           the size of array
complement  the SortedCollection of integers not in array

The instance creation method m:n: works as follows

m: length n: limit
  m := length.
  array := (1 to: m) asArray.
  complement := (m + 1 to: limit) asSortedCollection

In this class the method next modifies the array so that it will now hold the next permutation.

It might be worth mentioning that the algorithm is not recursive.

The method next answers with nil iff array contains the last permutation in the order (i.e., array = (n, n-1, ...., n-m+1).

To compute all permutations start with array = (1 ... m) and send next until the answer is nil.

next
  | index max h a c |
  index := self lastDecreasingIndex.
  max := complement max.
  h := (index to: m) findLast: [:i | (array at: i) < max] ifAbsent: nil.
  h isNil
    ifTrue: [
      index = 1 ifTrue: [^nil].
      a := array at: index - 1.
      index to: m do: [:i | complement add: (array at: i)].
      c := complement detect: [:cj | a < cj].
      array at: index - 1 put: c.
      complement remove: c; add: a.
      index to: m do: [:i | array at: i put: complement removeFirst]]
    ifFalse: [
      h := h + index - 1.
      a := array at: h.
      c := complement detect: [:ci | a < ci].
      array at: h put: c.
      complement remove: c; add: a.
      h + 1 to: m do: [:i | complement add: (array at: i)].
      h + 1 to: m do: [:i | array at: i put: complement removeFirst]]

Where

lastDecreasingIndex
  | index |
  index := m.
  [(array at: index - 1) > (array at: index)] whileTrue: [
    index := index - 1.
    index = 1 ifTrue: [^1]].
  ^index