PHP

Code pour "tirage avec remise sans ordre"

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Code pour "tirage avec remise sans ordre"

Tapco

Bonjour à tous,

me voici confronté à un problème, je dois réaliser un code (PHP) afin d'avoir toutes les combinaisons possibles "tirage avec remise sans ordre"

Disons que j'ai 3 colonnes qui peuvent prendre une valeur de 0 à 5.

le résultat est donc le suivant :

0-0-0
0-0-1
0-0-2
0-0-3
...
0-1-1
0-1-2

Du coup comme l'ordre n'est pas pris en compte, 0-0-1 = 1-0-0 je ne sais pas comment le vérifier avec mon code.

---------------
Henriot Steven

Publicité

rat de combat

attention rongeur méchant!

Tu tries tes trois valeurs selon la valeur (1<2<3 etc) et ensuite tu peux comparer si tu as déjà cette combinaison.

Message cité 1 fois

---------------
Si vous ouvrez un sujet merci de ne pas le "laisser mourir" subitement et de le marquer comme "résolu" le cas échéant!

dede_sav

Bonjour,

Si tu changes ton format de donnée tu n'aura plus le soucis ...
Par exemple, un tableau de 6 cases où tu stockerais le nombre de chiffre dans une chaine
0-0-1 = 1-0-0 = 2-1-0-0-0-0 => Il y deux 0, un 1, zero 2, zero 3, zero 4 et zero 5.

0-3-1 = 3-0-1 = 1-1-0-3-0-0 => Il y un 0, un 1, zero 2, un 3, zero 4 et zero 5.

edit: [:rttolivers] grillé par une solution plus simple

Message édité par dede_sav le 09-07-2018 à 17:22:21

Tapco

rat de combat a écrit :

Tu tries tes trois valeurs selon la valeur (1<2<3 etc) et ensuite tu peux comparer si tu as déjà cette combinaison.

Je ne suis pas sûr de comprendre ou alors j'ai du mal m'exprimer.

Ce que je souhaite c'est trouver toutes ces valeurs pour les mettre dans un tableaux.
et je dispose de 2 variables.

- le nombre de cases > p
- le nombre d'index par case > n

Disons p = 4 et n = 10

le résultat que je souhaite dans mon tableau sera celui la

0-0-0-0
0-0-0-1
0-0-0-2
.....
0-0-0-10
0-0-1-1
0-0-1-2
.....
10-10-10-10

---------------
Henriot Steven

MaybeEijOrNot

but someone at least

Bonjour,

Un petit peu d'observation (3 tirages avec remise, 4 possibilités par tirage) :

0 0 0 1 0 0 2 0 0 3 0 0
0 0 1 1 0 1 2 0 1 3 0 1
0 0 2 1 0 2 2 0 2 3 0 2
0 0 3 1 0 3 2 0 3 3 0 3

0 1 0 1 1 0 2 1 0 3 1 0
0 1 1 1 1 1 2 1 1 3 1 1
0 1 2 1 1 2 2 1 2 3 1 2
0 1 3 1 1 3 2 1 3 3 1 3

0 2 0 1 2 0 2 2 0 3 2 0
0 2 1 1 2 1 2 2 1 3 2 1
0 2 2 1 2 2 2 2 2 3 2 2
0 2 3 1 2 3 2 2 3 3 2 3

0 3 0 1 3 0 2 3 0 3 3 0
0 3 1 1 3 1 2 3 1 3 3 1
0 3 2 1 3 2 2 3 2 3 3 2
0 3 3 1 3 3 2 3 3 3 3 3

Le mieux étant de ne simplement pas générer les combinaisons en double, la solution devrait être assez simple après observation.

Message cité 1 fois
Message édité par MaybeEijOrNot le 09-07-2018 à 20:45:44

---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.

Tapco

MaybeEijOrNot a écrit :

On voit bien effectivement, sauf qu'il en manque

210, 310 a vu d’œil

---------------
Henriot Steven

MaybeEijOrNot

but someone at least

Tapco a écrit :

On voit bien effectivement, sauf qu'il en manque

210, 310 a vu d’œil

De quoi? Il ne manque rien, regarde mieux. En rouge, les doublons. J'ai quand même mis l'axe de symétrie en évidence...

Citation :

0 0 0 1 0 0 2 0 0 3 0 0
0 0 1 1 0 1 2 0 1 3 0 1
0 0 2 1 0 2 2 0 2 3 0 2
0 0 3 1 0 3 2 0 3 3 0 3

0 1 0 1 1 0 2 1 0 3 1 0
0 1 1 1 1 1 2 1 1 3 1 1
0 1 2 1 1 2 2 1 2 3 1 2
0 1 3 1 1 3 2 1 3 3 1 3

0 2 0 1 2 0 2 2 0 3 2 0
0 2 1 1 2 1 2 2 1 3 2 1
0 2 2 1 2 2 2 2 2 3 2 2
0 2 3 1 2 3 2 2 3 3 2 3

0 3 0 1 3 0 2 3 0 3 3 0
0 3 1 1 3 1 2 3 1 3 3 1
0 3 2 1 3 2 2 3 2 3 3 2
0 3 3 1 3 3 2 3 3 3 3 3

Message cité 1 fois
Message édité par MaybeEijOrNot le 09-07-2018 à 21:05:50

---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.

Tapco

MaybeEijOrNot a écrit :

De quoi? Il ne manque rien, regarde mieux. En rouge, les doublons. J'ai quand même mis l'axe de symétrie en évidence...

Citation :

0 0 0 1 0 0 2 0 0 3 0 0
0 0 1 1 0 1 2 0 1 3 0 1
0 0 2 1 0 2 2 0 2 3 0 2
0 0 3 1 0 3 2 0 3 3 0 3

0 1 0 1 1 0 2 1 0 3 1 0
0 1 1 1 1 1 2 1 1 3 1 1
0 1 2 1 1 2 2 1 2 3 1 2
0 1 3 1 1 3 2 1 3 3 1 3

0 2 0 1 2 0 2 2 0 3 2 0
0 2 1 1 2 1 2 2 1 3 2 1
0 2 2 1 2 2 2 2 2 3 2 2
0 2 3 1 2 3 2 2 3 3 2 3

0 3 0 1 3 0 2 3 0 3 3 0
0 3 1 1 3 1 2 3 1 3 3 1
0 3 2 1 3 2 2 3 2 3 3 2
0 3 3 1 3 3 2 3 3 3 3 3

mal compris la réponse. Donc oui il y a toute les combinaisons. Oui il faut éviter de générer les doublons mais comment faire en PHP ?

---------------
Henriot Steven

MaybeEijOrNot

but someone at least

1- Comment ferais-tu pour générer toutes les combinaisons ?
2- Sur quels paramètres pourrais-tu jouer pour ne pas générer les combinaisons en trop ?
3- D'après les observations, quelle règle peux-tu établir à propos des paramètres afin de ne générer que les combinaisons uniques ?

Message cité 1 fois
Message édité par MaybeEijOrNot le 09-07-2018 à 21:51:34

---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.

Tapco

MaybeEijOrNot a écrit :

1- Comment ferais-tu pour générer toutes les combinaisons ?

boucle, mais ça j'ai réussi.

MaybeEijOrNot a écrit :

j'en suis ici, je ne sais pas comment éviter les doublons étant donné que l'ordre n'a pas d'importance. Et en vrai p peut monter jusqu'à 20 et n vers les 200.
Si je peux éviter de trouver les doublons pour éviter la perte de temps...

---------------
Henriot Steven

Publicité

MaybeEijOrNot

but someone at least

Tu ne fais pas qu'une boucle a priori, ou alors j'ai raté quelque chose, je pense que tu en fais plusieurs. Sur une boucle tu n'as que 3 paramètres :
- valeur initiale
- vitesse d'incrémentation
- valeur finale

Dans mon exemple, tu as 3 tirages donc 3 boucles imbriquées (de variables $i, $j et $k). Ces 3 variables peuvent prendre pour valeurs 0, 1, 2 ou 3.
Si tu regardes les tirages que j'ai écrit, on prend la première colonne, soit tous les tirages commençant par 0. On peut donc pour $i = 0, pendre $j et $k entre 0 et 3.
Mais pour $i = 1 il faut commencer à éliminer des valeurs. Toutes celles ayant $k = 0.
Puis pour $i = 2, on remarque qu'il faut éliminer les valeurs pour $k = 0 ou $k = 1, etc.

Par contre je ne sais si p est le nombre de tirages ou le nombre de valeurs possibles. Mais avec p = 20 et n = 200 il va peut-être falloir choisir une autre stratégie que les boucles imbriquées. Déjà parce que ton nombre de boucles est prédéfinie et qu'en plus tu exploses la complexité de ton algorithme.

Que cherches-tu à faire au final ?

Message édité par MaybeEijOrNot le 09-07-2018 à 22:55:35

---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.

Tapco

j'ai essayé de faire des reset de mes $i, $j. quand j'arrive au max d'une colonne, je le remet à 0 puis je fait la colonne +1

je pense que la solution serait de faire une fonction récursif mais je n'ai pas encore trouvé le bon code pour ne pas perdre du temps à calculer les doublons...

---------------
Henriot Steven

rufo

Pas me confondre avec Lycos!

Aide pour ne pas générer les doublons : matrice triangulaire supérieure...

---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta

MaybeEijOrNot

but someone at least

Pour mon exemple :

Code :

