Le but de ce TP est d'implanter les différents algorithmes combinatoires que nous avons vus en cours dans le cas des permutations.
Les permutations d'un ensemble $S$ sont toutes les façons de lister les éléments de $S$. Par exemple, voici les permutations de l'ensemble $\lbrace 1, 2, 3 \rbrace$ :
$123, 132, 213, 231, 312, 321$.
Et voici les permutations de $\lbrace 1,1,2 \rbrace$ :
$112, 121, 211$.
On s'intéresse d'abord au cas où tous les éléments de $S$ sont distincts.
Dans la fonction qui suit, on vous demande d'engendrer récursivement les permutations de $\lbrace 1, \dots n \rbrace$. L'ordre dans lequel on obtient les permutatiosn n'a pas d'improtance. Comme dans le TP précédent, vous utiliserez un générateur à l'aide de l'instruction python yield.
Essayez de trouver seul l'algorithme, si vous êtes bloqués, vous pouvez consulter le fichier TP2_SOILER_ALERT, Indication 1.
In [4]:
# Rappel manipulation de liste en python
# liste vide
lvide = []
lvide
In [5]:
# liste à un élément
l1 = [3]
l1
In [6]:
# concaténation de liste
l = [2,2,1] + l1 + [1,2]
l
In [7]:
# Rappel python, copier un morceau de liste
# l[a:b] retourne la liste l entre l'indice a (inclus) et l'indice b (exclus)
l = [1,2,3,4]
In [8]:
l[:] # copie de toute la liste
In [9]:
l[:0] # copie de rien du tout
In [10]:
l[:1]
In [11]:
l[:3]
In [12]:
l[1:3]
In [13]:
l[1:]
In [14]:
l[2:]
In [18]:
def permutations(n):
"""
Return a generator on standard permutations of size n (permutations of {1, ...n})
Input:
- n, a non negative integer
"""
# écrire le code ici
In [ ]:
In [ ]:
In [20]:
# tests
assert list(permutations(0)) == [[]]
assert list(permutations(1)) == [[1]]
P2 = list(permutations(2))
P2.sort()
assert P2 == [[1,2],[2,1]]
P3 = list(permutations(3))
P3.sort()
assert P3 == [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
assert len(list(permutations(4))) == 24
In [ ]:
On souhaite à présent engendrer les permutations dans l'ordre lexicographique, est-ce le cas de votre algorithme ? Sans doute pas...
In [21]:
list(permutations(3)) == [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
False -> j'avais raison...
True -> Dans ce cas, soit vous conservez la liste des permutations de taille $n-1$, soit vous les engendrez plusieurs fois.
Dans tous les cas, écrivez la fonction suivante. Cette fois, elle prend en argument la liste des nombres à permuter (et non plus seulement le nombre $n$) et engendre les permutations de ces nombres en ordre lexicographique.
Aide : TP2_SPOILER_ALERT Indication 2
In [22]:
def permutations_lex(s):
"""
Return a generator on permutations of the set s in lexicographic order
INPUT:
- s, a list of distinct integers in lexicographic order
"""
# écrire le code ici
In [23]:
list(permutations_lex([1,2,3]))
In [24]:
# tests
assert list(permutations_lex([])) == [[]]
assert list(permutations_lex([1])) == [[1]]
assert list(permutations_lex([2])) == [[2]]
assert list(permutations_lex([1,2])) == [[1,2],[2,1]]
assert list(permutations_lex([2,3])) == [[2,3],[3,2]]
assert list(permutations_lex([1,2,3])) ==[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
P4 = list(permutations_lex([1,2,3,4]))
P4.sort()
assert P4 == list(permutations_lex([1,2,3,4]))
La fonction rank donne le numéro de la permutation dans la liste (en partant de 0). Aide : TP2_SPOILER_ALERT Indication 3
La fonction unrank donne la permutation qui a le numéro demandé. Aide : TP2_SPOILER_ALERT Indication 4
Remarque : La méthode qui consiste à engendrer la liste jusqu'à l'indice ou la permutation recherchée n'est pas acceptable. On veut des algorithmes dont la complexité est linéaire en fonction de la taille de la liste $s$.
On travaille toujours avec l'ordre lexicographique.
In [25]:
# Si besoin, vous pouvez utiliser la fonction suivante
import math
math.factorial(4)
In [26]:
# rappel python, l'indice d'un élément dans une liste
l = [2,3,1]
l.index(3)
In [27]:
import math
def rank(s,p):
"""
Return the rank of the permutation p among permutations of the set s in lex order
INPUT:
- s, the list of permuted values in lex order
- p, a permutation of s
OUTPUT: an integer between 0 and the number of permutations of s
"""
# écrire le code ici
In [28]:
rank([1,2,3],[1,2,3])
In [30]:
# des tests sur des petites permutations
assert rank([1,2,3],[1,2,3]) == 0
assert rank([1,2,3],[3,2,1]) == 5
assert rank([1,2,3],[1,3,2]) == 1
assert rank([2,3,4],[2,4,3]) == 1
assert [rank([1,2,3,4],p) for p in permutations_lex([1,2,3,4])] == list(range(24))
In [34]:
# maintenant on vérifie que votre algorithe est un peu efficace et que vous n'engendrez pas toutes les permutations !
assert rank([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],[15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]) == math.factorial(15)-1
assert rank([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],[12,11,3,10,2,15,5,1,13,7,9,8,14,6,4]) == 1022515728089
In [35]:
import math
def unrank(s,i):
"""
Return the permutation with rank i in the list of permutations of the set s in lex order
INPUT:
- s, the list of permuted values
- i, the rank of the permutation
OUTPUT : a permutation
"""
# écrire le code ici
In [36]:
unrank([1,2,3],0)
In [38]:
# tests sur de petites permtuations
assert unrank([1,2,3],0) == [1,2,3]
assert unrank([1,2,3],5) == [3,2,1]
assert unrank([1,2,3],1) == [1,3,2]
assert unrank([2,3,4],1) == [2,4,3]
assert [unrank([1,2,3,4],i) for i in range(24)] == list(permutations_lex([1,2,3,4]))
In [39]:
# tests sur des permtuations plus grosse
assert unrank([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15], math.factorial(15)-1) == [15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]
assert unrank([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15], 1022515728089) == [12,11,3,10,2,15,5,1,13,7,9,8,14,6,4]
Nous allons maintenant implanter une classe pour représenter l'ensemble des permutations d'un ensemble de valeurs donné. Pour l'instant, on suppose toujours que les valeurs sont toutes distinctes.
On vous donne la structure de l'objet, on a implanté les méthodes de base et il vous reste les autres. Pour les méthodes __iter__, rank et unrank il faut simplement reprendre le code que vous avez écrit plus tôt et l'adapter à l'écriture objet. Il vous reste la méthode next et la méthode random_permutation.
Remarque méthode random_element: il est possible d'écrire la méthode random_permtuation d'une façon générique qui n'utilise pas le fait que l'on travaille sur des permutations mais simplement les autres méthodes de la classe.
Remarque méthode next : là aussi, il est possible d'écrire un algorithme générique, cependant vous pouvez aussi chercher l'algorithme direct.
Remarque python Observez la syntaxe de la classe et les exemples ci-dessous pour en comprendre le fonctionnenment. Les méthodes qui commencent par un double underscore __ sont des méthodes spécilaes pour les objets python :
__init__ : la méthode d'initialisation de l'objet__repr__ : la méthode d'affichage de l'objet__iter__ : la méthode d'iteration sur l'objet, ici on veut que ça itère les permutations de l'ensembleVous remarquez que toutes les méthodes prennent en premier paramètre self qui représente l'objet lui même (vous n'avez cependant pas besoin de passer explicitement l'objet en paramètre). De même, il faut toujous préciser self.quelquechose pour accéder à l'attribut / méthode quelquechose à l'intérieur de la classe.
In [40]:
import math
import random
class Permutations():
def __init__(self, values):
"""
The combinatorial set of permutations of ``values``
INPUT:
- ``values`` a list of distinct values in lexicographic order
"""
self._values = values
def values(self):
"""
Return the values to be permuted
"""
return self._values
def __repr__(self):
"""
Default string repr of ``self``
"""
return "Permutations of " + str(self._values)
def cardinality(self):
"""
Return the cardinality of the set
"""
return math.factorial(len(self._values))
def first(self):
"""
Return the first element of the set in lex order
"""
return list(self.values())
def __iter__(self):
"""
Iterator on the elements of the set in lexicographic order
"""
# écrire le code ici
def rank(self,p):
"""
Return the rank of permutation ``p`` in ``self`` in lexicographic order (starting at 0)
INPUT:
- ``p`` a permutation of ``self``
"""
# écrire le code ici
def unrank(self,i):
"""
Return the permutation corresponding to the rank ``i``
INPUT:
- ``i`` a integer between 0 and the cardinality minus 1
"""
# écrire le code ici
def next(self,p):
"""
Return the next element following ``p`` in ``self``
INPUT :
- ``p`` a permutation of ``self``
OUPUT :
The next permutation or ``None`` if ``p`` is the last permutation of ``self``
"""
# écrire le code ici
def random_element(self):
"""
Return a random element of ``self`` with uniform probability
"""
# écrire le code ici
In [41]:
Permutations([1,2,3])
In [42]:
P = Permutations([1,2,3])
P.values()
In [43]:
P.cardinality()
In [44]:
list(P) # fonctionnera si la methode __iter__ est implantée
In [45]:
P.first()
In [46]:
P.rank([2,3,1])
In [47]:
P.unrank(3)
In [48]:
P.next([2,3,1])
In [49]:
P.random_element()
Voici une série de tests génériques pour des ensembles combinatoires. Exécutez les exemples ci-dessous pour vérifier que votre classe passe les tests.
In [51]:
def test_cardinality_iter(S):
assert(len(list(S)) == S.cardinality())
def test_rank(S):
assert([S.rank(p) for p in S] == list(range(S.cardinality())))
def test_unrank(S):
assert(list(S) == [S.unrank(i) for i in range(S.cardinality())])
def test_next(S):
L = [S.first()]
while True:
p = S.next(L[-1])
if p == None:
break
L.append(p)
assert(L == list(S))
def all_tests(S):
tests = {"Cardinality / iter": test_cardinality_iter, "Rank": test_rank, "Unrank": test_unrank, "Next": test_next}
for k in tests:
print("Testsing: "+ k)
try:
tests[k](S)
print("Passed")
except AssertionError:
print("Not passed")
In [52]:
all_tests(Permutations([1,2,3]))
In [53]:
all_tests(Permutations([1,2,3,4]))
In [54]:
all_tests(Permutations([2,4,5,6]))
In [55]:
all_tests(Permutations([1,2,3,4,5]))
In [56]:
all_tests(Permutations([1,2,3,4,5,6]))
In [57]:
all_tests(Permutations([1,2,3,4,5,6,7]))
Exercice : vérifiez expérimentalement que votre algorithme pour random_element donne bien une distribution uniforme.
In [ ]:
In [ ]:
Nous allons maintenant refaire le même exercice mais cette fois avec des multi permutations (permuations sur un ensemble de valeur avec répétitions). On prendra toujours en paramètre la liste des valeurs on accepte qu'elle contienne des valeurs répétées. Par exemple, les pemrutations de $1,1,2$ sont $112$, $121$ et $211$.
On vous donne la classe suivante avec quelques méthodes utiles. A vous de la compléter.
In [70]:
import math
import random
class MultiPermutations():
def __init__(self, values):
"""
The combinatorial set of permutations of ``values``
INPUT:
- ``values`` a list of values, non necessary disctincts, in lexicographic order
"""
self._values = values
self._distinct_values = None
self._number_of = None
def values(self):
"""
Return the values to be permuted
"""
return self._values
def distinct_values(self):
"""
Return the list of distinct values of ``self``
"""
if self._distinct_values is None:
if len(self._values) == 0:
dv = []
else:
dv = [self._values[0]]
for v in self._values:
if v != dv[-1]:
dv.append(v)
self._distinct_values = dv
return self._distinct_values
def number_of(self, i):
"""
Return the number of occurences of the number ``i`` in the values of ``self``
"""
if self._number_of is None:
self._number_of = {}
for v in self.values():
self._number_of[v] = self._number_of.get(v,0)+1
return self._number_of.get(i,0)
def remove(self, v):
"""
Return the set of multipermutations on the values of ``self`` where one occurence of ``v`` has been removed
"""
l = self.values()
i = l.index(v)
return MultiPermutations(l[:i] + l[i+1:])
def first(self):
"""
Return the first element of the set in lex order
"""
return list(self._values)
def __repr__(self):
"""
Default string repr of ``self``
"""
return "(Multi) Permutations of " + str(self._values)
def cardinality(self):
"""
Return the cardinality of the set
"""
# écrire le code ici
def __iter__(self):
"""
Iterator on the elements of the set in lexicographic order
"""
# écrire le code ici
def rank(self,p):
"""
Return the rank of permutation ``p`` in ``self`` in lexicographic order (starting at 0)
INPUT:
- ``p`` a permutation of ``self``
"""
# écrire le code ici
def unrank(self,i):
"""
Return the permutation corresponding to the rank ``i``
INPUT:
- ``i`` a integer between 0 and the cardinality minus 1
"""
# écrire le code ici
def next(self,p):
"""
Return the next element following ``p`` in ``self``
INPUT :
- ``p`` a permutation of ``self``
OUPUT :
The next permutation or ``None`` if ``p`` is the last permutation of ``self``
"""
# écrire le code ici
def random_element(self):
"""
Return a random element of ``self`` with uniform probability
"""
# écrire le code ici
In [71]:
M = MultiPermutations([1,1,2])
M
In [72]:
M.remove(1)
In [73]:
M.remove(2)
In [74]:
M.cardinality()
In [75]:
list(M)
In [76]:
M.rank([1,2,1])
In [77]:
M.unrank(1)
In [78]:
M.next([1,2,1])
In [79]:
M.random_element()
In [80]:
all_tests(M)
In [81]:
all_tests(MultiPermutations([1,2,3]))
In [82]:
all_tests(MultiPermutations([2,2,2]))
In [83]:
all_tests(MultiPermutations([1,1,2,2,2]))
In [84]:
all_tests(MultiPermutations([1,1,1,2,2,3,3]))
In [88]:
MBig = MultiPermutations([1,1,2,2,2,3,4,5,5,6,7,7,8,8,8,9,9,10,10,10,10,11,11,11,12,13,13,13,14,15,15,15,15])
assert MBig.cardinality() == 727006375353307862292480000000
for i in range(100):
p = MBig.random_element()
assert MBig.unrank(MBig.rank(p)) == p
Exercice : vérifiez expérimentalement que votre méthode pour random_element donnebien une distribution uniforme.
In [ ]:
In [ ]:
In [89]:
from trisoff import trisoff
Le tableau trisoff contient des fonctions de tris qui prennent en argument une list python et retournent une nouvelle liste (sans modifier l'ancienne) supposément triée. On souhaite tester les algorithmes sur différentes configurations. Pour cela, on implémente la classe suivante (à compléter).
In [90]:
class TestTris():
def __init__(self, permset):
"""
INPUT:
- ftri, a sorting function
- permset, a permutation set, an instance of Permutations or Multipermutations
"""
self._permset = permset
def permset(self):
"""
Return the permutation set of self
"""
return self._permset
def __repr__(self):
return "Sorting test class for " + str(self.permset())
def is_sorted(self,perm):
"""
Return True if perm is a sorted permutation of the permset (same values and sorted)
INPUT:
- perm, a list of numbers
"""
return perm == self.permset().first() # there is only one sorted perm per permset: the first one
def test_on_all(self,ftri):
"""
Return True if the function ftri works on all permutations of the permset
INPUT:
- ftri, a python function which takes a list input and returns a list
"""
# écrire le code ici
def test_on_one(self,ftri):
"""
Return True if the function ftri works on one random permutation of the permset
INPUT:
- ftri, a python function which takes a list input and returns a list
"""
# écrire le code ici
def test_on_many(self,ftri,k):
"""
Return True if the function ftri works on k random permutations of the permset
INPUT:
- ftri, a python function which takes a list input and returns a list
- k an integer
"""
# écrire le code ici
In [91]:
T = TestTris(Permutations([1,2,3]))
T
In [92]:
T.test_on_all(trisoff[0])
In [93]:
T.test_on_one(trisoff[0])
In [94]:
T.test_on_many(trisoff[0],100)
Le tableau trisoff contient 8 fonctions. Seules 2 fonctionnent dans tous les cas de figures et seule 1 de façon efficace. Trouvez les !
In [ ]: