Discussion :

[akrogames]

Bonjour à tous,

J'aurais besoin de vos avis et de vos recommandations. En effet, je cherche simplement à lister toutes les solutions d'un arrangement avec répétition entre n boites et k objets. Donc j'ai n^k solutions a lister.

Voici l'algorithme que j'utilise pour le moment :

Code :

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
 
DEBUT
 
Tableau boites = {-1, 1} // Je n'ai qu'une boite mais je veux modéliser des objets non rangé dans des boites donc je met -1
Tableau objets = {0, 1, 2} // J'ai 3 objets a placer ou à laisser dehors.
Tableau solution = {}
 
// INITIALISATION
Stack sboites = boites;
Stack sobjets = objets;
 
TANT QUE sobjets n'est pas vide FAIRE
     objet = Depiler sobjets;
 
     POUR i de 0 à boites.length FAIRE
          solution[objet] = boites[i];
     FIN POUR
FIN TANT QUE
 
FIN

Malheureusement cet algorithme n'est pas viable il ne liste pas toutes les solutions et je suis embourbé dans mes idées, c'est pourquoi si vous avez des documents ou des suggestions je suis preneur.

En vous remerciant par avance.

[dev_ggy]

Bonjour,

La première question que je me pose avant d'avancer avec toi. Pour un arrangement combien as-tu de tirage pour la boite 1 et la boite 2 et comment intervient dans ton tirage l'ordre entre les deux boites*? Où est la notion d'ordre de ton arrangement ? Je crois au vu de ton algorithme que tu tires une fois dans la première boite et une autre fois dans la seconde. Mais cela est-il bon ?

N'hésite pas à me reprendre si je n'ai pas bien compris ta demande.

Cordialement.

[akrogames]

Je comprends ta question, moi aussi je me suis demandé si j'avais affaire à une combinaison ou un arrangement. Je vais dérouler l'algorithme pour que tu puisses m'aider par la suite et appréhender mon problème.

Typiquement, si j'ai 1 boite A (Dont une boite fictive (-1) servant de conteneur pour les objets a l’extérieur) et trois objets (appelé 1, 2 et 3). Ce qui me fait donc 2^3 donc 8 solutions. Je déroule toutes les solutions (Chaque solution à 3 slots car 3 objets) à la main :
1er solution : [-1,-1,-1]; <= Tous les objets sont à l'extérieur et ne sont donc pas dans des boites.
2eme solution : [A,-1,-1];
3eme solution : [-1,A,-1];
4eme solution : [-1,-1,A];
5eme solution : [A,A,-1];
6eme solution : [-1,A,A];
7eme solution : [A,-1,A];
8eme solution : [A,A,A];

L'ordre ici est important pour moi, pour mon problème car c'est des boites numérotés dans mon problème sous-jacent.

Je pense que mon algorithme est juste jusqu'au début de la boucle while. Mais je ne suis pas convaincu. J'utilise des piles pour dépiler mes éléments quand je dois changer de branche sur mon arbre de recherche. Mais je me trompe peut être.

En tout cas, merci à toi de jeter un oeil sur mes difficultés.

[bretus]

Bonjour,

En fait, tu génères plusieurs combinaisons :

* 0 boites parmi 3

1er solution : [-1,-1,-1]; <= Tous les objets sont à l'extérieur et ne sont donc pas dans des boites.

<=> ensemble vide

* 1 boites parmi 3

2eme solution : [A,-1,-1];
3eme solution : [-1,A,-1];
4eme solution : [-1,-1,A];

<=> {1},{2},{3}

* 2 boites parmi 3

5eme solution : [A,A,-1];
6eme solution : [-1,A,A];
7eme solution : [A,-1,A];

<=> {1,2},{2,3},{1,3}
(avec des arrangements, tu aurais aussi {2,1},{3,2},{3,1})

* 3 boites parmi 3

8eme solution : [A,A,A];

<=> {1,2,3}

Niveau génération, je pense que tu peux procéder ainsi :
- Tu fais un tableau correspondant à tes n-boites
- Tu mets 0 quand la boites n'est pas là, 1 quand la boite est là

Tu te rends comtes que tu génères toutes les solutions considérant que ce tableau correspondant aux chiffres d'un nombre binaire qu'il suffit d'incrémenter (+1) en gérant une retenue :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
    [0,0,0] + 1 <=> ensemble vide
= [0,0,1] + 1 <=> {3}
= [0,1,0] + 1 <=> {2}
= [0,1,1] + 1 <=> {2,3}
= [1,0,0] + 1 <=> {1}
= [1,0,1] + 1 <=> {1,3}
= [1,1,0] + 1 <=> {1,2}
= [1,1,1] + 1 <=> {1,2,3}
=> dépassement d'entier => c'est fini

Niveau algorithme, c'est plutôt gentil du coup

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
bool prochaineCombinaison( tableau : int[0] ) {
    for ( int i = tableau.length - 1; i >= 0; i-- ){
        tableau[i] += 1 ;
        if ( tableau[i] > 1 ){
            // gestion de la retenue (on incrément le chiffre suivant)
            tableau[i]  = 0 ;
            continue ;
        }
        // pas de retenue
        return true ;
    }
    // impossible de gérer la retenue
    return false ;
}

L'ordre ici est important pour moi, pour mon problème car c'est des boites numérotés dans mon problème sous-jacent.

Tu peux trier la liste de solution générées ci-dessus en fonction du nombre de "1" dans chaque ligne dans un second temps.

[akrogames]

Merci a toi bretus d'avoir pris le temps de regarder.

