Discussion :

[pseudocode]

Certe. C'etait pour minimiser le nombre de candidats. Mais c'est sur qu'il faudrait que je cherche dans Total-Solution et pas dans Reste.

Effectivement, les temps de calculs deviennent vite prohibitifs. De plus, ça ne semble pas solutionner le problème 9-6/5 chez moi.

[zhao]

peut etre qu'un programme qui ferais le tri (donc prog de Zavonen) methode monté carlo ( donc prog Pseudocode ) et mon "prog" verif combi oui je sais il est pas beau mais je l'aime bien mon "prog" mais je reve de remplacer ce que je faisais a la main par un programme mais c'est largement au dessus de mes competances pour le moment :-)
donc on genere tous les MAX possible ,on les passe a la moulinette avec une methode de monte carlo ou autre dans mon verif en mettant une borne par exemple si il trouve 18 ou 15 ou 14 bref un scanf il arrete et voire ce que cela donne .moi j'y crois je sais pas pourquoi :-)

PETITE ETUDE INTERESSANTE ( enfin je trouve :-) )

J'ai pris les 15 combinaisons de notre algo et j'ai note les performances a chaque tour dans mon prog " verif combi" idem pour 14 et la a mon avis il y a aucun doute que pour 15 on ne prends pas les plus optimal la preuve par les faits :

POUR ALGO 10 - 6/5 =15

parcours NB6 NB5 NB4 NB3 NB2 total
1 1 24 90 80 15 210
2 2 44 115 48 1 210
3 3 64 121 22 0 210
4 4 80 114 12 0 210
5 5 96 105 4 0 210
6 6 112 91 1 0 210
7 7 121 82 0 0 210
8 8 132 70 0 0 210
9 9 143 58 0 0 210
10 10 153 47 0 0 210
11 11 165 34 0 0 210
12 12 170 28 0 0 210
13 13 182 15 0 0 210
14 14 191 5 0 0 210
15 15 195 0 0 0 210


*************************************************************


POUR ALGO 10 - 6/5=14

parcours NB6 NB5 NB4 NB3 NB2 total
1 1 24 90 80 15 210
2 2 48 126 34 0 210
3 3 68 124 15 0 210
4 4 84 115 7 0 210
5 5 104 99 2 0 210
6 6 116 87 1 0 210
7 7 133 70 0 0 210
8 8 139 63 0 0 210
9 9 152 49 0 0 210
10 10 164 36 0 0 210
11 11 178 21 0 0 210
12 12 181 17 0 0 210
13 13 193 4 0 0 210
14 14 196 0 0 0 210

ps)j'ai mis les combinaisons dans l'ordre pour ma verification.
signifcation NBxxx = combien ais je de combinaisons a xxx chiffre par exemple si NB4 = 20 cela signifie que j'ai 20 combinaisons qui ont 4 chiffres de bon et seulement 4 comme notre objectif est 5 ce n'est pas bon bien sur :
On peut constater que dés la deuxieme combinaison les VALID de 14 est deja plus performante pourquoi ? tout simplement parce que j'ai deja 48 combi a 5 au lieu de 44 pour notre algo des la deuxieme combi j'ai deja eliminé les combi NB2 ce qui n'est pas le cas dans notre algo et si on continue de lire on constate ou il y a des faiblesses etc...
enfin comme d'habitude je crois tout cela est plus intuitif qu'autre chose donc.... :-)
On peut meme ce poser la question de savoir si 14 est bien le minimum ( cela doit etre possible je pense a verifier) car regardez bien les lignes suivantes dans algo 10-6/5 =14
entre la combi 7 et 8 je ne couvre que 6 combi a 5 de + que la 8 ce qui est tres peu comparer aux autre d'autant plus que de la
11 a 12 je n'en gagne que 3 .
7 7 133 70 0 0 210
8 8 139 63 0 0 210
9 9 152 49 0 0 210
10 10 164 36 0 0 210
11 11 178 21 0 0 210
12 12 181 17 0 0 210


