C++ STL Следующая перестановка с комбинацией

Question

Я знаю, что я могу использовать std::next_permutation на некотором контейнере, содержащем элементы [1, 2, 3] который будет генерировать 6 перестановок этой последовательности. То, что я хотел бы сделать, это дать некоторый набор [1, 2, 3, 4, 5, 6] генерировать все возможные перестановки размера 3. Так что для этого примера [4, 3, 2] будет одной из перестановок, вытекающих из этого критерия. Я ищу STL способ сделать это (если это возможно), а не писать свою собственную функцию комбинации. О какой-то конкретной реализации STL, о которой я должен читать?

Answer 1

В настоящее время (по состоянию на 2016 год) нет единой функции STD для этого. Самое близкое у вас есть предложение от http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2639.pdf

Функция, которую вы хотите, называется next_partial_permutation и выглядит так (из 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

Это не самый эффективный алгоритм, но он прост. Вы должны начать с отсортированных элементов. Чтобы получить следующую k-перестановку, поменяйте местами последние nk элементов и затем попытайтесь получить следующую перестановку. Первые k элементов являются следующей k-перестановкой.

Answer 3

Вот алгоритм, написанный на Smalltalk.

Идея алгоритма состоит в том, чтобы рассмотреть лексикографический порядок массивов длины m с элементами между 1 а также n, Учитывая любой такой array, метод next заменяет array с его следующей частичной перестановкой в ​​указанном порядке.

Я создал класс с тремя переменными экземпляра

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

Метод создания экземпляра m:n: работает следующим образом

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

В этом классе метод next модифицирует array так что теперь он будет содержать следующую перестановку.

Возможно, стоит упомянуть, что алгоритм не является рекурсивным.

Метод next ответы с nil тогда и только тогда array содержит последнюю перестановку в порядке (т.е. array = (n, n-1, ...., n-m+1),

Чтобы вычислить все перестановки, начните с array = (1 ... m) и отправить next пока ответ 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]]

куда

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