Реализация Python для следующей_перестановки в STL

Question

next_permutation - это функция C ++, которая дает лексикографически следующую перестановку строки.Подробности о его реализации можно получить из этого действительно удивительного поста.http://wordaligned.org/articles/next-permutation

1. Кто-нибудь знает о подобной реализации в Python?
2. Существует ли прямой эквивалент Python для итераторов STL?

Answer 1

1. itertools.permutations близко; самая большая разница в том, что он рассматривает все элементы как уникальные, а не сравнивает их. Это также не изменяет последовательность на месте. Реализация std :: next_permutation в Python может оказаться для вас хорошим упражнением (используйте индексацию по списку, а не итераторы с произвольным доступом).

2. Нет. Итераторы Python сравнимы с входными итераторами, которые относятся к категории STL, но являются лишь верхушкой этого айсберга. Вместо этого вы должны использовать другие конструкции, например, вызываемый для выходного итератора. Это нарушает красивую синтаксическую общность итераторов C ++.

Answer 2

Реализация следующей лексикографической перестановки в Python ( ссылка )

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

Answer 3

itertools - это то, что вам нужно.

Answer 4

Вот простая реализация 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 5

Подробная реализация этого подхода к лексикографическому упорядочению

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