Combinaisons de 9 sur 8000 max 3 obkets similaires entre les résultats

[fdfdfd]

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

[fatal_error]

salut

basiquement et sans optimisation :

Code: Tout sélectionner

NB_ENR = 9 //le nombre d'objets par "main"
MAX_ENR = 9000  //le nombre d'objets total
pour enr_1 = 1 a MAX_ENR - NB_ENR //enr_1 represente le premier objet de la main
 pour enr_2 = enr_1+1
  pour enr_3 = enr_2+1
  ...
     pour enr_9 = enr_8 +1
      si valide (enr_1,enr_2,...,enr_9) //une fois la main generee on regarde si elle est valide
       ajouter a listeSolution v[enr_1,enr_2,...,enr_9]  //si oui, on lajoute aux soluces
      finsi
     fin pour
   fin pour
 fin pour
fin pour

et

Code: Tout sélectionner

bool valide(enr_1,...,enr_9) //retourne vrai si main valide, faux sinon
 pour i = 1 a 8
  pour j = i  a 9 //suppose reflexivite
    si similaire(enr_i,enr_j)
      compteurIdentique+=1 //si plus de trois objets se ressemblent
      si compteurIdentique >3
        return false
      finsi
    finsi
  fin pour
 fin pour
 return true
   

Bon, il y a mieux. Je pense notamment a faire des classes d'objets, mais comme on sait pas trop ce que représente ces enregistrements et les attributs qui font que certains obejts soient similaires, voila un algo passe partout ( moyennant des ptites erreurs, mais dans le principe ca doit etre bon)

[fdfdfd]

Bonjour
merci pour ta réponse,
je ne comprends pas tout

Supposons que nos objets soient des nombres

ta proposition ne génère que des mains avec des séries qui se suivent ? non ?
1 2 3 4 5 6 7 8 9 pour le premier

autre chose je ne comprend pas la fonction de validation ? tu compares quoi les enregistrement de tous les résultats ?

merci à toi pour ton coup de main

FD

[uztop]

Salut,

non, il y a 9 boucles for imbriquées dans la fonction de fatal_error; ca donne donc bien toutes les possibilités (sauf les trucs comme 1-1-1-1-1-1-1-1-1, je ne sais pas s'ils doivent être acceptés)

Pour la fonction qui sert à éviter les répétitions, en fait, je crois qu'il faudrait que tu précises le même problème: est ce que tu veux éviter d'avoir plus de trois fois le même numéro d'enregistrement (par exemple le numéro 12) ou tu veux éviter d'avoir plusieurs enregistrement identiques selon un autre critère (en gros, est ce que par exemple, le 12 et le 18 peuvent être identiques ?)?
fatal_error a supposé que deux enregistrements avec des numéros différents peuvent être quand même identiques

Sinon fatal_error, j'ai jamais vu les bouces écrites en français comme ça (pour au lieu de for), ça se fait ?

[fatal_error]

re,

en fait, c'est du pseudo code, au début je trouvais ca super relou mais au final je trouve ca pas mal. Lorsque j'écris des for, j'ai du mal à m'abstraire du code, alors qu'en ecrivant des pour, tant que, je trouve plus facile de donner les idées générales (avec l'approximation de la syntaxe)

[uztop]

oui pourquoi pas, c'est un peu surprenant mais c'est vrai que ça permet de s'abstraire du code.

Sinon, je ne sais pas quels sont les critères pour que 2 enregistrements soient similaires mais ton code ne prend pas les séries comme (1-1-1-2-3-4-5-6-7), je ne sais pas si elles devraient être acceptées ou pas.

[fatal_error]

En fait, je crois que j'ai pas du tout compris la question.

Moi je partais du principe qu'a lintérieur d'une main (donc de 9 enregistrement pris au hasard), il fallait qu'il n'y ait pas 3 enregistrements égaux, ou du moins 3 paires d'enregistrement strictement égales...

