Generating Permutations and Combinations

Next Permutation in Lexicographic Order

def next_permutation(arr):
    # Step 1: Find the longest non-increasing suffix
    i = len(arr) - 2
    while i >= 0 and arr[i] >= arr[i + 1]:
        i -= 1
    
    # Step 2: If the entire array is non-increasing, reverse it
    if i == -1:
        arr.reverse()
        return arr
 
    # Step 3: Find the smallest element in the suffix larger than arr[i]
    j = len(arr) - 1
    while arr[j] <= arr[i]:
        j -= 1
 
    # Step 4: Swap elements at i and j
    arr[i], arr[j] = arr[j], arr[i]
 
    # Step 5: Reverse the suffix starting at i+1
    arr[i + 1:] = reversed(arr[i + 1:])
    
    return arr

For example, if we want to generate the permutations of $1,2,3,4$. First we find the longest non-increasing suffix (with least length $2$). That is $3,4$. The smallest element in the suffix larger than $3$ is $4$, then we swap $3,4$ and reverse the elements after $4$ (that is $3$ itself). Then we get $1,2,4,3$

Now the longest non-increasing suffix is $2,4,3$. The smallest element in the suffix larger than $2$ is $3$, then we swap $2,3$ and we get $1,3,4,2$. Afterwards we reverse the elements $4,2$, and we get $1,3,2,4$

Next Combination in Lexicographic Order

def next_combination(arr, n, k):
    # Step 1: Find the rightmost element that can be incremented
    i = k - 1
    while i >= 0 and arr[i] == n - k + i:
        i -= 1
 
    # Step 2: If no such element exists, the current combination is the last one
    if i < 0:
        return None
 
    # Step 3: Increment this element
    arr[i] += 1
 
    # Step 4: Set all elements to the right to the smallest values possible
    for j in range(i + 1, k):
        arr[j] = arr[i] + j - i
    
    return arr

For example, if we want to find the next $4$-combination of $1,2,3,4,5,6$ after $1,2,5,6$. The rightmost element that can be incremented is $2$, so we get $1,3,5,6$. Then we need to set all the elements to the right to the smallest values possible, that is $1,3,4,5$