# For every integer n, this program finds the total number of
# permutations of the sequence (1, 1, 2, 2, ..., n, n) such that in each
# permutation, for each k, where 1 <= k <= n, there are k items between
# the locations of two k's in the permutation.
#
# This is a Python program. I have included comments to help programmers
# who know C but do not know Python.
#
# Author: Susam Pal
def arrange(n, solutions, s=None):
    # Main program does not pass an argument for s. So, if s is None,
    # then arrange() was not called by a recursive call. In this case
    # create a list with no symbols. 0 represents no symbol.
    if s is None:
        s = [0] * (n * 2) # A list full of zeroes of size 2n.

    # The symbol to be placed in two cells.
    m = max(s) + 1

    # Try to place symbol in ith and (i + m + 1)th cells of the list.
    for i in range(2 * n - m - 1):
        if s[i] == 0 and s[i + m + 1] == 0:
            # Create a copy of the list so that the original list that
            # this call received remains unaltered.
            s_copy = s[:]

            # Place the symbol in the pair of locations found.
            s_copy[i] = s_copy[i + m + 1] = m

            # If this symbol is the last symbol to be placed ...
            if m == n:
                # then a solution has been found.
                solutions.append(s_copy)
                return
            else:
                # else call itself to process the next symbol
                arrange(n, solutions, s_copy)
    return

# Call arrange() for every input size and find solutions.
if __name__ == '__main__':
    import time
    start_time = time.time()
    n = 1
    while True:
        solutions = [] 
        arrange(n, solutions)
        time_elapsed = time.time() - start_time
        print 'n = %2d : %10d solutions (%6.0f s)' % \
              (n, len(solutions), time_elapsed)
        n += 1