Bonjour a tous, 
Je fais face à un problème que je n'arrive pas à résoudre.

Supposons que j'ai une liste :

maList = [
[ [1, 2, 3], [4, 5], [6, 7, 8] ],
[ [1, 2, 3], [6, 7, 8], [4, 5] ],
[ [1, 2, 3], [4, 5, 6], [7, 8] ]
]

Et que je veuille supprimer les doublons (sachant que le deuxième liste contient les mêmes éléments mais pas dans le même ordre, et doit donc être supprimé).

Comment devrais-je procéder ?

Mon code est le suivant pour le moment : 

# Supprime les combinaisons deja existantes
# @param groups La liste des groupes deja trouves
def grp_exist(groups):
    len_group = len(groups)
    for i in range (0, len_group):
        groups[i].sort()

    toPop = list()

    for i in range (0, len_group-1):
        for j in range (i+1, len_group):
            equal = True

            for k in range(0, len(groups[i])):
                if groups[i][k] != groups[j][k]:
                    equal = False
            if equal == True:
                toPop.append(j)
    i = 0
    toPop = list(dict.fromkeys(toPop))
    for pop in toPop:
        groups.pop(pop-i)
        i = i + 1
    return groups

def test_grp_exist():
    combis = [[[1, 2, 3], [4, 5], [6, 7, 8]], [[1, 2, 3], [6, 7, 8], [4, 5]]]
    identical = grp_exist(combis)

test_grp_exist()

Mais il ne fonctionne pas à cause de l'ordre.

-
Edité par PepitoSama 5 octobre 2019 à 14:56:16

Dans ton cas, pour savoir si une liste s'obtient en permutant des éléments, il te suffit de les trier et de regarder si le résultat est le même :

maList = [
[ [1, 2, 3], [4, 5], [6, 7, 8] ],
[ [1, 2, 3], [6, 7, 8], [4, 5] ],
[ [1, 2, 3], [4, 5, 6], [7, 8] ]
]

print(sorted(maList[0])== sorted(maList[1]))

True

Par ailleurs, à ce que je vois de ton code, tu essayes «à la main» de retirer les doublons. Sauf contexte particulier, ce n'est pas comme ça qu'on fait en Python. La façon standard est d'utiliser la structure de données set (ensemble) puis de reconstruire une liste. Le seul inconvénient est que l'ordre initial de ta liste peut être modifié.

Si tu veux la liste des sans doublons en le faisant «à la main», voici une façon et que tu adapteras facilement à ton code :

def eliminer_doublons(L):
    sansDoublons=[]
    for i in range(0, len(L)):
        if L[i] not in sansDoublons:
            sansDoublons.append(L[i])
    return sansDoublons
for L in [
    [42, 81, 42, 65, 12, 81, 31, 42],
    [42],
    [42]*5,
    ]:
    print(L, "->",  eliminer_doublons(L))

[42, 81, 42, 65, 12, 81, 31, 42] -> [42, 81, 65, 12, 31]
[42] -> [42]
[42, 42, 42, 42, 42] -> [42]

-
Edité par PascalOrtiz 5 octobre 2019 à 15:27:40

Bonjour, 

Merci de ta réponse, je vais me renseigner sur les set du coup !

Je viens d'essayer mais cela ne marche pas vraiment dans mon cas.

Par exemple pour :

combis =
[
[[1, 2, 3], [6, 7], [8, 4, 5]],
[[1, 2, 3], [4, 5, 8], [6, 7]]
]
print(sorted(combis[0]) == sorted(combis[1]))

L'ordre des chiffre dans les liste ont une importance.

Elle vient d'où cette liste de listes de listes de nombres ? Pourquoi tu ne la tries et ne la filtres pas au moment de sa création ?

Sinon,

def filtre(lists):
    results = []
    for ls in lists:
        ls = sorted(sorted(x) for x in ls)
        if ls not in results:
            results.append(ls)
    return results

-
Edité par HaSh3 5 octobre 2019 à 16:01:42

PepitoSama a écrit:

Je viens d'essayer mais cela ne marche pas vraiment dans mon cas.

Par exemple pour :

combis =
[
[[1, 2, 3], [6, 7], [8, 4, 5]],
[[1, 2, 3], [4, 5, 8], [6, 7]]
]
print(sorted(combis[0]) == sorted(combis[1]))

L'ordre des chiffre dans les liste ont une importance.

