Generates the permutations and sign of a sequence by constructing a tree

where the nth level contains all n-permutations of m (n < m) objects.

At the last level where n == m all permutations are generated. The sign is kept updated by determining where the next number is inserted into the current leaf's set of numbers.


Constructing the permutations of the sequence [A, B, C] constructs the following tree:

[[(A, +1)], [(AB, +1), (BA, -1)], [(ABC, +1), (ACB, -1), (CAB, +1], [(BAC, -1), (BCA, +1), (CBA, -1)]]

seq a sequence of a string to provide permutations

returns: a permutation list with the elements of the seq permuted and a sign associated with the permutation.