Python implementation for next_permutation in STL

1. itertools.permutations is close; the biggest difference is it treats all items as unique rather than comparing them. It also doesn't modify the sequence in-place. Implementing std::next_permutation in Python could be a good exercise for you (use indexing on a list rather than random access iterators).

2. No. Python iterators are comparable to input iterators, which are an STL category, but only the tip of that iceberg. You must instead use other constructs, such as a callable for an output iterator. This breaks the nice syntax generality of C++ iterators.

Here's a straightforward Python 3 implementation of wikipedia's algorithm for generating permutations in lexicographic order:

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

It produces the same results as std::next_permutation() in C++ except it doesn't transforms the input into the lexicographically first permutation if there are no more permutations.