Je rajouterais ceci , dans un premier temps il n'est pas necessaire de tester tous les chemins mais seulement 210*210 ( si je me trompe pas ) en prenant la plus performante en cas d'egalité ( mais la je pense qu'il y en auras moins car on teste nb6 nb5 nb4 nb3 nb2 ) on prends la premiere pour voire ce que cela donne ensuite suivant le resultat on peut envisager de prendre la deuxieme ou suivant un criter etc... ce qui est certain c'est que cette 2 ieme combi de 15 n'aurais pas ete accepté en tant que meilleur avec "prog-verif" donc pourquoi pas :-)

mince quel dommage je ne sais pas comment mettre le tableau en forme en edit pas de probleme mais quand je post les espaces disparaisse .
bon je vais essayer de mettre une image desolé .

http://img380.imageshack.us/my.php?image=ecran1fc8.gif

[Zavonen]

Zhao,
Je crois que tu fais fausse route.
Voici un programme Python qui calcule automatiquement les stats telles que tu les présentes:

Code python :

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
# -*- coding: cp1252 -*-
import random
from sets import Set
 
def Inter(L):
    return [X for X in L[0] if all([X in B for B in L[1:]])]
 
#décide si la décomposition de n en binaire comporte exactement p chiffres 1.
def hpcb(n,p):
    s=0
    while n:
        s+=n%2
        n=n/2
    return s==p
# retourne tous les nombres entre 0 et n-1 ayant p fois le chiffre 1 en système binaire
def fcar(p,n):
    return [i for i in range(0,n) if hpcb(i,p)]
 
def canreduce(X):
    return [Y for Y in Tab1 if communs(X,Y)>=5]
 
def proximL(L):
    NB6=[Y for Y in Tab1 if max([communs(X,Y) for X in L])==6]
    NB5=[Y for Y in Tab1 if max([communs(X,Y) for X in L])==5]
    NB4=[Y for Y in Tab1 if max([communs(X,Y) for X in L])==4]
    NB3=[Y for Y in Tab1 if max([communs(X,Y) for X in L])==3]
    NB2=[Y for Y in Tab1 if max([communs(X,Y) for X in L])==2]
    return [len(NB6),len(NB5),len(NB4),len(NB3),len(NB2)]
 
# associe une partie de L à p élément à un nombre
def assoc(L,h):
    k = len(L)-1
    M=[L[k-i] for i in range(0,k+1)]
    result=[]
    i=0
    while h:
        r=h%2
        if r:
            result.append(M[i])
        h=h/2
        i+=1
    result.reverse()
    return result
 
# retourne toutes les combinaisons de E à p éléments dans l'ordre
def Combinaisons (E,p):
    H=fcar(p,2**len(E))
    H.reverse()
    return [assoc(E,h) for h in H]
 
 
#calcule le nombre d'éléments communs aux listes X,Y
def communs(X,Y):
    n=0;
    for x in X:
        if x in Y:
            n+=1
    return n
 
# liste des éléments à conserver dans T2 selon le critère nombre d'éléments avec L <p
def Conserver(T2,L,q):
    return [X for X in T2 if communs(X,L)<q]
 
#Calcule combien de combinaisons X peut supprimer dans R sur la base de p éléments communs au moins
def PeutSupprimer(X,p):
    global Reste
    H=[L for L in Reste if communs(X,L)>=p]
    return len(H)
 
# détermine la combinaison qui supprime le plus de combinaisons dans T1
def TrouveSuivant(p):
    global Tab1
    s=PeutSupprimer(Tab1[0],p)
    S=Tab1[0]
    for X in Tab1:
        t= PeutSupprimer(X,p)
        if t >s:
            s=t
            S=X
    return S
 
# enleve l'élement X de la liste L
def Enleve(X,L):
    return [Y for Y in L if Y !=X]
 
#trace pour constater l'avancement
def Voir():
    global Reste, Valid,Tab1
    print len(Tab1),len(Reste),Valid[-1]
 
 
# effectue le traitement indiqué
def Traite(p):
    global Reste, Valid,Tab1
    Reste=Conserver(Reste,Tab1[0],5)
    X=[1,2,3,4,5,6];
    Valid.append(X)
    Tab1=Enleve(X,Tab1)# on enlève la première
    while Reste !=[]:
        X=TrouveSuivant(p)
        Reste=Conserver(Reste,X,p)
        Valid.append(X)
        Tab1=Enleve(X,Tab1)
 
#variables globales
Valid=[]
Tab1=[]
Reste=[]
 
def main():
    global Reste,Tab1,Valid
    N=range(1,11)# les nombres de 1 à 10
    Valid=[]
    Tab1=Combinaisons(N,6)
    Reste=Combinaisons(N,6)
    Traite(5)
    Tab1=Combinaisons(N,6)# rétablir Tab1 initial
    #test
    for i in range (1,16):
        print proximL(Valid[0:i])
 
if __name__ == '__main__':
    main()

Voici le résultat de l'exécution:

[1, 24, 90, 80, 15]
[2, 48, 126, 34, 0]
[3, 72, 127, 8, 0]
[4, 96, 109, 1, 0]
[5, 120, 85, 0, 0]
[6, 132, 72, 0, 0]
[7, 144, 59, 0, 0]
[8, 156, 46, 0, 0]
[9, 165, 36, 0, 0]
[10, 174, 26, 0, 0]
[11, 182, 17, 0, 0]
[12, 190, 8, 0, 0]
[13, 193, 4, 0, 0]
[14, 194, 2, 0, 0]
[15, 195, 0, 0, 0]

C'est un test pour un ensemble à 15 éléments non optimal, il démarre mieux qu'un ensemble optimal, et pourtant au bout du compte ...
Toute méthode visant à maximiser NB5, NB4 en séquence, est naturelle mais vouée à l'échec.

[zhao]

Merci beaucoup Zavonen bon je resterais encore un bon moment avec mon problème :-)