for($i=0; $i<4; $i++) {
for($j=0; $j<4; $j++) {
for($k=$i; $k<4; $k++) {
$combinaison = $i.'-'.$j.'-'.$k;
}
}
}

Attention, cela se passe différemment entre un tirage impair et un tirage pair.
Si le nombre de tirages est variable il faut en effet passer par une fonction récursive car tu ne peux pas utiliser des boucles puisqu'elles doivent être écrites à l'avance.
Je te conseille de te faire des exemples comme le mien mais avec 4 tirages et avec 5 tirages pour bien comprendre. Ensuite il faudra transposer en fonction récursive.

Niveau 1 : boucles imbriquées
Niveau 2 : fonction récursive
Niveau 3 : fonction mathématique (pour descendre la complexité de l'algo mais cela dépend de ce que tu veux réellement faire au final)

Message édité par MaybeEijOrNot le 10-07-2018 à 12:03:12

---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.

art_dupond

je suis neuneu... oui oui !!

j'aurais fait

Code :

$i=0
$j=$i
$k=$j

Avec

Code :

$i=0
$j=0
$k=$i

ça donne :

$i=0,$j=0,$k=0->3

Code :

0 0 0
0 0 1
0 0 2
0 0 3

$i=0,$j=1,$k=0->3

Code :

0 1 0
...

Message cité 1 fois

---------------
oui oui

Tapco

Code :

$z = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q'];
$boucle = count($z) - 1;
$i = $j = $k = $t = 0;
for ($i = 0; $i <= $boucle; $i++) {
for ($j = $i; $j <= $boucle; $j++) {
for ($k = $j; $k <= $boucle; $k++) {
for ($l = $k; $l <= $boucle; $l++) {
echo $z[$i].'-'.$z[$j].'-'.$z[$k].'-'.$z[$l].' ';
$t ++;
}
}
}
}
echo '<hr>Total = ' . $t;

J'ai trouvé grâce à vos réponses !!!
Enfin déjà en code pas très propre...

Maintenant, il faut que je trouve comment faire ça avec une fonction récursive pour que ce soit valable pour n case.

Message cité 1 fois

---------------
Henriot Steven

MaybeEijOrNot

but someone at least

art_dupond a écrit :

j'aurais fait

Code :

$i=0
$j=$i
$k=$j

Avec

Code :

$i=0
$j=0
$k=$i

ça donne :

$i=0,$j=0,$k=0->3

Code :

0 0 0
0 0 1
0 0 2
0 0 3

$i=0,$j=1,$k=0->3

Code :

0 1 0
...

Non.

J'ai écrit toutes les possibilités plus haut. En tenant compte de l'ordre, on est, dans mon exemple, à 64 combinaisons.
Grâce à la coloration des combinaisons, nous pouvons compter simplement les combinaisons uniques quand on ne prend pas en compte l'ordre soit 6x4 (en rouge) + 4x4 (en noir) = 24 + 16 = 40 combinaisons uniques.

Si on fait ce que je proposais, on obtient les 40 combinaisons suivantes :

Code :

0-0-0
0-0-1
0-0-2
0-0-3
0-1-0
0-1-1
0-1-2
0-1-3
0-2-0
0-2-1
0-2-2
0-2-3
0-3-0
0-3-1
0-3-2
0-3-3
1-0-1
1-0-2
1-0-3
1-1-1
1-1-2
1-1-3
1-2-1
1-2-2
1-2-3
1-3-1
1-3-2
1-3-3
2-0-2
2-0-3
2-1-2
2-1-3
2-2-2
2-2-3
2-3-2
2-3-3
3-0-3
3-1-3
3-2-3
3-3-3

Maintenant si on fait ce que tu proposes on obtient 20 combinaisons :

Code :

0-0-0
0-0-1
0-0-2
0-0-3
0-1-1
0-1-2
0-1-3
0-2-2
0-2-3
0-3-3
1-1-1
1-1-2
1-1-3
1-2-2
1-2-3
1-3-3
2-2-2
2-2-3
2-3-3
3-3-3

La combinaison 0-1-0 n'est pas générée par exemple, donc ça ne fonctionne pas.

---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.

MaybeEijOrNot

but someone at least

Tapco a écrit :

Code :

$z = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q'];
$boucle = count($z) - 1;
$i = $j = $k = $t = 0;
for ($i = 0; $i <= $boucle; $i++) {
for ($j = $i; $j <= $boucle; $j++) {
for ($k = $j; $k <= $boucle; $k++) {
for ($l = $k; $l <= $boucle; $l++) {
echo $z[$i].'-'.$z[$j].'-'.$z[$k].'-'.$z[$l].' ';
$t ++;
}
}
}
}
echo '<hr>Total = ' . $t;

Comme tu es parti sur ce que proposais art_dupond, je doute que ça fonctionne...

---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.

Tapco

Code :

$z = [0, 1, 2, 3];
$boucle = count($z) - 1;
$i = $j = $k = $t = 0;
for ($i = 0; $i <= $boucle; $i++) {
for ($j = $i; $j <= $boucle; $j++) {
for ($k = $j; $k <= $boucle; $k++) {
echo $z[$i].'-'.$z[$j].'-'.$z[$k].' ';
$t ++;
}
}
}

Résultat :

Code :

0-0-0
0-0-1
0-0-2
0-0-3
0-1-1
0-1-2
0-1-3
0-2-2
0-2-3
0-3-3
1-1-1
1-1-2
1-1-3
1-2-2
1-2-3
1-3-3
2-2-2
2-2-3
2-3-3
3-3-3
Total = 20

ça fonctionne bien

---------------
Henriot Steven

MaybeEijOrNot

but someone at least

Ok, c'est moi qui n'est pas compris le problème. [:prozac]

J'étais parti, je ne sais pas pourquoi, sur pas d'ordre gauche/droite et droite/gauche, donc en effet ça fonctionne en réduisant le nombre d'itération sur chaque boucle imbriquée. Et là ça simplifie grandement ton problème.

Message cité 1 fois

---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.

Tapco

MaybeEijOrNot a écrit :

plus qu'à adapter ça pour n case. Pour l'instant, toujours pas trouvé

---------------
Henriot Steven

art_dupond

je suis neuneu... oui oui !!

Tu peux faire un truc comme ça.

Code :

$N = 4; # taille du set de données
$C = 4; # nombre de colonnes
echo 'Dataset size: '.$N.' ';
echo 'Columns: '.$C.' ';
echo '<hr />';
# on initialise un tableau de résultat de dimension C : 0 0 0 ...
$curr = array_fill(0,$C,0);
# on se place sur la dernière valeur du tableau
$rank = $C - 1;
while (true) {
$new_rank = false;
# On affichage le résultat
foreach($curr as $val) {
echo $val;
}
echo ' ';
# Si la première valeur de tableau de résultat est (N-1), alors on a fini.
if ($curr[0] == $N-1) {
break;
}
# On regarde si la valeur actuelle == (N-1)
# Si c'est le cas, on a fini d'incrémenter sur ce rang
# => il faut descendre de rang ($rank--)
#
# On "descend" de rang tant que les valeurs rencontrées sont == N-1
while ($curr[$rank] == $N-1) {
$rank--;
$new_rank = true;
}
# on incrémente la valeur au rang courrant
$curr[$rank]++;
# si on a changé de rang il faut mettre a jour tous les rangs supérieurs
# Les rangs supérieurs vont prendre la meme valeur que la valeur du rang courrant.
if ($new_rank) {
for($i=$rank+1;$i<$C;++$i) {
$curr[$i] = $curr[$rank];
}
# on remet le rang à droite pour recommencer à incrémenter à droite
$rank = $C - 1;
}
}

L'idée c'est de créer un tableau de résultat et d'incrémenter les valeurs pour générer toutes les combinaisons.

Pour l'exemple à N=4 valeurs possibles et C=3 colonnes,
on va initialiser un tableau de resultats : 000

On va incrémenter la valeur la plus à droite jusqu'à atteindre la valeur MAX:
000
001
002
003

Quand celle-ci est atteinte, on incrémente la valeur du rang inférieur:
013

et on réinitialise toutes les valeurs "à droite" avec cette nouvelle valeur:
011

De nouveau, on incrémente jusqu'à atteindre la valeur MAX:
011
012
013

Lorsqu'on doit descendre de rang, on le fait jusqu'à trouver une valeur != MAX

Donc, si la valeur courante est 033, ça donne

1. Mise à jour du rang le plus à droite dont la valeur < MAX
133

2. Réinitialisation des valeurs à droite de cette valeur
111

3. On recommence à incrémenter à droite.

Message édité par art_dupond le 11-07-2018 à 11:20:24

---------------
oui oui

Tapco

C'est super, merci à tous. Ça fonctionne comme je veux.

J'ai plus qu'à adapter à mon code.

---------------
Henriot Steven

Publicité

FORUM HardWare.fr

Programmation

PHP

Code pour "tirage avec remise sans ordre"

Sujets relatifs
forcer un code CSS sur une page web	Création base de données avec Entity code first
[Perl] Optimisation code perl CGI - Problème de performance	Code jeux du nombre aléatoire en python 3.6
Bouton skype (code javascript) pas reconnu dans html du site Jimdo	Modification de code sur fichier .xspf de VLC 3.0
(HELP ! ) Tri par ordre Alphabétique AJAX (Help ! )	Générer code d'activation
Bidouille de code pour actualiser un utilitaire d'un jeu (titan quest)	Remplacer du code sur toutes les pages du site
Plus de sujets relatifs à : Code pour "tirage avec remise sans ordre"

Page générée en 0.136 secondes