STL中next_permutation的Python实现

Question

next_permutation是一个C++函数，它可以给出字符串的字典序下一个排列。有关其实现的详细信息可以从这篇真正令人惊叹的文章中获得。http://wordaligned.org/articles/next-permutation

1. 是否有人知道Python中类似的实现？
2. 是否存在STL迭代器的Python等效版本？

- user277465

---

дёҚе»әи®®иҝҷж ·еҒҡпјҢдҪҶжӮЁеҸҜд»ҘдҪҝз”ЁCythonзј–еҶҷзҡ„next_permutationжү©еұ•жЁЎеқ—жқҘи°ғз”Ёstd::next_permutationпјҲиҝҷеҸҜиғҪеҜ№жөӢиҜ•/и°ғиҜ•еҫҲжңүз”ЁпјүгҖӮ - jfs

Answer 1

1. itertools.permutations 函数与它相似，但最大的区别在于它将所有项视为唯一而不是比较它们。此外，它也不会就地修改序列。 在Python中实现 std::next_permutation 可以成为一个很好的练习（使用列表索引而不是随机访问迭代器）。

2. 不是。Python 迭代器类似于输入迭代器，这是 STL 的一种类别，但只是整个迭代器体系的冰山一角。您必须使用其他构造，例如用于输出迭代器的可调用对象。这打破了 C++ 迭代器的语法通用性。

- Fred Nurk

---

如果您能给我一个pastebin示例或示例链接，那就太好了。谢谢！ - user277465

你提到了其他构造，比如“输出运算符的可调用对象”。我想知道能否给我指出一些代码示例来演示你上面提到的设计模式。 - user277465

@zubin：我不知道有什么东西尝试单独传递一个callable（可调用对象）来举例说明，但你应该熟悉它，因为C++广泛使用functor（函数对象）。 - Fred Nurk

Answer 2

这是一个简单的Python 3实现wikipedia上生成字典序排列算法：

def next_permutation(a):
    """Generate the lexicographically next permutation inplace.

    https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
    Return false if there is no next permutation.
    """
    # Find the largest index i such that a[i] < a[i + 1]. If no such
    # index exists, the permutation is the last permutation
    for i in reversed(range(len(a) - 1)):
        if a[i] < a[i + 1]:
            break  # found
    else:  # no break: not found
        return False  # no next permutation

    # Find the largest index j greater than i such that a[i] < a[j]
    j = next(j for j in reversed(range(i + 1, len(a))) if a[i] < a[j])

    # Swap the value of a[i] with that of a[j]
    a[i], a[j] = a[j], a[i]

    # Reverse sequence from a[i + 1] up to and including the final element a[n]
    a[i + 1:] = reversed(a[i + 1:])
    return True

它与C++中的std::next_permutation()产生相同的结果，除了在没有更多排列的情况下，它不会将输入转换为词典顺序的第一个排列。

- jfs

---

当没有下一个排列时（例如，当a = ['b'，'a'，'a']时），它不会产生与std::next_permutation()相同的结果。 - tav

@tav 你是对的，维基百科算法与std::next_permutation有所不同（后者可能生成非字典序下一个排列：“aab”不是“baa”的下一个排列：从c++文档中得知：“否则将范围转换为字典上的第一个排列”）。两个函数均按照文档说明运行。 - jfs

值得注意的是，在return False之前添加a.reverse()可以实现与std::next_permutation()相同的行为。 - tav

Answer 3

itertools 看起来是你需要的工具。

- Kirill V. Lyadvinsky

Answer 4

Python中用于字典序下一个排列的实现 (参考)

def lexicographically_next_permutation(a):
    """
    Generates the lexicographically next permutation.

    Input: a permutation, called "a". This method modifies
    "a" in place. Returns True if we could generate a next
    permutation. Returns False if it was the last permutation
    lexicographically.
    """
    i = len(a) - 2
    while not (i < 0 or a[i] < a[i+1]):
        i -= 1
    if i < 0:
        return False
    # else
    j = len(a) - 1
    while not (a[j] > a[i]):
        j -= 1
    a[i], a[j] = a[j], a[i]        # swap
    a[i+1:] = reversed(a[i+1:])    # reverse elements from position i+1 till the end of the sequence
    return True

- Assem

Answer 5

在词典序排序方面，this方法的冗长实现

def next_permutation(case):
    for index in range(1,len(case)):
        Px_index = len(case) - 1 - index
        #Start travelling from the end of the Data Structure
        Px = case[-index-1]
        Px_1 = case[-index]

        #Search for a pair where latter the is greater than prior
        if Px < Px_1 :
            suffix = case[-index:]
            pivot = Px
            minimum_greater_than_pivot_suffix_index = -1
            suffix_index=0

            #Find the index inside the suffix where ::: [minimum value is greater than the pivot]
            for Py in suffix:
                if pivot < Py:
                    if minimum_greater_than_pivot_suffix_index == -1 or   suffix[minimum_greater_than_pivot_suffix_index] >= Py:
                        minimum_greater_than_pivot_suffix_index=suffix_index
                suffix_index +=1
            #index in the main array
            minimum_greater_than_pivot_index = minimum_greater_than_pivot_suffix_index + Px_index +1

            #SWAP
            temp = case[minimum_greater_than_pivot_index]
            case[minimum_greater_than_pivot_index] = case[Px_index]
            case[Px_index] = temp

            #Sort suffix
            new_suffix = case[Px_index+1:]
            new_suffix.sort()

            #Build final Version
            new_prefix = case[:Px_index+1]
            next_permutation = new_prefix + new_suffix
            return next_permutation
        elif index == (len(case) -1):
            #This means that this is at the highest possible lexicographic order
            return False



#EXAMPLE EXECUTIONS
print("===INT===")
#INT LIST
case = [0, 1, 2, 5, 3, 3, 0]
print(case)
print(next_permutation(case))


print("===CHAR===")
#STRING
case_char = list("dkhc")
case = [ord(c) for c in case_char]
print(case)
case = next_permutation(case)
print(case)
case_char = [str(chr(c)) for c in case]
print(case_char)
print(''.join(case_char))

- Dehan

Answer 6

该算法在模块more_itertools中实现，作为函数more_itertools.distinct_permutations的一部分：

• 文档;
• 源代码。

def next_permutation(A):
            # Find the largest index i such that A[i] < A[i + 1]
            for i in range(size - 2, -1, -1):
                if A[i] < A[i + 1]:
                    break
            #  If no such index exists, this permutation is the last one
            else:
                return

            # Find the largest index j greater than j such that A[i] < A[j]
            for j in range(size - 1, i, -1):
                if A[i] < A[j]:
                    break

            # Swap the value of A[i] with that of A[j], then reverse the
            # sequence from A[i + 1] to form the new permutation
            A[i], A[j] = A[j], A[i]
            A[i + 1 :] = A[: i - size : -1]  # A[i + 1:][::-1]

或者，如果序列保证只包含不同的元素，则可以使用模块more_itertools中的函数来实现next_permutation：

import more_itertools

# raises IndexError if s is already the last permutation
def next_permutation(s):
   seq = sorted(s)
   n = more_itertools.permutation_index(s, seq)
   return more_itertools.nth_permutation(seq, len(seq), n+1)

- Stef