Given n and a particular permutation s, find the next permutation in lexicographic order of elements 1-n (python)

Question

For example, suppose we have NextInOrder(10,(1,2,4,7)), then with these two as inputs for the function, I wish to write a python function that returns (1,2,4,8) by finding the next permutation in lexicographic order where elements of the permutation are in the range 1-10

So as another example NextInOrder(10, (5,3,2,10)) would return (5,3,4,1)

Answer 1

You can use a digit counter approach starting from the last position. Increase the last position to a value not in the previous positions. Backtrack to previous position(s) when the next value is out of range.

For example:

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)

output:

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

Answer 2

You could use 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)

Demo:

>>> NextInOrder(10,(1,2,4,7))
(1, 2, 4, 8)
>>> NextInOrder(10, (5,3,2,10))
(5, 3, 4, 1)