En relisant l'énoncé, j'ai l'impression que a la sortie, on a un nombre de mains, disons le sac, tel que en prenant deux mains au hasard dans le sac, il n'y a pas plus de trois objets de la première main, qui soient identiques a la seconde.

Du coup, si c'est ca, l'algo est carrément a coté

[uztop]

oui en relisant bien c'est comme ça que je le comprend aussi; si on a tiré (1-2-3-4-5-6-7-8-9), on a le droit de prendre (1-2-3-10-11-12-13-14-15) mais pas (1-2-3-4-10-11-12-13-14).

Mais alors la fonction de vérification est horrible, enfin je ne vois pas comment faire quelque chose de simple.

[fdfdfd]

Merci à vous pour vos réponses,
C'est bien ça, vous avez bien compris l'énoncé
deux main prise au hasard dans le sac doivent avoir au maximum 3 objets identiques

J'en ai trouvé quelques unes empiriquement
mais j'arrive pas à trouver une règle générale et simple
je suis d'ailleurs que à moitié sûr que ce que je sors est exact
voilà si vous avez d'autrees idées ?

Je travaille maintenant avec le même problème mais sur des série de 8 avec max 2 objets identiques entre tous les éléments du sac
je suis sûr que un bon matheux doit pouvoir sortir une généralisation de ce pb

merci à vous
FD

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

For i = 1 à 1000
------------------
For j = 0 à (i-1)
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 /

[fatal_error]

re,

tout d'abord, je ne comprends pas du tout a quoi corresponde les i,j,k et la syntaxe que tu emploies fdfdfd.

Pour revenir sur lenoncé, jimagine que ce qui t'intéresse, c'est le sac avec le plus de mains possibles dedans.

Une idée, serait de faire plein de tas, puis de les regrouper au fur et a mesure. Plus précisément :
on commence par faire tous les tas de deux mains possibles. Une fois faits, on tente les tas ( paire + paire). Une paire etant constituée de deux mains.
On peut ignorer les tas (paire+main), car pour égaliser un tas (paire + paire), il faudrait rajouter une main et obtiendrait alors un tas (paire + paire).
Du coup, on continue, jusqu'a ce qu'on trouve pas de solution.
Une fois qu'on trouve pas de solutions, ca veut dire qu'on ne peut plus faire des tas ( tas_n_1+tas_n_2) avec card(tas_n_1)=card(tas_n_2). tas_n_1 représente un tas de reference au niveau n, tas_n_2 represente un tas quelconque different de tas_n_1 au niveau n.
on doit donc se limiter a tas_n_1 + tas_{n'} avec card(tas_n')card(tas_n_1)/2
tas_n' représente un tas quelconque de niveau inférieur a tas_n_1

Pour trouver tas_n', on peut tenter pour tous les tas_n_2 denlever un objet, et de voir si ca colle avec tas_n_1. Si ca colle, on a trouvé un sac (pe pas le seul) mais qui contient un max delements.
Si ca colle pas, on le fait pour tous les tas_n_j. Si ca colle toujours pas, il faut alors songer a un tas tas_n_1 + tas_n' avec card(tas_n')=card(tas_n_1)+2

pour tenter doptimiser un peu ca, on peut pour chaque tas, mettons pour tas_n_1, backlister les mains qui sont incompatibles avec tas_n_1. Ainsi quand tas_n_1 rencontre tas_n_2, on peut deja savoir si tas_n_2 est candidat potentiel (sous reserve qu'aucune de ses mains ne figure dans la blacklist).
On peut grace a cette blackliste, trouver un sac minimum composé des mains de tas_n_1 et quelques unes (les valides) de tas_n_2.

Apres, pe qu'il vaut mieux faire tous les tas possibles, mais je pense que ca risque de faire péter lhorloge (les deux). J'ai aussi un petit doute sur le fait qu'on exclue des possibilités (notamment si card(tas_n')+2
En freestyle, donc surement une boulette en vue.