IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Python Discussion :

Toutes les combinaisons possibles (en plus complexe)


Sujet :

Python

  1. #1
    Candidat au Club
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 6
    Points : 2
    Points
    2
    Par défaut Toutes les combinaisons possibles (en plus complexe)
    Bonjour,

    Je me retrouve plus face à un problème d'algo que de codage. Voici le problème:

    J'ai 2 listes de nombres qui contiennent chacun le même nombre de valeurs.
    Par exemple:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    liste1 = [2,4,4,6,6,12,12,12,16,18]
    liste2 = [1,1,1,2,2,4,4,4,4,4]
    Je voudrais obtenir l'ensemble des combinaisons de combinaisons de deux nombres (un de chaque liste) existantes, sans répétition d'une combinaison au sein d'une solution.
    Pour être plus clair par une exemple je voudrais qu'un des résultats soit:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    [[2,1],[4,1],[4,4],[6,4],[6,2],[12,1],[12,2],[12,4],[16,4],[18,4]]
    Merci beaucoup pour vos réponses

  2. #2
    Expert éminent

    Homme Profil pro
    Inscrit en
    Octobre 2008
    Messages
    4 298
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2008
    Messages : 4 298
    Points : 6 778
    Points
    6 778
    Par défaut
    Salut,

    par exemple:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
     
    #!/usr/bin/env python
    # -*- coding: utf-8 -*-
     
    liste1 = [2,4,4,6,6,12,12,12,16,18]
    liste2 = [1,1,1,2,2,4,4,4,4,4]
     
    liste3 = set()
     
    for item in liste1:
        for item2 in liste2:
            l = (item, item2)
            liste3.add(l)
     
     
    print liste3
    set([(6, 4), (18, 2), (16, 4), (12, 1), (12, 2), (6, 1), (4, 4), (16, 2), (2, 1), (18, 4), (16, 1), (12, 4), (6, 2), (2, 2), (4, 2), (4, 1), (2, 4), (18, 1)])

    Bon maintenant faut trier, mais le principal est là

    Vincent

  3. #3
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 76
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Points : 1 913
    Points
    1 913
    Par défaut
    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    #!/usr/bin/env python
    # -*- coding: utf-8 -*-
     
    liste1 = list(set([2,4,4,6,6,12,12,12,16,18]))
    liste2 = list(set([1,1,1,2,2,4,4,4,4,4]))
     
    liste3=[(x,y) for x in liste1 for y in liste2]
    print liste3
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  4. #4
    Membre expérimenté
    Homme Profil pro
    Inscrit en
    Avril 2004
    Messages
    1 046
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Avril 2004
    Messages : 1 046
    Points : 1 376
    Points
    1 376
    Par défaut
    Code console : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    >>>[(i,j) for i in set(liste1) for j in set(liste2)]
    [(2, 1), (2, 2), (2, 4), (4, 1), (4, 2), (4, 4), (6, 1), (6, 2), (6, 4), (12, 1), (12, 2), (12, 4), (16, 1), (16, 2), (16, 4), (18, 1), (18, 2), (18, 4)]
    après faut faire des paquets de 10 si j'ai bien comprite.
    ------------------------------------------------------------------
    arf, trop tard.

  5. #5
    Membre du Club
    Profil pro
    Inscrit en
    Mars 2010
    Messages
    53
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Mars 2010
    Messages : 53
    Points : 64
    Points
    64
    Par défaut
    ou bien on utilise les fonctions existantes:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    from itertools import product
    combi = list(product(set(liste1), set(liste2)))
    ce qui donne exactement les résultats de josmiley et Zavonen.

    pour les petites listes, je préfère quand même la solution 'inline' de josmiley

  6. #6
    Candidat au Club
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 6
    Points : 2
    Points
    2
    Par défaut
    Déjà un grand merci pour vos réponses, mais ce n'est pas exactement ce que je voulais. (Je comprends que j'explique mal, mais c'est assez complexe)
    Effectivement, vos solutions génèrent tous les couples possibles. Ce qu'il me faudrait c'est que chaque paquet de 10 couples soit formé qu'à partir des éléments dans la liste.

    Par exemple, la liste 1 contient un seul 2, donc il apparaitra qu'une seule fois dans le paquet.
    Et il faudrait que le script me sorte toutes les permutations des couples au sein d'un paquet.

    Encore merci pour l'usage de vos méninges!

  7. #7
    Membre du Club
    Profil pro
    Inscrit en
    Mars 2010
    Messages
    53
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Mars 2010
    Messages : 53
    Points : 64
    Points
    64
    Par défaut
    Citation Envoyé par doloris Voir le message
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    liste1 = [2,4,4,6,6,12,12,12,16,18]
    liste2 = [1,1,1,2,2,4,4,4,4,4]
    Pour être plus clair par une exemple je voudrais qu'un des résultats soit:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    [[2,1],[4,1],[4,4],[6,4],[6,2],[12,1],[12,2],[12,4],[16,4],[18,4]]
    au fait, pourquoi pas [18, 1] ?

    et pourquoi je voudrais qu'un des résultats?

    c'est pas clair pour moi..

  8. #8
    Candidat au Club
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 6
    Points : 2
    Points
    2
    Par défaut
    je veux tous les résultats, là je donne un des résultats en exemple.

    Et pas [18,1] car, il faut consommer uniquement les nombres qu'il y a dans les listes. Ainsi, il y'a 10 chiffres par liste, la réponse ne peut faire que 10 couples.
    Et, c'est [18,4] le dernier couple car avant d'arriver à ce dernier couple, on a déjà utilisé dans la liste 1 tous les chiffres sauf le 18 et dans la liste 2, tous sauf le 4.

    Est-ce plus clair?

  9. #9
    Membre du Club
    Profil pro
    Inscrit en
    Mars 2010
    Messages
    53
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Mars 2010
    Messages : 53
    Points : 64
    Points
    64
    Par défaut
    Citation Envoyé par doloris Voir le message
    je veux tous les résultats, là je donne un des résultats en exemple.

    Et pas [18,1] car, il faut consommer uniquement les nombres qu'il y a dans les listes. Ainsi, il y'a 10 chiffres par liste, la réponse ne peut faire que 10 couples.
    Et, c'est [18,4] le dernier couple car avant d'arriver à ce dernier couple, on a déjà utilisé dans la liste 1 tous les chiffres sauf le 18 et dans la liste 2, tous sauf le 4.

    Est-ce plus clair?
    je commence à comprendre

    En fait, on fait pas ce qu'on veut. Par exemple si on "mange" tous les nombres mais qu'on laisse 12 et 12 dans la première liste et 1 et 1 dans la deuxième, c'est qu'on s'est planté c'est ça?

  10. #10
    Membre extrêmement actif
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    1 418
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 1 418
    Points : 1 658
    Points
    1 658
    Par défaut
    Bonjour,

    Et ça ? :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    liste1 = [1,4,8,9]
    liste2 = [13,22,56,90]
     
    from itertools import permutations
     
    for li in permutations(liste2,4):
        print zip(liste1,li)
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    [(1, 13), (4, 22), (8, 56), (9, 90)]
    [(1, 13), (4, 22), (8, 90), (9, 56)]
    [(1, 13), (4, 56), (8, 22), (9, 90)]
    [(1, 13), (4, 56), (8, 90), (9, 22)]
    [(1, 13), (4, 90), (8, 22), (9, 56)]
    [(1, 13), (4, 90), (8, 56), (9, 22)]
    [(1, 22), (4, 13), (8, 56), (9, 90)]
    [(1, 22), (4, 13), (8, 90), (9, 56)]
    [(1, 22), (4, 56), (8, 13), (9, 90)]
    [(1, 22), (4, 56), (8, 90), (9, 13)]
    [(1, 22), (4, 90), (8, 13), (9, 56)]
    [(1, 22), (4, 90), (8, 56), (9, 13)]
    [(1, 56), (4, 13), (8, 22), (9, 90)]
    [(1, 56), (4, 13), (8, 90), (9, 22)]
    [(1, 56), (4, 22), (8, 13), (9, 90)]
    [(1, 56), (4, 22), (8, 90), (9, 13)]
    [(1, 56), (4, 90), (8, 13), (9, 22)]
    [(1, 56), (4, 90), (8, 22), (9, 13)]
    [(1, 90), (4, 13), (8, 22), (9, 56)]
    [(1, 90), (4, 13), (8, 56), (9, 22)]
    [(1, 90), (4, 22), (8, 13), (9, 56)]
    [(1, 90), (4, 22), (8, 56), (9, 13)]
    [(1, 90), (4, 56), (8, 13), (9, 22)]
    [(1, 90), (4, 56), (8, 22), (9, 13)]

    Si les listes contiennent des doublons, que faut il faire ?

  11. #11
    Candidat au Club
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 6
    Points : 2
    Points
    2
    Par défaut
    Citation Envoyé par miawaw Voir le message
    je commence à comprendre

    En fait, on fait pas ce qu'on veut. Par exemple si on "mange" tous les nombres mais qu'on laisse 12 et 12 dans la première liste et 1 et 1 dans la deuxième, c'est qu'on s'est planté c'est ça?
    Oui, il ne faut laisser aucun nombre et qu'il n'y ai pas de doublons dans les couples (donc effectivement s'il reste 12/12 et 1/1 on a forcément un doublon).

    Pour ton script eyquem, il faut utiliser la totalité des nombres des listes (et certains apparaissent plusieurs fois, d'où une certaine difficulté d'ailleurs), donc en sortie on doit forcément avoir des paquets de 10 couples.

    En cas de doublons dans les couples, le paquet ne doit pas être retenu

  12. #12
    Membre expérimenté
    Homme Profil pro
    Inscrit en
    Avril 2004
    Messages
    1 046
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Avril 2004
    Messages : 1 046
    Points : 1 376
    Points
    1 376
    Par défaut
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    l1 = [2,4,4,6,6,12,12,12,16,18]
    l2 = [1,1,1,2,2,4,4,4,4,4]
    out=[]
    while l1:
    	i=-1
    	a=l1.pop()
    	while (a,l2[i]) in out:
    		i-=1
    	b=l2.pop(i)
    	out.append((a,b))
    print out
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    [(18, 4), (16, 4), (12, 4), (12, 2), (12, 1), (6, 4), (6, 2), (4, 4), (4, 1), (2, 1)]
    ça doit pouvoir se réduire.

  13. #13
    Candidat au Club
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 6
    Points : 2
    Points
    2
    Par défaut
    Citation Envoyé par josmiley Voir le message
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    l1 = [2,4,4,6,6,12,12,12,16,18]
    l2 = [1,1,1,2,2,4,4,4,4,4]
    out=[]
    while l1:
    	i=-1
    	a=l1.pop()
    	while (a,l2[i]) in out:
    		i-=1
    	b=l2.pop(i)
    	out.append((a,b))
    print out
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    [(18, 4), (16, 4), (12, 4), (12, 2), (12, 1), (6, 4), (6, 2), (4, 4), (4, 1), (2, 1)]
    ça doit pouvoir se réduire.
    Je t'avouerai que je connais pas bien les fonctions que tu as utilisées, mais le résultat qu'il me faut est tous les paquets de couples possibles et non un seul. La solution ici semble correcte, mais c'est une solution unique.

  14. #14
    Membre du Club
    Profil pro
    Inscrit en
    Mars 2010
    Messages
    53
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Mars 2010
    Messages : 53
    Points : 64
    Points
    64
    Par défaut
    Bonjour,

    l'algo de jo de fonctionne malheureusement pas sur
    liste1 = [1,1,3]
    liste2 = [2,2,4]

    je pense qu'il faut tester toutes les permutations possibles, ou alors trouver un super algo mais je ne crois pas qu'une simple boucle en viendra à bout.

  15. #15
    Membre extrêmement actif
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    1 418
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 1 418
    Points : 1 658
    Points
    1 658
    Par défaut
    Pour ton script eyquem, il faut utiliser la totalité des nombres des listes (et certains apparaissent plusieurs fois, d'où une certaine difficulté d'ailleurs), donc en sortie on doit forcément avoir des paquets de 10 couples.
    Pour une liste2 de 10 éléments, il y a 3.628.800 permutations à 10 éléments possibles.
    Je pensais qu’il serait clair que j’ai pris des listes à 4 éléments ( et donc permutations(liste2,4) ) pour pouvoir afficher les combinaisons trouvées.








    Oui, il ne faut laisser aucun nombre et qu'il n'y ai pas de doublons dans les couples (donc effectivement s'il reste 12/12 et 1/1 on a forcément un doublon).
    Moi, quand je lis « dans les couples », je comprends “dans les couples“, c’est à dire que
    (12,12) est interdit.

    Mais je comprends avec l’exemple de 12/12/ et 1/1 que ce qu'il faut en fait comprendre, c'est qu'une combinaison du genre
    .........(4,8), (12,1), (12,1) )
    c’est à dire pour moi un doublon dans la combinaison,
    est interdite.



    Muni de ce nouveau renseignement, je propose donc:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    liste1 = [1,4,4,9]
    liste2 = [2,4,6,6]
    print repr(liste1)+'\n'+repr(liste2)+'\n'
     
    from itertools import permutations
     
    for li in permutations(liste2,4):
        comb = zip(liste1,li)
        if len(set(comb))==len(comb):
            print comb
        else:
            print comb,'  pas bon'




    Mais il reste une question:

    - dans la première combinaison [(1, 2), (4, 4), (4, 6), (9, 6)]
    le 4 en position 2 de liste1 est combiné avec le 6 en position 2 de liste 2,
    et le 9 en position 3 de liste1 est combiné avec le 6 en position 3 de liste2

    - dans la seconde combinaison [(1, 2), (4, 4), (4, 6), (9, 6)]
    le 4 en position 2 de liste1 est combiné avec le 6 en position 3 de liste 2,
    et le 9 en position 3 de liste1 est combiné avec le 6 en position 2 de liste2

    - mais les deux combinaisons sont macroscopiquement identiques


    Je ne crois pas que l’origine positionnelle des éléments des couples des combinaisons soit considérée comme importante, et dans cette hypothèse les deux premières combinaisons sont, à l’œil nu, identiques. Aussi ne faut il à mon avis pas retenir la deuxième combinaison. Et donc en adaptant le programme à cette fin:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
     
    liste1 = [1,4,4,9]
    liste2 = [2,4,6,6]
    print repr(liste1)+'\n'+repr(liste2)+'\n'
     
    from itertools import permutations
     
    res = []
    for li in permutations(liste2,4):
        comb = zip(liste1,li)
        if li not in res:
            res.append(li)
            if len(set(comb))==len(comb):
                print comb
            else:
                print comb,'  couples en doublon(s)'
        else:
            print comb,'  deja vue'
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    [1, 4, 4, 9]
    [2, 4, 6, 6]
     
    [(1, 2), (4, 4), (4, 6), (9, 6)]
    [(1, 2), (4, 4), (4, 6), (9, 6)]   deja vue
    [(1, 2), (4, 6), (4, 4), (9, 6)]
    [(1, 2), (4, 6), (4, 6), (9, 4)]   couples en doublon(s)
    [(1, 2), (4, 6), (4, 4), (9, 6)]   deja vue
    [(1, 2), (4, 6), (4, 6), (9, 4)]   couples en doublon(s)
    [(1, 4), (4, 2), (4, 6), (9, 6)]
    [(1, 4), (4, 2), (4, 6), (9, 6)]   deja vue
    [(1, 4), (4, 6), (4, 2), (9, 6)]
    [(1, 4), (4, 6), (4, 6), (9, 2)]   couples en doublon(s)
    [(1, 4), (4, 6), (4, 2), (9, 6)]   deja vue
    [(1, 4), (4, 6), (4, 6), (9, 2)]   couples en doublon(s)
    [(1, 6), (4, 2), (4, 4), (9, 6)]
    [(1, 6), (4, 2), (4, 6), (9, 4)]
    [(1, 6), (4, 4), (4, 2), (9, 6)]
    [(1, 6), (4, 4), (4, 6), (9, 2)]
    [(1, 6), (4, 6), (4, 2), (9, 4)]
    [(1, 6), (4, 6), (4, 4), (9, 2)]
    [(1, 6), (4, 2), (4, 4), (9, 6)]   deja vue
    [(1, 6), (4, 2), (4, 6), (9, 4)]   deja vue
    [(1, 6), (4, 4), (4, 2), (9, 6)]   deja vue
    [(1, 6), (4, 4), (4, 6), (9, 2)]   deja vue
    [(1, 6), (4, 6), (4, 2), (9, 4)]   deja vue
    [(1, 6), (4, 6), (4, 4), (9, 2)]   deja vue
    Ce qui donne, en ne gardant que les bonnes combinaisons:


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    res = []
    for li in permutations(liste2,4):
        comb = zip(liste1,li)
        if comb not in res:
            if len(set(comb))==len(comb):
                res.append(comb)
                print comb
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    [(1, 2), (4, 4), (4, 6), (9, 6)]
    [(1, 2), (4, 6), (4, 4), (9, 6)]
    [(1, 4), (4, 2), (4, 6), (9, 6)]
    [(1, 4), (4, 6), (4, 2), (9, 6)]
    [(1, 6), (4, 2), (4, 4), (9, 6)]
    [(1, 6), (4, 2), (4, 6), (9, 4)]
    [(1, 6), (4, 4), (4, 2), (9, 6)]
    [(1, 6), (4, 4), (4, 6), (9, 2)]
    [(1, 6), (4, 6), (4, 2), (9, 4)]
    [(1, 6), (4, 6), (4, 4), (9, 2)]




    Mais ce n’est pas suffisant... peut être: on remarque que les deux premières combinaisons ont les mêmes éléments, même s’ils ne sont pas dans le même ordre dans les deux combinaisons.

    L’ordre compte-t-il , auquel cas il n’y a pas à chercher plu loin, ou ne compte-t-il pas et faut il éliminer les combinaisons d’éléments déjà vues dans une ordre différent ?


    À force de proposer des réponses, on va finir par obtenir un énoncé correct.

  16. #16
    Candidat au Club
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 6
    Points : 2
    Points
    2
    Par défaut
    Merci pour ta réponse eyquem, on touche presque au but.
    Encore désolé pour l'énoncé, mais j'ai du mal à le formuler clairement je suis d'accord avec toi .

    Alors pour répondre à tes questions, l'ordre compte, dans ton exemple, on gardera bien les deux lignes suivantes:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    [(1, 2), (4, 4), (4, 6), (9, 6)]
    [(1, 2), (4, 6), (4, 4), (9, 6)]
    Cependant, il faut être exhaustif dans la liste, et donc on devrait avoir toutes les combinaisons aillant des éléments similaires. On devra donc voir apparaitre également:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    [(4, 4), (1, 2), (4, 6), (9, 6)]
    [(4, 6), (4, 4), (1, 2),  (9, 6)]
    etc....

  17. #17
    Membre extrêmement actif
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    1 418
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 1 418
    Points : 1 658
    Points
    1 658
    Par défaut
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    liste1 = [1,4,4,9]
    liste2 = [2,4,6,6]
    print 'liste1 = '+repr(liste1)+'\nliste2 = '+repr(liste2)+'\n'
     
    from itertools import permutations
     
    res = []
    for li in permutations(liste1,4):
        for ly in permutations(liste2,4):
            comb = zip(li,ly)
            if comb not in res and len(set(comb))==len(comb):
                res.append(comb)
     
    print '\n'.join(repr(u) for u in res)
    print '\nnombre de combinaisons differentes sans doublons:',len(res)
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    liste1 = [1, 4, 4, 9]
    liste2 = [2, 4, 6, 6]
     
    [(1, 2), (4, 4), (4, 6), (9, 6)]
    [(1, 2), (4, 6), (4, 4), (9, 6)]
    [(1, 4), (4, 2), (4, 6), (9, 6)]
    [(1, 4), (4, 6), (4, 2), (9, 6)]
    [(1, 6), (4, 2), (4, 4), (9, 6)]
    [(1, 6), (4, 2), (4, 6), (9, 4)]
    [(1, 6), (4, 4), (4, 2), (9, 6)]
    [(1, 6), (4, 4), (4, 6), (9, 2)]
    [(1, 6), (4, 6), (4, 2), (9, 4)]
    [(1, 6), (4, 6), (4, 4), (9, 2)]
    [(1, 2), (4, 4), (9, 6), (4, 6)]
    [(1, 2), (4, 6), (9, 6), (4, 4)]
    [(1, 4), (4, 2), (9, 6), (4, 6)]
    [(1, 4), (4, 6), (9, 6), (4, 2)]
    [(1, 6), (4, 2), (9, 4), (4, 6)]
    [(1, 6), (4, 2), (9, 6), (4, 4)]
    [(1, 6), (4, 4), (9, 2), (4, 6)]
    [(1, 6), (4, 4), (9, 6), (4, 2)]
    [(1, 6), (4, 6), (9, 2), (4, 4)]
    [(1, 6), (4, 6), (9, 4), (4, 2)]
    [(1, 2), (9, 6), (4, 4), (4, 6)]
    [(1, 2), (9, 6), (4, 6), (4, 4)]
    [(1, 4), (9, 6), (4, 2), (4, 6)]
    [(1, 4), (9, 6), (4, 6), (4, 2)]
    [(1, 6), (9, 2), (4, 4), (4, 6)]
    [(1, 6), (9, 2), (4, 6), (4, 4)]
    [(1, 6), (9, 4), (4, 2), (4, 6)]
    [(1, 6), (9, 4), (4, 6), (4, 2)]
    [(1, 6), (9, 6), (4, 2), (4, 4)]
    [(1, 6), (9, 6), (4, 4), (4, 2)]
    [(4, 2), (1, 4), (4, 6), (9, 6)]
    [(4, 2), (1, 6), (4, 4), (9, 6)]
    [(4, 2), (1, 6), (4, 6), (9, 4)]
    [(4, 4), (1, 2), (4, 6), (9, 6)]
    [(4, 4), (1, 6), (4, 2), (9, 6)]
    [(4, 4), (1, 6), (4, 6), (9, 2)]
    [(4, 6), (1, 2), (4, 4), (9, 6)]
    [(4, 6), (1, 4), (4, 2), (9, 6)]
    [(4, 6), (1, 6), (4, 2), (9, 4)]
    [(4, 6), (1, 6), (4, 4), (9, 2)]
    [(4, 2), (1, 4), (9, 6), (4, 6)]
    [(4, 2), (1, 6), (9, 4), (4, 6)]
    [(4, 2), (1, 6), (9, 6), (4, 4)]
    [(4, 4), (1, 2), (9, 6), (4, 6)]
    [(4, 4), (1, 6), (9, 2), (4, 6)]
    [(4, 4), (1, 6), (9, 6), (4, 2)]
    [(4, 6), (1, 2), (9, 6), (4, 4)]
    [(4, 6), (1, 4), (9, 6), (4, 2)]
    [(4, 6), (1, 6), (9, 2), (4, 4)]
    [(4, 6), (1, 6), (9, 4), (4, 2)]
    [(4, 2), (4, 4), (1, 6), (9, 6)]
    [(4, 2), (4, 6), (1, 4), (9, 6)]
    [(4, 2), (4, 6), (1, 6), (9, 4)]
    [(4, 4), (4, 2), (1, 6), (9, 6)]
    [(4, 4), (4, 6), (1, 2), (9, 6)]
    [(4, 4), (4, 6), (1, 6), (9, 2)]
    [(4, 6), (4, 2), (1, 4), (9, 6)]
    [(4, 6), (4, 2), (1, 6), (9, 4)]
    [(4, 6), (4, 4), (1, 2), (9, 6)]
    [(4, 6), (4, 4), (1, 6), (9, 2)]
    [(4, 2), (4, 4), (9, 6), (1, 6)]
    [(4, 2), (4, 6), (9, 4), (1, 6)]
    [(4, 2), (4, 6), (9, 6), (1, 4)]
    [(4, 4), (4, 2), (9, 6), (1, 6)]
    [(4, 4), (4, 6), (9, 2), (1, 6)]
    [(4, 4), (4, 6), (9, 6), (1, 2)]
    [(4, 6), (4, 2), (9, 4), (1, 6)]
    [(4, 6), (4, 2), (9, 6), (1, 4)]
    [(4, 6), (4, 4), (9, 2), (1, 6)]
    [(4, 6), (4, 4), (9, 6), (1, 2)]
    [(4, 2), (9, 4), (1, 6), (4, 6)]
    [(4, 2), (9, 6), (1, 4), (4, 6)]
    [(4, 2), (9, 6), (1, 6), (4, 4)]
    [(4, 4), (9, 2), (1, 6), (4, 6)]
    [(4, 4), (9, 6), (1, 2), (4, 6)]
    [(4, 4), (9, 6), (1, 6), (4, 2)]
    [(4, 6), (9, 2), (1, 6), (4, 4)]
    [(4, 6), (9, 4), (1, 6), (4, 2)]
    [(4, 6), (9, 6), (1, 2), (4, 4)]
    [(4, 6), (9, 6), (1, 4), (4, 2)]
    [(4, 2), (9, 4), (4, 6), (1, 6)]
    [(4, 2), (9, 6), (4, 4), (1, 6)]
    [(4, 2), (9, 6), (4, 6), (1, 4)]
    [(4, 4), (9, 2), (4, 6), (1, 6)]
    [(4, 4), (9, 6), (4, 2), (1, 6)]
    [(4, 4), (9, 6), (4, 6), (1, 2)]
    [(4, 6), (9, 2), (4, 4), (1, 6)]
    [(4, 6), (9, 4), (4, 2), (1, 6)]
    [(4, 6), (9, 6), (4, 2), (1, 4)]
    [(4, 6), (9, 6), (4, 4), (1, 2)]
    [(9, 2), (1, 6), (4, 4), (4, 6)]
    [(9, 2), (1, 6), (4, 6), (4, 4)]
    [(9, 4), (1, 6), (4, 2), (4, 6)]
    [(9, 4), (1, 6), (4, 6), (4, 2)]
    [(9, 6), (1, 2), (4, 4), (4, 6)]
    [(9, 6), (1, 2), (4, 6), (4, 4)]
    [(9, 6), (1, 4), (4, 2), (4, 6)]
    [(9, 6), (1, 4), (4, 6), (4, 2)]
    [(9, 6), (1, 6), (4, 2), (4, 4)]
    [(9, 6), (1, 6), (4, 4), (4, 2)]
    [(9, 2), (4, 4), (1, 6), (4, 6)]
    [(9, 2), (4, 6), (1, 6), (4, 4)]
    [(9, 4), (4, 2), (1, 6), (4, 6)]
    [(9, 4), (4, 6), (1, 6), (4, 2)]
    [(9, 6), (4, 2), (1, 4), (4, 6)]
    [(9, 6), (4, 2), (1, 6), (4, 4)]
    [(9, 6), (4, 4), (1, 2), (4, 6)]
    [(9, 6), (4, 4), (1, 6), (4, 2)]
    [(9, 6), (4, 6), (1, 2), (4, 4)]
    [(9, 6), (4, 6), (1, 4), (4, 2)]
    [(9, 2), (4, 4), (4, 6), (1, 6)]
    [(9, 2), (4, 6), (4, 4), (1, 6)]
    [(9, 4), (4, 2), (4, 6), (1, 6)]
    [(9, 4), (4, 6), (4, 2), (1, 6)]
    [(9, 6), (4, 2), (4, 4), (1, 6)]
    [(9, 6), (4, 2), (4, 6), (1, 4)]
    [(9, 6), (4, 4), (4, 2), (1, 6)]
    [(9, 6), (4, 4), (4, 6), (1, 2)]
    [(9, 6), (4, 6), (4, 2), (1, 4)]
    [(9, 6), (4, 6), (4, 4), (1, 2)]
     
    nombre de combinaisons differentes sans doublons 120

  18. #18
    Membre expérimenté
    Homme Profil pro
    Inscrit en
    Mars 2007
    Messages
    941
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Mars 2007
    Messages : 941
    Points : 1 384
    Points
    1 384
    Par défaut
    Les deux permutations inbriquées, sur 10 éléments, cela fera plus de 13168 milliards d'itérations.

    Il vaut mieux considérer, dans un premier temps, que l'ordre ne compte pas, cela ne donne que 11 solutions pour les deux listes de 10 éléments du premier post. Et ensuite calculer les permutations de ces solutions. Comme on sait déjà qu'il n'y a pas de couples répétés dans ces 11 solutions, toutes les permutations seront uniques (cela en fera tout de même 11*10! soit près de 40 millions).

    Pour que l'ordre ne compte pas, il suffit d'enregistrer comb dans res non pas sous forme de liste mais de set. Au passage le len(comb) (longueur de la liste comb) est constant; on peut donc le précalculer avant la boucle.

    Une optimisation est d'utiliser un set pour res également, afin d'accélérer le test comb not in res. Un set n'étant pas hashable, il ne peut pas être membre d'un autre set. Il faudra utiliser un frozenset pour comb.

    Après il ne reste plus qu'à générer les permutations des solutions trouvées.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    liste1 = [2,4,4,6,6,12,12,12,16,18]
    liste2 = [1,1,1,2,2,4,4,4,4,4]
     
    from itertools import permutations
     
    def combine(l1, l2):
        res = set()
        size = len(l1)
        for li in permutations(l2):
            comb = frozenset(zip(l1,li))
            if len(comb) == size and comb not in res:
                res.add(comb)
                yield comb
     
    counter = 0
    for comb in combine(liste1, liste2):
        print(comb)
        for p in permutations(comb):
            # faire ce qu'il faut
            counter += 1
    print(counter)
    Mais le fait que la fonction itertools.permutations ne tienne pas compte des doublons génère beaucoup de permutations inutiles de liste2. Sur les 3628800 permutations générées, il n'y en a en fait que 2520 différentes ! Remplacer cette fonction par une autre qui ne génère que les permutations uniques fera gagner beaucoup de temps lorsqu'il y a beaucoup de doublons comme dans liste2.
    Par exemple:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    liste1 = [2,4,4,6,6,12,12,12,16,18]
    liste2 = [1,1,1,2,2,4,4,4,4,4]
     
    from itertools import permutations
     
    def permuts(l):
        if len(l) == 0:
            yield []
        else:
            for e in set(l):
                l.remove(e)
                for p in permuts(l):
                    p.append(e)
                    yield p
                l.append(e)
     
    def combine(l1, l2):
        res = set()
        size = len(l1)
        for li in permuts(l2):
            comb = frozenset(zip(l1,li))
            if len(comb) == size and comb not in res:
                res.add(comb)
                yield comb
     
    counter = 0
    for comb in combine(liste1, liste2):
        print(comb)
        for p in permutations(comb):
            # faire ce qu'il faut
            counter += 1
    print(counter)

    La fonction permuts est implémentée naïvement et est beaucoup plus lente que itertools.permutations lorsqu'il n'y a pas de doublons (c'est pourquoi je ne l'ai pas réutilisée à la fin où je sais qu'il n'y a pas de doublons), mais elle est tout de même quelques centaines de fois plus rapide que cette dernière pour générer les permutations de liste2.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Afficher toutes les combinaisons possibles
    Par NELLLY dans le forum MATLAB
    Réponses: 1
    Dernier message: 07/01/2008, 22h09
  2. Algo pour toutes les combinaisons possibles
    Par rantanplan08 dans le forum Général Java
    Réponses: 6
    Dernier message: 03/01/2008, 10h45
  3. Réponses: 5
    Dernier message: 18/06/2007, 21h52
  4. Réponses: 16
    Dernier message: 20/10/2006, 17h31
  5. toutes les combinaisons possibles
    Par marocleverness dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 29/05/2006, 01h11

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo