Discussion :

[fdfdfd]

Bonjour,

j'ai une liste de 8000 enregistrements

je cherche à générer des combinaisons de 9 enregistrements sans répétitions parmi les 8000 enregistrements

MAIS SUBTILITE chacune de ces combinaisons ne DOIT avoir AU MAXIMUM que 3 enregistrements similaires à une autre.

Je m'explique
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 10 >> pas OK
1 2 3 10 11 12 13 14 15 16 >> OK

Bah je galère, si vous avez une idée d'algorithme je suis ultra preneur, j'ai creusé toute la journée là dessus !

vous avez une idée ?

merci à tous

FD

[micetf]

Combien de combinaisons dois-tu générer ?
Fred

[fdfdfd]

le maximum possible
ce que je cherche c'est un algo pour les générer
et si je pouvais aussi calculer leur nombre possible ça serait super

je suis pas un habitué des forums donc j'ai collé un autre message dans un autre sujet par erreur, voici le détail de mon message,

merci à tous,

Bonjour,

Mes maths sont assez loin !!

Je cherche un algorithme pour générer toutes les combinaisons sans répétitions de 9 enregistrements sur 8000 enregistrements MAIS avec AU MAXIUM 3 enregistrements identiques entre 2 combinaisons.

Concrètement, j'ai 8000 objets j'en tire 9 sans répétitions et sans tenir compte de leur ordre, je veux tous les résultats ayant au maximum 3 objets similaires entre eux. C'est à dire que chaque résultat ait au maximum 3 objets similaires aux autres résultats.

Vous avez une idée de comment procéder ?
Si d'ailleurs en prime je pouvais calculer le nombre de résultats que cela peut générer ça serait super,

merci à tous,

FD

[marcha]

Salut,

Pas sur d'avoir bien compris la question :-)

La première idée qui m'est venue c'est de prendre les 9 premiers
enregistrements des 8000 pour créer la première combinaison.

Ensuite pour créer les autres combinaisons, on prends les 6 suivants
enregistrements des 8000 et on y ajoute les 3 derniers enregistrement
de la combinaison précédente, et ainsi de suite.

Ceci te garanti de ne pas avoir plus de 3 enregistrements en commun

Mais je pense qu'il manque une information à ta question, car je suppose
que tu vas nous dire que ma solutions et trop simpliste :-)

[pseudocode]

La première idée qui m'est venue c'est de prendre les 9 premiers
enregistrements des 8000 pour créer la première combinaison.

Ensuite pour créer les autres combinaisons, on prends les 6 suivants
enregistrements des 8000 et on y ajoute les 3 derniers enregistrement
de la combinaison précédente, et ainsi de suite.

Ceci te garanti de ne pas avoir plus de 3 enregistrements en commun

Ca garantit meme qu'il y en a toujours 3 en commun.

Une variante de ce principe, c'est de retirer de l'ensemble de départ 6 éléments parmi les 9 tirés. Ensuite on tire à nouveau 9 éléments parmi les 8000-6 = 7994 éléments restants, etc.

[fdfdfd]

merci à vous deux pour voss réponses,
effectivement vos methodes sont impec c'est ce que j'avais appliqué ça me permet effectivement de générer certaines combinaisons

Mais j'en voudrais le maximum possible, du moins un plus grand nombre que celle généré seulement par ce que vous proposez

Si vous avez une idée

en gros pour l'instant voilà ce que je fais
1 2 3 4 5 6 7 8 9
1 2 3 10 11 12 13 14 15
etc.
1 2 3 7989 7990 7991 7992 7993 7994 7995

>> ça m'en fait 1332 environ

Ensuite je décalle de 3
4 5 6 7 8 9 10 11 12
4 5 6 13 14 15 16 17 18
etc.
4 5 6 7992 7993 7994 7995 7996 7997 7998

>> ça m'en fait 1331 environ

Ensuite on peut partir sur des décallages de 3 entre les chiffres consécutifs
1 4 7 etc. (sur cette série on peut en faire 2 commencer par 1 4 7 puis par 10 13 16)
2 5 8 etc. (sur cette série on peut en faire 2 commencer par 2 5 8 puis par 11 14 17)
3 6 9 etc. (sur cette série on peut en faire 2 commencer par 2 5 8 puis par 11 14 17)

>> en gros tout ça permet de sortir environ 2600 nouvelles combinaisons

Puis on augmente le décallage à 4 etc.

ça permet d'en sortir un certain nombre mais pas tant que ça finalement

[marcha]

Salut,

Nous sommes bien d'accord que pour toi, les deux séries suivantes
sont les mêmes ?

1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 9 8

D'autre part on pourrait essayer de ramener ton problème
à une taille plus humaine :-) par exemple, chercher
des groupes de 9 lettres de l'alphabet dont pas plus de 3
correspondent ?

abc defghi jklmno pqrstu vwxyz

abc defghi
abc jklmno
abc pqrstu

etc...

qu'en pensez-vous ? ensuite on extrapole à 8000 ?

[fdfdfd]

Bon j'ai trouvé comment en générer plus de 6M déjà donc c'est bon pour moi merci à tous,

la solution que j'ai pour l'instant est la suivante
pour simplifier ci-dessous je considère que j'ai 9000 objets et non 8000 comme dit initialement plus haut dans la discussion

1) j'en génère environ 2,6 M avec ça

For i = 1 à 1000
------------------
For j = 1 à i
For k = 0 à (9000/9*i)
1+j / 1+i+j / 1+2i+j // 1+3i+j+6*i*k / 1+4i+j+6*i*k / 1+5i+j+6*i*k / 1+6i+j+6*i*k / 1+7i+j+6*i*k / 1+8i+j+6*i*k /

2) j'en génère dans les 4M avec

avec 9037 objets pour simplifier

For j = 0 à 991
For k = 1 à [9036-(36+9*(j+9))]
k / k+j+1 / k+j+1+2 / k+j+1+2+3 / k+j+1+2+3+4 / k+j+1+2+3+4+5 / k+j+1+2+3+4+5+6 / k+j+1+2+3+4+5+6+7 / k+j+1+2+3+4+5+6+7+8 /