给定 n 和一个特定的排列 s,按照元素 1-n (python) 的字典顺序找到下一个排列
Given n and a particular permutation s, find the next permutation in lexicographic order of elements 1-n (python)
例如,假设我们有NextInOrder(10,(1,2,4,7))
,那么用这两个作为函数的输入,我想写一个python函数,returns (1,2,4,8)
通过按字典顺序查找下一个排列,其中排列的元素在 1-10
范围内
另一个例子 NextInOrder(10, (5,3,2,10))
会 return (5,3,4,1)
您可以使用 itertools
:
from itertools import permutations
def NextInOrder(n, current):
perms = permutations(range(1, n+1), len(current))
for perm in perms:
if perm == current:
return next(perms)
演示:
>>> NextInOrder(10,(1,2,4,7))
(1, 2, 4, 8)
>>> NextInOrder(10, (5,3,2,10))
(5, 3, 4, 1)
您可以使用从最后一个位置开始的数字计数器方法。将最后一个位置增加到一个不在以前位置的值。当下一个值超出范围时,返回到先前的位置。
例如:
def nextPerm(N,P):
result = list(P) # mutable permutation
i = len(P)-1 # position to advance (start with last)
while i in range(len(P)): # advance/backtrack loop
result[i] += 1 # next value at position
if result[i] > N: # value beyond range
result[i]=0
i -= 1 # backtrack
elif result[i] not in result[:i]: # distinct values only
i += 1 # next position to advance
return None if i<0 else tuple(result)
输出:
P = (1,2,4,7)
while P:
P = nextPerm(10,P)
print(P)
(1, 2, 4, 8)
(1, 2, 4, 9)
(1, 2, 4, 10)
(1, 2, 5, 3)
(1, 2, 5, 4)
(1, 2, 5, 6)
(1, 2, 5, 7)
(1, 2, 5, 8)
(1, 2, 5, 9)
(1, 2, 5, 10)
(1, 2, 6, 3)
...
例如,假设我们有NextInOrder(10,(1,2,4,7))
,那么用这两个作为函数的输入,我想写一个python函数,returns (1,2,4,8)
通过按字典顺序查找下一个排列,其中排列的元素在 1-10
另一个例子 NextInOrder(10, (5,3,2,10))
会 return (5,3,4,1)
您可以使用 itertools
:
from itertools import permutations
def NextInOrder(n, current):
perms = permutations(range(1, n+1), len(current))
for perm in perms:
if perm == current:
return next(perms)
演示:
>>> NextInOrder(10,(1,2,4,7))
(1, 2, 4, 8)
>>> NextInOrder(10, (5,3,2,10))
(5, 3, 4, 1)
您可以使用从最后一个位置开始的数字计数器方法。将最后一个位置增加到一个不在以前位置的值。当下一个值超出范围时,返回到先前的位置。
例如:
def nextPerm(N,P):
result = list(P) # mutable permutation
i = len(P)-1 # position to advance (start with last)
while i in range(len(P)): # advance/backtrack loop
result[i] += 1 # next value at position
if result[i] > N: # value beyond range
result[i]=0
i -= 1 # backtrack
elif result[i] not in result[:i]: # distinct values only
i += 1 # next position to advance
return None if i<0 else tuple(result)
输出:
P = (1,2,4,7)
while P:
P = nextPerm(10,P)
print(P)
(1, 2, 4, 8)
(1, 2, 4, 9)
(1, 2, 4, 10)
(1, 2, 5, 3)
(1, 2, 5, 4)
(1, 2, 5, 6)
(1, 2, 5, 7)
(1, 2, 5, 8)
(1, 2, 5, 9)
(1, 2, 5, 10)
(1, 2, 6, 3)
...