Python实现STL中的next_permutation

Question

next_permutation 是一个 C++ 的函数，它可以给出一个字符串的字典序下一个排列。关于它的具体实现，可以参考这篇非常棒的文章。http://wordaligned.org/articles/next-permutation

1. 有没有人知道在 Python 中有没有类似的实现？
2. Python 有没有和 STL 迭代器直接对应的东西？

Answer 1

itertools 看起来正是你需要的东西。

Answer 2

这里有一个简单的Python 3实现，使用的是维基百科上关于生成字典序排列的算法：

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()是一样的，不过如果没有更多的排列，它不会把输入转换成字典序的第一个排列。

Answer 3

1. itertools.permutations 这个工具很接近你想要的，最大的不同是它把所有的项目都当作独特的，而不是进行比较。它也不会直接修改原来的序列。用Python实现 std::next_permutation 可能是个不错的练习（可以在列表上用索引，而不是随机访问的迭代器）。

2. 不可以。Python的迭代器可以和输入迭代器相比，这是一种STL（标准模板库）分类，但这只是冰山一角。你必须使用其他的结构，比如可调用的输出迭代器。这就打破了C++迭代器那种优雅的语法通用性。