[Résolu] [Java] Algorithme de séparation de billes dans des groupes

[Deejayfool]

Bonjour à tous!

 

J'ai un petit problème pour une application en Java. Je dois séparer 24 billes de 4 couleurs différentes (6 billes par couleur) en groupe de 3 billes tout en étant sûr de ne pas avoir deux billes de même couleur.

 

J'ai réussi à faire ce début de code mais malheureusement cela ne permet pas d'être certain d'avoir que des billes de la même couleur pour les deux derniers groupes de 3 (par exemple, les 6 premiers groupes font "Blanc", "Bleu", "Vert" et donc les deux derniers groupes n'auront plus que des "Noir", "Noir", "Noir").

 

Ici "listeBille" est une liste qui contient les 24 billes.

 

Bille[] tabBille = null;
boolean trouve;
int valAleatoire;
Couleur couleur;

for (int i = 0; i < 8; i++)  //Il y aura 8 groupes de 3 billes
{
   //On ajoute 3 billes dans notre nouveau tableau
   tabBille = new Bille[3];
   for (int j = 0; j < 3; j++)
   {
       trouve = false;

       //On récupère une bille au hasard parmi la liste
       while (!trouve)
       {
           trouve = true;
           valAleatoire = (int)(Math.random() * listeBille.size());
           couleur = listeBille.get(valAleatoire).getCouleur();

           //On vérifie qu'une bille de la même couleur n'existe pas déjà dans le tableau
           for (int k = 0; k < tabBille.length; k++)
           {
               //Si c'est la même couleur, alors il faut qu'on cherche une autre bille
               if (tabBille[k] != null && tabBille[k].getCouleur().compareTo(couleur) == 0)
               {
                   trouve = false;
                   break;
               }
           }
       }
       tabBille[j] = listeBille.get(valAleatoire);
       listeBille.remove(valAleatoire);
   }

   [...] Code permettant de traiter le tableau de billes [...]
}

 

Si quelqu'un saurait m'aiguiller pour ce problème ou connaitrait un algorithme qui permet de s'assurer que ce genre de cas n'arrive jamais, je lui en serai très reconnaissant .

Modifié le 31 mars 2011 par Deejayfool

[Dylav]

Bonsoir Deejayfool,

 

J'ai une solution triviale à te proposer. Soient A, B, C et D les quatre couleurs. Tu formes 4 groupes par rotations successives (A-B-C, D-A-B, C-D-A, B-C-D), puis tu fais la même chose une seconde fois…

 

Ça doit se programmer facilement ?

 

@+

Dylav

[Deejayfool]

Merci beaucoup pour ta réponse Dylav!

 

Malheureusement, si je fais cela, je retomberai toujours sur les 8 mêmes groupes en lançant l'algorithme. Il y a une chose que j'ai oublié d'expliquer et je m'en excuse, c'est qu'à chaque fois que je fais appel à cette boucle "for", je ne dois pas obtenir forcément les mêmes groupes de billes .

[Dylav]

Bonjour Deejayfool,

 

Je comprends ce que tu dis, mais tu ne dois pas en être malheureux, car en fait il n'existe qu'une seule solution, ces huit groupes-là ! La seule variante éventuelle serait de les voir apparaître dans un ordre différent…

 

Sauf à dire que la bille rouge n°3 dans la liste ne doit pas être « confondue » avec la bille rouge n°9, et que l'utilisation dans un groupe de l'une plutôt que l'autre rend le groupe différent ? Mais je n'ai pas vraiment perçu cela dans l'énoncé de ton problème.

 

De toute manière, pour rendre la démarche « aléatoire », tu peux procéder ainsi,

1. constitution du 1er groupe,
   • recherche aléatoire d'une bille de couleur A non encore utilisée (par une succession de tirages aléatoires dans la table jusqu'à obtenir une bille disponible de la bonne couleur),
     
   • marquage « bille utilisée » dans la liste (elle ne pourra plus resservir),
     
   • recherche aléatoire d'une bille de couleur B non encore utilisée, marquage,
     
   • recherche aléatoire d'une bille de couleur C non encore utilisée, marquage,

[*] constitution du 2nd groupe (même chose avec les couleurs D-A-B, c'est-à-dire en repartant de la première couleur non utilisée par le groupe précédent, et en recommençant au début de la table lorsqu'on en a atteint la fin),

[*] constitution du 3ème groupe (idem avec C-D-A),

[*] etc jusqu'au 7ème groupe,

[*] les trois dernières billes (non marquées utilisées) seront forcément de couleurs différentes (B-C-D), tu pourras le vérifier, et formeront donc le huitième groupe.

La démarche exposée linéairement ci-dessus peut bien entendu être exprimée sous la forme d'une boucle de traitement à parcourir sept fois (les groupes), et contenant elle-même une boucle à parcourir trois fois (les trois couleurs du groupe). La seule petite « difficulté » réside dans la façon de construire automatiquement la triplette de couleurs de chaque groupe.

 

@+

Dylav

[Deejayfool]

Effectivement, je ne m'étais pas rendu que c'était les seules possibilités .

 

Merci beaucoup pour ton aide Dylav!!