##
# Check if a permutation representation is really one.
#
# @param p A list meant to represent a permutation.
# @return True if p is really the representation of a permutation, false if not.
def check_permutation(p):
    n = len(p)
    c = [False for i in range(n)]
    valid = True

    i = 0
    while valid and i < n:
        if p[i] < 1 or p[i] > n or c[p[i] - 1]:
            valid = False
        else:
            c[p[i] - 1] = True
        i += 1

    return valid

##
# Decompose a permutation into disjoint cycles.
#
# @param p A list meant to represent a permutation.
# @pre `p` must represent a valid permutation.
# @return A list of lists, each representing a (disjoint with the respect to the
# others) cycle of p.
def disjoint_cycles(p):
    d = []
    n = len(p)
    treated = [False for i in range(n)]

    for i in range(n):
        if not treated[i]:
            cycle = [i + 1]
            treated[i] = True
            j = i
            while p[j] != cycle[0]:
                cycle.append(p[j])
                treated[p[j] - 1] = True
                j = p[j] - 1
            d.append(cycle)
                
    return d

##
# Compute the signature of a permutation.
#
# @param p A list meant to represent a permutation.
# @pre `p` must represent a valid permutation.
# @return An integer giving the signature of the permutation.
def signature(p):
    d = disjoint_cycles(p)
    parity = 0
    for c in d:
        parity = (parity + len(c) - 1) % 2

    if parity == 0:
        sig = 1
    else:
        sig = -1

    return sig

##
# Compute the lexicographically ordered list of all permutations of a given
# size.
#
# @param n The size of the permutations to consider.
# @pre `n` must be a positive integer.
# @return The list of all permutations on n, ordered lexicographically.
def list_of_permutations(n):
    return list_of_permutations_aux([i + 1 for i in range(n)])

##
# Compute the lexicographically ordered list of all permutations of a given set
# of elements.
#
# @param e The set of elements to consider.
# @pre `e` must be a list of ordered elements.
# @return The list of all permutations of the set e, ordered lexicographically.
def list_of_permutations_aux(e):
    l = []

    if len(e) == 1:
        l.append([e[0]])

    else:
        r = range(len(e))
        for i in r:
            head = e[i]
            del e[i]
            l_aux = list_of_permutations_aux(e)
            for p_aux in l_aux:
                p_aux.insert(0, head)
                l.append(p_aux)
            e.insert(i, head)

    return l

list_plot([(1, 18.8 * 10^-6), (2, 31.9 * 10^-6), (3, 31 * 10^-6),
           (4, 302 * 10^-6), (5, 1.17 * 10^-3), (6, 9.55 * 10^-3),
           (7, 67.8 * 10^-3), (8, 184 * 10^-3), (9, 1.4), (10, 17.9)],
          plotjoined=true, scale="semilogy")

##
# Get the lexicographically smallest permutation among two.
#
# @param p1 A first list meant to represent a permutation.
# @param p2 A second list meant to represent a permutation.
# @pre `p1` and `p2` must each represent valid permutations of the same size.
# @return p1 if it is lexicographically smaller than p2 (or equal to p2), p1
# otherwise.
def minlex(p1, p2):
    n = len(p1)

    i = 0
    while i < n and p1[i] == p2[i]:
        i += 1

    if i < n and p1[i] > p2[i]:
        p = p2
    else:
        p = p1

    return p

##
# Get the number of a permutation (according to the lexicographical order).
#
# @param p A list meant to represent a permutation.
# @pre `p` must represent a valid permutation.
# @return The number of p in the lexicographically ordered list of all
# permutations having the same size as p.
def numlex(p):
    n = len(p)
    rank = [i + 1 for i in range(n)]

    pos = 1
    for i in range(n - 1):
        r = rank.index(p[i])
        pos += factorial(n - (i + 1)) * r
        del rank[r]

    return pos

##
# Compute the successor of a permutation (according to the lexicographical
# order).
#
# @param p A list meant to represent a permutation.
# @pre `p` must represent a valid permutation.
# @return The successor of p for the lexicographical order, p if it is the
# greatest possible for its size.
def succlex(p):
    n = len(p)

    found = False
    for i in range(n - 1):
        if p[i] < p[i + 1]:
            found = True
            k = i

    if found:
        pivot = p[k]
        s = p[:k + 1]
        tail = p[k + 1:]
        i = len(tail) - 1
        while pivot > tail[i]:
            i -= 1
        s[k] = tail[i]
        tail[i] = pivot
        tail.reverse()
        s = s + tail

    else:
        s = p

    return s

##
# Compute the predecessor of a permutation (according to the lexicographical
# order).
#
# @param p A list meant to represent a permutation.
# @pre `p` must represent a valid permutation.
# @return The predecessor of p for the lexicographical order, p if it is the
# smallest possible for its size.
def predlex(p):
    n = len(p)

    found = False
    for i in range(n - 1):
        if p[i] > p[i + 1]:
            found = True
            k = i

    if found:
        pivot = p[k]
        s = p[:k + 1]
        tail = p[k + 1:]
        i = len(tail) - 1
        while pivot < tail[i]:
            i -= 1
        s[k] = tail[i]
        tail[i] = pivot
        tail.reverse()
        s = s + tail

    else:
        s = p

    return s

##
# Compute the number of fixpoints of a permutation.
#
# @param p A list meant to represent a permutation.
# @pre `p` must represent a valid permutation.
# @return The number of fixpoints of p.
def fix(p):
    n = len(p)
    nb_fixpoints = 0

    for i in range(n):
        if p[i] == i + 1:
            nb_fixpoints += 1

    return nb_fixpoints

##
# Compute the expected number of fixpoints in a uniform distribution over all
# permutations of a given size.
#
# @param n The size of the permutations to consider.
# @pre `n` must be a positive integer.
# @return The expected number of fixpoints in a permutation taken uniformly at
# random from the uniform distribution over all permutations of size n.
def expected_nb_fixpoints(n):
    l = list_of_permutations(n)
    s = 0

    for p in l:
        s += fix(p)

    return s / factorial(n)

##
# Compute the number of inversions of a permutation.
#
# @param p A list meant to represent a permutation.
# @pre `p` must represent a valid permutation.
# @return The number of inversions of p.
def inv(p):
    n = len(p)
    nb_inversions = 0

    for i in range(n):
        for j in range(i + 1, n):
            if p[j] < p[i]:
                nb_inversions += 1

    return nb_inversions

##
# Compute the expected number of inversions in a uniform distribution over all
# permutations of a given size.
#
# @param n The size of the permutations to consider.
# @pre `n` must be a positive integer.
# @return The expected number of inversions in a permutation taken uniformly at
# random from the uniform distribution over all permutations of size n.
def expected_nb_inversions(n):
    l = list_of_permutations(n)
    s = 0

    for p in l:
        s += inv(p)

    return s / factorial(n)

##
# Compute the inversion vector of a permutation.
#
# @param p A list meant to represent a permutation.
# @pre `p` must represent a valid permutation.
# @return The inversion vector of p.
def inversion_vector(p):
    n = len(p)
    inv_vect = [0 for i in range(n - 1)]
    encountered = [False for i in range(n)]

    for i in range(n - 1):
        for e in range(1, p[i]):
            if not encountered[e - 1]:
                inv_vect[e - 1] += 1
        encountered[p[i] - 1] = True

    return inv_vect

##
# Compute the list of inversion vectors of the lexicographically ordered list of
# all permutations of a given size.
#
# @param n The size of the permutations to consider.
# @pre `n` must be a positive integer.
# @return The list of all inversion vectors for all permutations on n (ordered
# lexicographically).
def list_of_inversions(n):
    return [inversion_vector(p) for p in list_of_permutations(n)]