next_permutation是一个C++函数,它可以给出字符串的字典序下一个排列。有关其实现的详细信息可以从这篇真正令人惊叹的文章中获得。http://wordaligned.org/articles/next-permutation
- 是否有人知道Python中类似的实现?
- 是否存在STL迭代器的Python等效版本?
next_permutation是一个C++函数,它可以给出字符串的字典序下一个排列。有关其实现的详细信息可以从这篇真正令人惊叹的文章中获得。http://wordaligned.org/articles/next-permutation
itertools.permutations 函数与它相似,但最大的区别在于它将所有项视为唯一而不是比较它们。此外,它也不会就地修改序列。 在Python中实现 std::next_permutation 可以成为一个很好的练习(使用列表索引而不是随机访问迭代器)。
不是。Python 迭代器类似于输入迭代器,这是 STL 的一种类别,但只是整个迭代器体系的冰山一角。您必须使用其他构造,例如用于输出迭代器的可调用对象。这打破了 C++ 迭代器的语法通用性。
这是一个简单的Python 3实现wikipedia上生成字典序排列算法:
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()
产生相同的结果,除了在没有更多排列的情况下,它不会将输入转换为词典顺序的第一个排列。a = ['b','a','a']
时),它不会产生与std::next_permutation()
相同的结果。 - tavreturn False
之前添加a.reverse()
可以实现与std::next_permutation()
相同的行为。 - tavPython中用于字典序下一个排列的实现 (参考)
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
在词典序排序方面,this方法的冗长实现
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))
该算法在模块more_itertools
中实现,作为函数more_itertools.distinct_permutations
的一部分:
def next_permutation(A):
# Find the largest index i such that A[i] < A[i + 1]
for i in range(size - 2, -1, -1):
if A[i] < A[i + 1]:
break
# If no such index exists, this permutation is the last one
else:
return
# Find the largest index j greater than j such that A[i] < A[j]
for j in range(size - 1, i, -1):
if A[i] < A[j]:
break
# Swap the value of A[i] with that of A[j], then reverse the
# sequence from A[i + 1] to form the new permutation
A[i], A[j] = A[j], A[i]
A[i + 1 :] = A[: i - size : -1] # A[i + 1:][::-1]
或者,如果序列保证只包含不同的元素,则可以使用模块more_itertools
中的函数来实现next_permutation
:
import more_itertools
# raises IndexError if s is already the last permutation
def next_permutation(s):
seq = sorted(s)
n = more_itertools.permutation_index(s, seq)
return more_itertools.nth_permutation(seq, len(seq), n+1)
next_permutation
жү©еұ•жЁЎеқ—жқҘи°ғз”Ёstd::next_permutationпјҲиҝҷеҸҜиғҪеҜ№жөӢиҜ•/и°ғиҜ•еҫҲжңүз”ЁпјүгҖӮ - jfs