Python Implementation For Next_permutation In STL

next_permutation is a C++ function which gives the lexicographically next permutation of a string. Details about its implementation can be obtained from this really awesome post. h

Solution 1:

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.

Solution 2:

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.

Solution 3:

itertools is seems to be what you need.

Solution 4:

An implementation for the lexicographic-ally next permutation in Python (reference)

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

Solution 5:

A verbose implementation of this approach on lexicographic ordering

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