C++ STL中的下一个排列与组合

Question

我知道可以在一些包含元素[1, 2, 3]的容器上使用std::next_permutation来生成6个排列。我想做的是给定一个集合[1, 2, 3, 4, 5, 6]，生成所有大小为3的可能排列。因此，对于此示例，[4, 3, 2]将成为符合此条件的排列之一。我正在寻找一种STL方法来完成这个任务（如果可能），而不是编写自己的组合函数。有任何特定的STL实现应该了解吗？

- Mutating Algorithm

---

https://dev59.com/9nVC5IYBdhLWcg3w-mVO - Alan Stokes

https://dev59.com/2mox5IYBdhLWcg3wGwpo - Alan Stokes

https://dev59.com/qGcs5IYBdhLWcg3wRB3h - Alan Stokes

@AlanStokes：所有那些问题都涉及组合；而这个问题是关于排列的。 - Nick Matteo

这是关于置换组合的问题。而且楼主知道如何进行置换，只需要找到组合。因此，“我正在寻找一种STL方法来完成这个任务[...]而不是编写自己的组合函数。” - Alan Stokes

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

- Mircea Baja

Answer 2

这不是最高效的算法，但它很简单。你必须从已排序的元素开始。要获取下一个k排列，请反转最后n-k个元素，然后尝试获取下一个排列。前k个元素是下一个k排列。

- rici

---

现在你这么说，似乎很明显，+1。 - Barry

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，使它现在保存下一个排列。

值得一提的是，该算法不是递归的。

如果array包含顺序中的最后一个排列（即array =（n，n-1，....，n-m + 1）），则方法next回答nil。

要计算所有排列，请从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]]

Where

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

- Leandro Caniglia