je continuerais a chercher car j'aime ça et si par miracle je trouve je ne manquerais pas de vous le signaler car vous m'avez toi et Pseudocode beaucoup aidé et j'ai appris énormément de choses grâce a vous et je vous en remercie .
Bon je vais continuer a travailler le C et réfléchir a mon problème et recommencer a zero :-)
@+ :-)

[Zavonen]

Pourquoi nous échouons ...
Ce problème est topologique par nature.
Je m'explique:
Considérons pour simplifier le cas des suites de 6 nombres.
Introduisons sur ces suites la distance:
d(X,Y) = nombre d'éléments distincts entre A et B
Nous cherchons à recouvrir l'ensemble des 210 combinaisons par 14 boules de rayon 1.
Toutes nos stratégies gloutonnes ('greedy') reviennent à chercher d'abord une boule unitaire englobant le maximum d'éléments puis une seconde englobant le maximum d'éléments restant et ainsi de suite ...
Mais en fait ce qu'il faut rechercher c'est 14 boules 'équiréparties' (bien distribuées dans l'ensemble).
Au lieu de chercher les unes à la suite des autres des boules gloutonnes, peut être est il plus judicieux de prendre à chaque fois des boules se trouvant à distance minimum (>=2) des autres ?
C'est juste une idée comme ça.

[Zavonen]

cf: Mon post précédent.
Approche prometteuse...
La plupart des suites de 16 combinaisons générées aléatoirement sur ce principe
effacent 209 combinaisons sur les 210.
Avec 17 on obtient un très grand nombre de solutions.
Je rappelle que la moyenne statistique de longueur des suites effaçant les 210 est de l'ordre de 40.
Avec 16 et un tirage aléatoire, on n'est qu'à 2 points de l'optimum connu et à 1 point de l'algorithme 'greedy'.
C'est un assez bon tir groupé, il faudrait maintenant trouver un critère qui, dans la liste des possibles effectue la bonne sélection.
Il manque donc encore quelque chose, si quelqu'un a une idée...

[zhao]

Bonjour Zavonen .

Je comprend un peu ce que tu veux dire et oui il manque quelque chose a chaque fois et parfois ce quelque chose est vraiment minime :-)
Je vais réfléchir de nouveau car peut être que c'est l'approche en elle même qu'il faut changer totalement bref pas évident mais si cela était le cas ce problème perdrais tout son intérêt :-)
Que veut tu dire par >=2 ? peut tu mettre un exemple avec des combinaisons par exemple TAB1 et TAB2 et comment tu les test exactement et pourquoi tu choisis tel ou tel combinaison ?

[Zavonen]

