Permutations and next permutation

A permutation is one ordering of a list’s items, and n different items have n! permutations: 24 for four items, 3,628,800 for ten. Listing all permutations places the items one position at a time, as a backtracking search. The next permutation of an ordering is the one right after it in sorted order. It can be found in place, in O(n) time, without listing any others. Four tools cover the family. Used flags mark which items are already placed. Swaps keep the unplaced items inside the list itself. A skip rule stops equal values from being tried twice at one position. Dividing by factorials builds the k-th permutation directly.

Two problems about orderings

Problem A: every seating. Write seatings(guests, pair), which lists every order of the guests in a row of seats in which the two guests of pair sit side by side. Limits: n ≤ 9. For guests A, B, C and D with the pair A and B, 12 of the 24 orders qualify, from ABCD to DCBA. A variant lists the distinct orderings of values that repeat. Their number is n! divided by the orderings of each group of equal values: toffee has 6! / (2! × 2!) = 180.

Problem B: the next code. A display shows a code of n digits. Its next code is the smallest code larger than it that uses exactly the same digits; after the largest comes the smallest. Rearrange the digits in place, with O(1) extra memory. Limits: 1 ≤ n ≤ 10⁵.

• 534976 becomes 536479.
• 4321 becomes 1234: it was the largest.
• 1155 becomes 1515, with repeated digits.

The brute force, and why it fails

Try every ordering. For A, keep those where the pair sits together. For B, keep the smallest ordering above the code, which is its next permutation:

"""Both problems by brute force: try every ordering, then keep what the problem asks for."""
import math
import time
from itertools import permutations


def next_code_brute(code):
    """The smallest ordering of the digits that is larger than code; after the largest comes the smallest."""
    current = tuple(code)
    larger = (p for p in permutations(code) if p > current)  # every ordering of the positions: n! of them
    best = min(larger, default=None)
    return "".join(best if best is not None else sorted(code))


def seatings_brute(guests, pair):
    """Every seating order in which the two guests of pair sit side by side."""
    a, b = pair
    return ["".join(p) for p in permutations(guests) if abs(p.index(a) - p.index(b)) == 1]


print(next_code_brute("534976"), next_code_brute("4321"), next_code_brute("1155"))
orders = seatings_brute("ABCD", ("A", "B"))
print(f"{len(orders)} of {math.factorial(4)} seating orders keep A and B together: {' '.join(orders)}")

print("digits  orderings tried  time")
for code in ["31415926", "314159265", "3141592653"]:
    start = time.perf_counter()
    next_code_brute(code)
    seconds = time.perf_counter() - start
    print(f"{len(code):>6} {math.factorial(len(code)):>16,}  {seconds:.2f} s")
print(f"12 digits: {math.factorial(12):,} orderings; 20 digits: {math.factorial(20):,}")

536479 1234 1515
12 of 24 seating orders keep A and B together: ABCD ABDC BACD BADC CABD CBAD CDAB CDBA DABC DBAC DCAB DCBA
digits  orderings tried  time
     8           40,320  0.00 s
     9          362,880  0.17 s
    10        3,628,800  1.72 s
12 digits: 479,001,600 orderings; 20 digits: 2,432,902,008,176,640,000

Each digit multiplies the work: 10 digits take seconds, 12 digits need 479,001,600 orderings and 20 digits need 2.4 × 10¹⁸. At 10⁵ digits the brute force cannot even start. For A it is acceptable, because the answer itself has tens of thousands of orderings at 9 guests, but it still builds every ordering before checking the pair.

What to notice

Read the code from the right. While the digits never increase, the suffix is already the largest order of its own digits, so rearranging it alone cannot give a larger code. The change must happen at the first digit, from the right, that is smaller than the digit after it. For A, a guest of the pair whose two neighbouring seats are taken by others can never sit by its partner, so that branch can stop at once.

Next permutation in four steps, with a dry run Pro: opens with a Pro, Premium or Ultimate pass