Python实现在STL next_permutation

Question

next_permutation是一个C++函数,它按字典顺序给出字符串的下一个排列.有关其实现的详细信息可以从这个非常棒的帖子中获得.http://wordaligned.org/articles/next-permutation

1. 有人知道Python中的类似实现吗？
2. STL迭代器是否有直接的python等价物？

Answer 1

这是维基百科算法的一个简单的 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

它产生与std::next_permutation()在 C++ 中相同的结果，但如果没有更多排列，它不会将输入转换为按字典顺序排列的第一排列。

Answer 2

1. itertools.permutations关闭；最大的区别是它将所有项目视为唯一项，而不是将它们进行比较。它也不会就地修改序列。在Python中实现std :: next_permutation对您来说可能是一个好习惯（使用列表索引而不是随机访问迭代器）。

2. 不会。Python迭代器与输入迭代器相当，后者是STL类别，但仅是冰山一角。相反，您必须使用其他构造，例如输出迭代器的callable。这破坏了C ++迭代器良好的语法通用性。