Avant d'implémenter j'ai étudié ta proposition qui me semble étrange ou alors je n'ai pas appréhender certaines notions de ta solution. Techniquement, il n'y a pas forcément le même nombre de boites que d'objets donc la représentation de ta solution avec les boites me semble bancal. Il y a aussi le fait qu'une boite peut contenir plusieurs objets. Mais j'ai peut être pas compris ta proposition.

D'ailleurs tu titre le nom de ta fonction prochaineCombinaison, alors je ne sais pas si nous nous sommes compris entièrement.

J'ai quand même tenté d'implémenter ta solution pour voir ce que cela donne :

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
	public boolean prochaineCombi(int[] boite) {
		for (int i = boite.length-1; i >= 0 ; i--) {
			boite[i] += 1;
 
			if(boite[i] > 1) {
				boite[i] = 0;
				continue;
			}
 
			return true;
		}
 
		return false;
	}

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
while(this.prochaineCombi(boites)) {
 
}

Mais je n'arrive pas à appréhender ton algo car pour moi, tu dois avoir au moins le même nombre de boite que d'objet sinon cela pose problème. Et dans la fonction prochaineCombinaison, il y a aucune référence à mon second tableau d'objets.

Tu pourrais préciser les choses, de mon côté, il me semble nous devrions faire une fonction récursive car le nombre de boucle for de l'algorithme dépend du nombre de boites et vu que mon nombre de boite et dynamique...

En tout cas merci à toi, j'espère qu'on pourra avancer encore... Si j'avance de mon côté je posterai mes avancées.

[bretus]

Tu pourrais préciser les choses, de mon côté, il me semble nous devrions faire une fonction récursive car le nombre de boucle for de l'algorithme dépend du nombre de boites et vu que mon nombre de boite et dynamique...

Le récursif est rarement préférable au non récursif (la pile d'appel gonfle).


Avec ça, tu comprends

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
void affiche( int[] boites ){
    for ( int i = 0; i < boites.length; i++ ){
        print ( boites[i] == 0 ? "-1 " : "A " ) ;
    }
}

C'est exactement la même représentation, sauf que "-1" chez toi <=> "0" chez moi et "A" chez toi <=> "1" chez moi

Edit : Tu trouveras une démo ici en JavaScript sur JSFiddle

[iakou]

Bonjour akrogames.
Je me serais bien immiscé dans la problématique.
Hélas, je n'ai rien compris de ce que vous voulez faire ! Et apparemment les intervenants successifs guère plus...
Un problème clairement énoncé c'est la moitié du travail.
Cdlt

[Jedai]

Éclaircissement, d'après ce que je comprend de l'exemple donné :
Il y a k boites (dont probablement une boite fictive pour "en-dehors des boites" mais ça ne change rien à la solution, juste à son interprétation),
Il y a n objets à ranger dans ces boites, on peut placer n'importe quel nombre d'objet dans une même boite.

Autrement dit la question c'est de choisir parmi k boites pour chacun des n objets, il y a donc kⁿ solutions possibles.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
boites = [1..k]
nbObjets = n

Il est possible de faire de l'itératif, mais la solution récursive est bien plus naturelle :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
repartitions :: [a] -> Int -> [[a]]
repartitions boites 0        = [ [] ]
repartitions boites nbObjets = [ boiteChoisie : suite | boiteChoisie <- boites, suite <- repartitions boites (nbObjets - 1) ]

Ceci est un code Haskell mais peut facilement se traduire en python (sachant que (x : xs) est une liste dont le premier élément est x et la suite est xs) ou en tout autre langage.

A vous de voir si cela vaut la peine de traduire en itératif (quel est le nombre maximum d'objet ? Votre langage peut-il supporter cette profondeur d'appel ?) et si vous devez adaptez selon ce vous voulez faire avec ces possibilités (si vous voulez juste les afficher, dans un langage autre qu'Haskell vous allez devoir reformuler la fonction pour éviter de vous trainer la liste complète en mémoire, en Haskell ça marchera sans adaptation si vous faites "mapM_ print (repartitions ["-1","A"] 3)").

--
Jedaï

[akrogames]

Le problème a été clairement explicité, c'est de faire un arrangement avec répétition.

Voici ma solution qui fonctionne parfaitement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
box = {-1, 0}
objectCount = 3
solutions = {}
 
getPermutations(0, new array[objectCount]) // function call
 
getPermutations(index, output)
   if index == output.length
      solutions.add(output)
   else
      for each box b
         output[index] = b
         getPermutations(index + 1, output)

Exemple complet en Java :

Code java :

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
import java.util.*;
import java.lang.*;
import java.io.*;
 
 
class Akrogames
{
    static void getPermutations(int index, int[] output, ArrayList<int[]> solutions, int[] boxes)
    {
        if (index == output.length)
        {
            int[] temp = new int[output.length];
            System.arraycopy(output, 0, temp, 0, output.length);
            solutions.add(temp);
            return;
        }
        for (int b: boxes)
        {
            output[index] = b;
            getPermutations(index + 1, output, solutions, boxes);
        }
    }
 
    public static void main (String[] args) throws java.lang.Exception
    {
        ArrayList<int[]> solutions = new ArrayList<>();
        int objectCount = 3;
        getPermutations(0, new int[objectCount], solutions, new int[]{-1, 0});
        for (int[] temp: solutions)
        {
            for (int i: temp)
                System.out.print(i + " ");
            System.out.println();
        }
    }
}

Le résultat est celui que j'ai explicité plus haut :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
1er solution : [-1,-1,-1];
2eme solution : [A,-1,-1];
3eme solution : [-1,A,-1];
4eme solution : [-1,-1,A];
5eme solution : [A,A,-1];
6eme solution : [-1,A,A];
7eme solution : [A,-1,A];
8eme solution : [A,A,A];

je suis certain que cela va servir à des gens. En espérant que cela les aides.

Bonne journée.