2 suites sont à une distance 0 si elles sont égales, à une distance 1 si elles diffèrent d'un numéro, à une distance 2 si elles diffèrent de deux numéros, etc...
Tu as une distance comme en géométrie la distance de deux points. Simplement ici les boules sont des carrés en dimension 2, des cubes en dimension 3, des hypercubes en dimension 6.
Un ensemble Valid est réducteur si tout élément de Tab1 est situé dans une boule de rayon 1 ayant son centre dans Valid.
Le jeu consiste à remplir donc un espace qui ressemble à un cube tronqué avec d'autres cubes (ou hypercubes) en en utilisant le moins possible, c'est donc bien un puzzle ou plutôt une sorte de tantrix.
Dans notre cas on remarque les boules ont toutes exactement 25 éléments, donc ce premier théorème. Un réducteur optimal aura forcément au minimum 9 éléments (on sait qu'en pratique c'est plus que ça). Le problème vient du fait que compte tenu de la forme et de la taille de l'ensemble à recouvrir et compte tenu de la taille et de la forme des cubes, le problème est difficile.
J'ai lu dans la littérature qu'il n'existe pas d'algo déterministe conduisant à une solution minimale.
Les gens mélangent donc des heuristiques comme celle que tu proposes, ou celle que je propose ou d'autres, ils les mélangent et finissent avec la force brute.
J'ai essayé de combiner ma dernière approche avec la tienne, et il semble que les deux méthodes soient incompatibles, si j'essaie en même d'écarter mes boules et de les prendre grosses, le résultat final est mauvais (c'est compréhensible on laisse plein de petits espaces vides qu'il faut venir combler à la fin avec des boules pleines).
Bref, on n'a guère avancé... Je vois que beaucoup de gens ont cherché, certains prétendent avoir trouvé (fait un google avec 'systèmes réducteurs' et tu verras). Personne ne donne aucune méthode. Je ne crois pas à cette technique pour gagner au lotto ou à un quelconque autre jeu. Au début c'était possible avec les chevaux mais les statisticiens de la française des jeux sont passés par là et on changé la règle du jeu pour ce qui concerne les combinaisons dans le désordre.
Il est temps pour moi de dire stop.
Ce problème est trop compliqué.

[zhao]

OK Zavonen je comprends maintenant ( du moins je crois ) :-)
Perso ce n'est pas pour jouer au loto car les combinaisons comme tu le sais je les aient déjà ,c'est un problème qui me plait si tu préfère c'est mon hobi :-)
Je vais donc continuer a chercher et un jour je trouverais la solution pour les 14 ça j'en suis sur car ( oui l'espoir fait vivre ;-) ) je suis tenace et persévérant .
Merci pour tout et surtout de votre patience a toi et Pseudocode .
Je vous tiendrais au courant .
@+ :-)

ps) serais t'il possible de vérifier avec une force brute soit algo glouton ou verif combi toutes les chemins possible pour 10 6/5 pour au moins savoir si 14 est bien le minimum ou alors même pour 10 cela est impossible ?

que faut 'til changer dans ton programme Zavonen pour qu'il face tous les chemins possible et s'arrete quand il en trouve soit 15 soit 14 etc...
Je parle du programme soit en C le dernier soit en pyton .

[Zavonen]

Par force brute directe, sans heuristique particulière, aucun de mes programmes n'est capable de venir à bout de ce problème (de déterminer l'ensemble réducteur optimal à14 éléments dans le cas 10- 5/6).
Tu penses bien que si cela avait été possible je l'aurais fait.
Bon courage !

[zhao]

ok :-)
je me disais aussi :-)
@+

[zhao]

Bonjour a tous :-)
Oui me revoilà car il y a encore une piste d'ont nous avions parler et que nous avons pas exploiter .
un ALGO Génétique .

d'ailleurs cela se traduit comment ce genre de chose ?
comment ça fonctionne ?
Pour mon problème cela se concrétiserais comment ?
ça se programme comment en C ?
etc. :-)
@+ :-)

ps) Je viens juste de penser a ça :
pourquoi faire tous les chemins pour trouver la solution ? ne peut t'on faire comme ceci :

JE suis en A et je veux allez a B en un minimum de Km (disons 100 ) ( voyageur de commerce mais je suis pas sur que ce que je pense est le meme probleme ou la meme solution)

au depart j'ai disons 5 chemins possibles je vais par conventions prendre le 1 j'arrive a une intersection et j'ai 2 chemins possible 1 qui m'indique B1=85km et B2=50km je prends B2 je continue et j'arrive a une intersection qui me dit c1=55km et C2=60km aucun de ses chemins est inferieur a B2 je quitte cet branche et je reviens en arriere a 1 et je compare le chemin 2 avec 1 pour voire si j'ai un chemin plus court que B1 etc... bref je sais pas si je m'exprime bien le but est bien sur d'eviter de faire tous les chemins et de revenir en arriere jusqu'as ce que j'arrive a B enfin bon je suis pas sur que vous comprenez ce que je veux dire :-)
toujours le meme probleme manque de connaissance :-)
@+ :-)

