#!/usr/bin/env python
# -*- coding: utf-8 -*-

import getopt
import sys
import time

def shift(listwise, shift=0):
    """ Rearranges entries within given list-wise object, either by moving
        the 'final' entry to the 'first' place, while shifting all other entries
        to the 'next' position.
    """
    if not isinstance(listwise, list):
        listwise = list(listwise)
    if shift == 0:
        return listwise[:]
    else:
        return listwise[shift:] + listwise[:shift]


def count(generated):
    """ Counts up 'truthy' object in the given generated list-wise object.
    """
    return len(filter(lambda x: x == True, generated))


def itermasks(auxiliary, residual):
    """ Iterates over all left-shifted objects generated by the given auxiliary
        list-wise object.
    """
    mask = []
    for length in auxiliary:
        mask += [True if i == length - 1 else False for i in range(length)]
    mask = mask + [False] * residual
    yield mask
    for amount in auxiliary:
        mask = shift(mask, amount)
        yield mask
    return


def search(length, residual, auxiliary, generated, sentinels=set()):
    """ Pseudo brute-force search, i.e., search with simple pruning.
    """
    if length <= 1:
        if (residual > 0) and (residual not in auxiliary):
            auxiliary.append(residual)
            cache = generated[:]
            for mask in itermasks(auxiliary, 0):
                generated = map(lambda x: x[0] or x[1], zip(generated, mask))
            if all(generated):
                sentinels.add(residual)
                print auxiliary
            auxiliary.remove(residual)
            generated = cache
        elif residual == 0 and all(generated):
            sentinels.add(auxiliary[len(auxiliary) - 1])
            print auxiliary
    else:
        rightmost = sum(auxiliary)
        for index in filter(lambda x: (x - rightmost + 1 not in auxiliary) and (generated[x] == False), range(rightmost, len(generated))):
            candidate = index - rightmost + 1
            if len(auxiliary) == 1 and candidate in sentinels:
                continue
            auxiliary.append(candidate)
            cache = generated[:]
            for mask in itermasks(auxiliary, residual - candidate):
                generated = map(lambda x: x[0] or x[1], zip(generated, mask))
            if count(generated) - count(cache) < 2 * len(auxiliary) - 1:
                auxiliary.remove(candidate)
                generated = cache
                continue
            search(length - 1, residual - candidate, auxiliary, generated, sentinels)
            auxiliary.remove(candidate)
            generated = cache
    return len(sentinels) > 0


def main(argv=None):
    """ Main routine.
    """
    if not argv:
        argv = sys.argv[1:]
    if argv:
        try:
            length = int(argv[0])
            if length <= 0:
                raise Exception()
            residual = length * (length - 1) + 1
            auxiliary = [1]
            generated = [True if i == 0 else False for i in range(residual)]
        except:
            print >>sys.stderr, "error: invalid argument"
            return
        start = time.clock()
        if not search(length - 1, residual - 1, auxiliary, generated):
            print "no solution found"
        end = time.clock()
        print "time elapsed: " + str(end - start) + " (sec)"
    else:
        print >>sys.stderr, "usage: clistsolver <list length>"
    return


if __name__ == '__main__':
    sys.exit(main())