Tu ne l'avais pas précisé  Dans le principe, ça ne change rien, il suffit de «normaliser» en triant aussi les sous-listes :

combis =[
[[1, 2, 3], [6, 7], [8, 4, 5]],
[[1, 2, 3], [4, 5, 8], [6, 7]]
]

print(sorted(sorted(L) for L in combis[0])== sorted(sorted(L) for L in combis[1]))

Pour les doublons et set, tu peux regarder  ici.

-
Edité par PascalOrtiz 5 octobre 2019 à 16:01:19

HaSh3 :

Cette liste vient d’un algorithme récursif.

En gros je dois générer dans un ensemble allant de 1 à n tous les groupes faisable par tranche de 2 ou 3

Par exemple pour 4 personne il est possible de faire :

12 34

13 24

14 23

Pour 5 personnes : 

123 45

124 35

125 34

... etc

Je ne cherche pas à optimiser mais juste à faire fonctionner pour le moment car c’est une demande du professeur.

PascalOrtiz :

C’est vrais que dit comme ça c’est logique, je vais essayer merci de ton aide ! 

PepitoSama a écrit:

En gros je dois générer dans un ensemble allant de 1 à n tous les groupes faisable par tranche de 2 ou 3

Oui, très bon exo, je vais d'ailleurs sans doute le rajouter à ma liste d'exercices sur la récursivité  Pour le coup, ta fonction récursive devrait pouvoir gérer elle-même l'absence de doublons plutôt que de tout générer puis supprimer les doublons.

-
Edité par PascalOrtiz 5 octobre 2019 à 17:49:17

@PascalOrtiz +1

Puisqu'il s'agit de travailler la récursion ça ne va pas beaucoup t'aider, mais si tu veux te faire une idée de ce qui ce fait en pratique, regarde la fonction itertools.permutations.

Le nombre de partitions croit très vite (pour n=17 on est à environ 1 milliard de partitions) donc très rapidement, on est dans l'incapacité des les produire.

PascalOrtiz :

Je sais, la consigne est d'en faire un pour 11 personne pour le moment, puis d'optimiser pour éliminer les opérations inutiles

-
Edité par PepitoSama 5 octobre 2019 à 22:10:18

J'ai incorporé ta question à mes exercices de récursivité en ajoutant quelques indications de résolution.

PascalOrtiz a écrit:

J'ai incorporé ta question à mes exercices de récursivité en ajoutant quelques indications de résolution.

Je pense que j'avais déjà fais ce que tu explique, mais sans optimisation l'algo reste très long, je n'ai pas calculé le nombre d'opération mais c'est exponentiel à vu d’œil.

Voici mon premier rendu : https://github.com/PepitoSama/Projet-Math-de-la-D-cision/

Je pense créer une table de hash pour vérifier l’existence des groupes nouvellement créés, mais je ne sais pas si c'est une bonne piste, en théorie, le nombre d'opération sera inférieur.

-
Edité par PepitoSama 6 octobre 2019 à 12:24:48

L'algo est sans doute sur-exponentiel. Pour n=11, à ce que je comprends de ton code, tu génères uniquement les partitions ayant un certain format ([3, 2, 2, 2, 2]) et ça prend beaucoup de temps (au bout de 1 minute, il n'y avait toujours rien) donc il y a problème dans ton algorithme (dont la logique ne me semble pas claire et le codage plutôt compliqué).

Pour n=11, avec un i5, tu devrais obtenir le résultat en moins d'une demi-seconde et pour tous les formats. On doit pouvoir en un temps raisonnable obtenir toutes les partitions (quelques dizaines de secondes) jusqu'à n=14.

A mon avis, inutile d'aller code une table de hash, et essaye surtout de clarifier puis de simplifier ton algorithme. En outre, même si ce n'est probablement pas la cause de la lenteur, il y a des choses qu'il faut absolument éviter  du genre pop(0) sur une liste.

Fondamentalement, je vois deux méthodes : celle que j'explique sur mon site et une autre, que je n'ai pas écrite et qui serait plutôt itérative. Il faut résoudre l'équation en nombres entiers 2a+3b=n (ce qui donne le format de partition) puis générer pour chaque a et chaque b solution toutes les partitions sur 2a éléments formées de a parties à 2 éléments et, idem, toutes les façons de générer les partitions sur 3b éléments formées de b parties à 3 éléments. Là pour le coup itertools peut servir.