[pseudocode]

un ALGO Génétique .

d'ailleurs cela se traduit comment ce genre de chose ?
comment ça fonctionne ?
Pour mon problème cela se concrétiserais comment ?
ça se programme comment en C ?

Tu peux consulter les tutoriels de khayyam sur ce sujet:

http://khayyam.developpez.com/

[zhao]

Bonjour Pseudocode :-)

Merci pour le lien humm pas facile pour moi de comprendre enfin bon je vais essayer :-)
@+ :-)

[khayyam90]

Ah, voilà qu'on parle d'algos génétiques

De ce que j'ai pu comprendre de ce sujet assez pointu, c'est qu'il s'agit avant tout d'un problème de dénombrement où il faut trouver le nombre de grilles à jouer pour avoir n numéros parmi m numéros sortis dans un ensemble de p numéros possibles. On ne cherche même pas à savoir quelles sont ces grilles, on veut juste les dénombrer.

Je ne vois pas bien en quoi les algos génétiqes peuvent venir en aide, d'autant que le résultat exact semble escompté.

[pseudocode]

On ne cherche même pas à savoir quelles sont ces grilles, on veut juste les dénombrer.

heu... on veut quand même connaitre les grilles. Le but c'est de les jouer.

Je ne vois pas bien en quoi les algos génétiqes peuvent venir en aide, d'autant que le résultat exact semble escompté.

C'est juste que l'heuristique des algos génétiques (croisement/mutation) est sans doute meilleure qu'un pur monté-carlo. Ca ne sera sans doute pas optimal, mais je laisse zhao à ses rêves... P=NP, P=NP, P=NP, ...

[zhao]

Bonjour khayyam90,Pseudocode,Zavonen et a tous .

Oui laissez moi mon rêves en ses temps difficile les rêves sont important :-)

Bon ce n'est pas pour les jouer car j'ai déjà ses combinaisons :-)
Je voudrais enfin voire un programme qui puisse me les sortir , j'ai lu ton pdf sur le voyageur de commerce et celui sur le astar et je me demandais si il ne serais pas possible de trouver ce minimum "CONNU" avec un de ses Algo je dit bien connu et non Reel qui lui est de tout e façon hors de portée si je ne me trompe pas le probleme du voyageur de commerce a partir d'un certain nombre de villes est lui aussi un probleme NP pourtant on arrive a trouver des solutions optimal .

si on prends mon problème et que l'ont considère les programmes de Zavonen on est tres proche de la solution optimal et on est même pour 10 6/5 =14 a l'optimal avec le Programme de pseudocode malheureusement il ne fonctionne que pour 10 6/5 .
Donc la seule solution est de combiner ses solution avec une heuristique et il ne reste que les Algo dit genetique ou de type A comme dans le pdf Astar .
voila mon souhait :-)
@+ :-)

[khayyam90]

si je ne me trompe pas le probleme du voyageur de commerce a partir d'un certain nombre de villes est lui aussi un probleme NP pourtant on arrive a trouver des solutions optimal .

il est en effet NP complet mais on ne peut pas trouver à coup sûr la solution optimale. Les méta heuristiques donnent des solutions qui peuvent peut-être être optimales. Mais rien ne l'affirme.
Dès lors qu'on cherche une solution optimale, les méta heuristiques sont déconseillées, elles n'apportent que des solutions approchées et on n'a aucun moyen de dire si une solution est optimale (sauf en trouvant une meilleure solution qui infirmera l'optimalité de la solution précédente).

si on prends mon problème et que l'ont considère les programmes de Zavonen on est tres proche de la solution optimal et on est même pour 10 6/5 =14 a l'optimal avec le Programme de pseudocode malheureusement il ne fonctionne que pour 10 6/5 .
Donc la seule solution est de combiner ses solution avec une heuristique et il ne reste que les Algo dit genetique ou de type A comme dans le pdf Astar .

En combinant des résultats de plusieurs programmes via une heuristique (algos génétiques ou autre) on pourra obtenir un résultat mais rien ne garantira qu'il sera optimal.
Et A* (le pdf Astar) ne sert qu'à rechercher un chemin dans un graphe. Son chemin peut être optimal sous certaines conditions.

[zhao]

