Discussion :

[Hesiode]

Bonsoir,

J'ai plusieurs valeurs, par exemple : 1/2/3/4/5/6

Je voudrais par un algo obtenir tout les couples possible, mais avec ces conditions :
- un couple ne peut pas être fait de 2 même valeurs
- une valeur ne peut être utilisé qu'une fois

En gros, je voudrais arriver au resultat suivant :
1. [1/2] [3/4] [5/6]
2. [1/3] [2/6] [4/5]
3. [1/4] [2/5] [3/6]
4. [1/5] [2/3] [4/6]
5. [1/6] [2/4] [3/5]

J'ai tente plusieurs algo, mais à chaque fois un moment ou un autre je tombais sur des couples déjà formés

Autre formulation pour mieux comprendre :
J'ai tout les couples d'une serie de caractere, par exemple a/b/c/d
ce qui nous donne :
(a/b)(a/c)(a/d)
(b/c)(b/d)
(c/d)

Je voudrais tous les mettre dans un tableau (donc 2x3), sans qu'il y ai 2 fois ou plus le même caractere sur une ligne,
par exemple, le bon tableau donnerai :
1 : (a/b) (c/d)
2 : (a/c) (b/d)
3 : (a/d) (b/c)

Merci beaucoup

[j.p.mignot]

Pour la série
1,2,3,4,5,6 vous cherchez ''la'' solution
1. [1/2] [3/4] [5/6]
2. [1/3] [2/6] [4/5]
3. [1/4] [2/5] [3/6]
4. [1/5] [2/3] [4/6]
5. [1/6] [2/4] [3/5]

Précisez car je ne vois pas du tout comment vous pouvez sélectionner votre soulution plutôt que, par exemple :

1. [1/2] [3/5] [4/6]
2. [1/3] [2/6] [4/5]
3. [1/5] [2/4] [3/6]
4. [1/4] [2/3] [5/6]
5. [1/6] [2/5] [3/4]

Le problème me semble mal posé.

[Nemerle]

Précisez car je ne vois pas du tout comment vous pouvez sélectionner votre soulution plutôt que, par exemple :

1. [1/2] [3/5] [4/6]
2. [1/3] [2/6] [4/5]
3. [1/5] [2/4] [3/6]
4. [1/4] [2/3] [5/6]
5. [1/6] [2/5] [3/4]

Le problème me semble mal posé.

Et bien si, dans sa 2de précision:

Je voudrais tous les mettre dans un tableau (donc 2x3), sans qu'il y ai 2 fois ou plus le même caractere sur une ligne,

Tu cherches en fait une table de toutes les rencontres possibles à 2n joueurs dans une compétition en n tours:

Tu commences par 1- contre 2 (soit [1/2] dans ta notation), 3 contre 4,...,...,(2n-1) contre 2n. Ecrivons les en lignes:

(dans ta notation: 1. )
12
34
56
...
(2n-1)(2n)

Ensuite, tu fais une permutation circulaire en laissant un joueur fixe, par exemple 1: ta permutation est alors sur (2,3,...,2n), dans le sens inverse des aiguilles d'une montre par exemple:

(dans ta notation: 2. )
14
26
38
...
(2n-5)(2n)
(2n-3)(2n-1)

Tu termines tes tours de permutations, et c'est bon!!

[Zavonen]

Votre problème n'a aucune solution pour un ensemble à un seul élément
Il a une et une seule solution pour un ensemble à deux élements
Pour un ensemble à n éléments:
Vous pouvez associez ce premier élément à chacun des n-1 restant et combiner cela avec toutes les solutions pour les n-2 restants.
Cela dit, dans votre exemple vous "manquez" des solutions:
Je vous cite:
En gros, je voudrais arriver au resultat suivant :
1. [1/2] [3/4] [5/6]
2. [1/3] [2/6] [4/5]
3. [1/4] [2/5] [3/6]
4. [1/5] [2/3] [4/6]
5. [1/6] [2/4] [3/5]
Pourquoi ne pas prendre aussi [1/2][3/5][4/6] ???
Il faudra donc faire une réurrence descendante de pas 2 avec deux conditions terminales correspondant à n=1 ou à n=2 selon la parité du paramètre.

[Nemerle]

Il faudra donc faire une réurrence descendante de pas 2 avec deux conditions terminales correspondant à n=1 ou à n=2 selon la parité du paramètre.

n impair n'est pas l'objet du problème et il n'y a de toute façon pas à faire de récurrence la-dedans (cf post + haut).

[Zavonen]

n impair n'est pas l'objet du problème et il n'y a de toute façon pas à faire de récurrence la-dedans (cf post + haut).

Pour peu que j'ai compris votre problème, ce petit programme Python devrait faire l'affaire.

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
 
# -*- coding: cp1252 -*-
 
import copy
 
def pprint (L): # seulement pour un bel affichage
    for i in range (0,len(L)):
        print L[i]
    return
 
 
 
 
def supprime( L, i, j):# enlève les éléments d'indice i et j de la liste L
    R=[]
    for k in range(0,len(L)):
        if ((k!=i)and(k!=j)):
            R.append(L[k])
    return R
 
def Rencontres (L): # renvoie la liste des possibilités de rencontres
    S=[]
    if len(L)==2:
        return [[L]] # terminaison de la récursivité deux joueurs= une seule rencontre
    else:
        for i in range (1,len(L)):
            R=Rencontres(supprime(L,0,i))#appel récursif
            for j in range (0, len(R)):
                T=R[j]
                T.append([L[0],L[i]])
                S.append(T)
    return S
 
 
 
 
 
pprint (Rencontres ([1,2,3,4, 5 ,6,7,8]))