##
# 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)]