En combinant des résultats de plusieurs programmes via une heuristique (algos génétiques ou autre) on pourra obtenir un résultat mais rien ne garantira qu'il sera optimal.

C'est exactement ce que je souhaite en C pour déjà voire le résultat ensuite comprendre ce genre de programme etc... bref savoir , étudier,avoir un résultat tangible au moins égal a ce que Zavonen et Pseudocode on fait et qui sait peut être plus tard le modifier je serais vraiment heureux d'avoir ceci , ce qui serais super c'est de fixer par exemple des bornes d'arrêter la recherche quand il a trouver comme résultat 15 ou 14 ( je parle pour 10 6/5 ) et d'avoir la possibilité de choisir une recherche pour 10 ou 11,.....et bien sur de stocker ses 14 ou 15 ou... combinaisons pour pouvoir les afficher etc...
Voila un de mes rêves comme le dit si bien Pseudocode :-)
ensuite promis je vous laisse tranquille jusqu'à ce que je trouve quelque chose d'intéressant que je posterais sur le forum :-)

Donc svp faites moi rêver :-)
@+ :-)

[Zavonen]

Je reviens sur un de mes posts précédents concernant un façon 'topologique' de voir les choses.
L'algo basé sur cette remarque (voir code ci-après) est particulièrement simple (beaucoup plus simple que le glouton) et très rapide.
Pour ce qui concerne ses performances (mesurées ici dans le cas 10 5/6), on obtient 41% de solutions dans des ensembles de longueur 17 ainsi construits.
Je trouve que le rapport qualité/complexité est plutôt bon.
Il reste que cet algo ne trouve ni l'optimal, ni une solution à 15, ni même à 16.
Il trouve cependant beaucoup de 'presque solutions' de longueur 16 effaçant 209 éléments sur les 210.
Il est si rapide qu'on peut sans doute le raffiner. Ici comme vous voyez je prends à chaque fois la première boule à distance >=2 de l'ensemble Valid. Parmi toutes celles qui vérifient cette condition, il en est peut être une qui est "plus égale que les autres". Mais selon quel critère ? Pas la gloutonnerie en tout cas. J'ai déjà essayé et expliqué pourquoi cela ne marche pas. L'idée serait peut être de rendre Valid 'le plus compact possible' à chaque étape, et lui éviter de s'étirer pour remplir au plus vite tout l'espace.

Code python :

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
# -*- coding: cp1252 -*-
 
#décide si la décomposition de n en binaire comporte exactement p chiffres 1.
def hpcb(n,p):
    s=0
    while n:
        s+=n%2
        n=n/2
    return s==p
# retourne tous les nombres entre 0 et n-1 ayant p fois le chiffre 1 en système binaire
def fcar(p,n):
    return [i for i in range(0,n) if hpcb(i,p)]
 
def canreduceL(L):
    return [Y for Y in Tab1 if any([communs(X,Y)>=5 for X in L])]
# associe une partie de L à p élément à un nombre
def assoc(L,h):
    k = len(L)-1
    M=[L[k-i] for i in range(0,k+1)]
    result=[]
    i=0
    while h:
        r=h%2
        if r:
            result.append(M[i])
        h=h/2
        i+=1
    result.reverse()
    return result
 
#calcule le nombre d'éléments communs aux listes X,Y
def communs(X,Y):
    n=0;
    for x in X:
        if x in Y:
            n+=1
    return n
 
# retourne toutes les combinaisons de E à p éléments dans l'ordre
def Combinaisons (E,p):
    H=fcar(p,2**len(E))
    H.reverse()
    return [assoc(E,h) for h in H]
 
def dist(X,Y):
    return 6 - communs(X,Y)
 
def distL(X,L):
    return min([dist(X,Y) for Y in L])
 
#variables globales
Valid=[]
Tab1=[]
Reste=[]
 
def main():
    global Reste,Tab1,Valid
    N=range(1,11)# les nombres de 1 à 10
    Valid=[]
    Tab1=Combinaisons(N,6)
    Reste=Combinaisons(N,6)
    stat=0
    for i in range(0,210):
        Valid=[Tab1[i]]
        for j in range(0,17):
            for Y in Tab1:
                if distL(Y,Valid) >=2:
                    Valid.append(Y)
                    break
        if len(canreduceL(Valid))==210:
            stat+=1
    print float(stat)/210
 
if __name__ == '__main__':
    main()