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:

defnext_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 permutationfor i inreversed(range(len(a) - 1)):
        if a[i] < a[i + 1]:
            break# foundelse:  # no break: not foundreturnFalse# no next permutation# Find the largest index j greater than i such that a[i] < a[j]
    j = next(j for j inreversed(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:])
    returnTrue

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)

deflexicographically_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) - 2whilenot (i < 0or a[i] < a[i+1]):
        i -= 1if i < 0:
        returnFalse# else
    j = len(a) - 1whilenot (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 sequencereturnTrue

Solution 5:

A verbose implementation of this approach on lexicographic ordering

defnext_permutation(case):
    for index inrange(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 priorif 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 == -1or   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 orderreturnFalse#EXAMPLE EXECUTIONSprint("===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))