Nested Loops: Lexicographic Permutations

Problem: Print the lexicographic permutations of a sequence.

Example: 

permutatations([1,2,2,3])

[1, 2, 2, 3]
[1, 2, 3, 2]
[1, 3, 2, 2]
[2, 1, 2, 3]
[2, 1, 3, 2]
[2, 2, 1, 3]
[2, 2, 3, 1]
[2, 3, 1, 2]
[2, 3, 2, 1]
[3, 1, 2, 2]
[3, 2, 1, 2]
[3, 2, 2, 1]

Solution in Python:


def permutatations(a):
    """
    Author: Mayur P Srivastava
    """

    n = len(a)

    # Add a degenerate element a0 less than an.
    tmp = sorted(a)
    a   = [tmp[-1] - 1]
    a.extend(tmp)

    while (True):
        # Step 1 [Visit]: Visit the permutation a1, a2, ..., an
        print a[1:]

        # Step 2 [Find j]:
        j = n - 1
        while j > 0 and a[j] >= a[j+1]:
            j = j - 1
        # If j is 0, terminate the algo.
        if j == 0:
            break

        # Step 3 [Increase aj]
        l = n
        while l > 0 and a[j] >= a[l]:
            l = l - 1
        a[j], a[l] = a[l], a[j] # Swap.

        # Step 4 [Reverse aj+1, aj+2, ..., an]
        k = j + 1
        l = n
        while k < l:
            a[k], a[l] = a[l], a[k]
            k = k + 1
            l = l - 1

Concepts Learned: Nested loops.