Discussion :

[reveur3]

Bonjour,

je voudrais trouver un algorithme de répartition qui prendrait 2 paramètres en entrée :

- le nombre d'objets à répartir
- le nombre de "personnes" (par exemple) entre lesquelles répartir ces objets.

Cette algorithme renverrait en sortie un tableau à 2 dimensions avec toutes les répartitions possibles.

Exemple
Répartir 2 objets parmi 3 personnes (a,b,c) donnerait :

a b c
2 0 0
1 1 0
1 0 1
0 2 0
0 1 1
0 0 2


Merci de votre aide,

[vincent69]

Soit np le nbr de personnes et no le nbr d'objet

Tu commences pas initialiser un tableau r =( no, 0, ... , 0) de taille np.
et i = 1

tant que r[np]<no faire

à toi de chercher un peu ce qu'il faut mettre ici, qques pistes :
r[i] = r[i] -1
r[i+1] = no - r[1] - ... - r[i]
i=i+1
(il manque des tests, il va falloir à un moment decrementer i...)
A la fin de chaque itération tu as une nouvelle repartition.

fin tant que

[reveur3]

Merci Vincent.

Quelqu'un aurait-il une autre piste ? ou un lien vers un site intéressant ?

[pseudocode]

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
void recurse(int[] tab, int index, int value) {
	if (index==tab.length-1) {
		tab[index]=value;
		System.out.println(Arrays.toString(tab));
		return;
	}
 
	for(int v=0;v<=value;v++) {
		tab[index]=v;
		recurse(tab, index+1, value-v);
	}
}
 
int NbObjet=2, NbPerson=3;
recurse(new int[NbPerson], 0, NbObjet);

[reveur3]

Merci beaucoup pseudocode.

Je sais pas si tu avais cet algo dans tes cartons ou si tu l'as pondu comme ça, mais chapeau en tout cas !

Je vais me servir de ce bout de code et essayer d'en faire une fonction qui renvoie un tableau à 2 dimensions, en C.

[pseudocode]

Merci beaucoup pseudocode.

Je sais pas si tu avais cet algo dans tes cartons ou si tu l'as pondu comme ça, mais chapeau en tout cas !

Je vais me servir de ce bout de code et essayer d'en faire une fonction qui renvoie un tableau à 2 dimensions, en C.

J'ai juste écrit en récursif une imbrication de boucle for().

Pour 4 personnes (a,b,c,d) et 2 objets, l'imbrication serait:

Code java :

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

1
2
3
4
5
6
7
8
for(int a=0;a<=2;a++) {
	for(int b=0;b<=2-a;b++) {
		for(int c=0;c<=2-a-b;c++) {
			int d=2-a-b-c;
			System.out.println(a+","+b+","+c+","+d);
		}
	}
}

[reveur3]

Par curiosité, tu travailles dans quoi ?
Je suis étudiant à Montpellier.

[pseudocode]

Par curiosité, tu travailles dans quoi ?
Je suis étudiant à Montpellier.

dans un bureau.

[vincent69]

mon algo proposé permettait de le faire en itératif... j'aime pas trop le récursif
Mais bon c'est sur fallait un peu se creuser le tête pour le comprendre et le finaliser...

[reveur3]

mon algo proposé permettait de le faire en itératif... j'aime pas trop le récursif
Mais bon c'est sur fallait un peu se creuser le tête pour le comprendre et le finaliser...

Merci pour ta remarque.

Je veux pas être méchant mais de quel algo tu parles ?

Si tu réfléchissais un peu, tu verrais qu'un algo itératif fixe le nombre de personne, alors que j'ai besoin qu'il soit variable.

[vincent69]

ça peut être itératif sans pour autant fixer le nombre de personne... me semble pas avoir fixer np...

Si tu réfléchissais un peu, tu verrais qu'un algo itératif fixe le nombre de personne, alors que j'ai besoin qu'il soit variable.

Avant de donner ce genre de conseil, commences par l'appliquer !

[Trap D]

Ca peut se faire facilement avec des contraintes en Prolog :

Code :

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

1
2
3
4
5
6
7
8
9
:- use_module(library(clpfd)).
 
repartition(Np, No) :-
	length(L, Np),
	L ins 0..No,
	sum(L, #=, No),
	label(L),
	writeln(L),
	fail.

Le résultat :

2 ?- repartition(3, 2).
[0, 0, 2]
[0, 1, 1]
[0, 2, 0]
[1, 0, 1]
[1, 1, 0]
[2, 0, 0]
false.

[reveur3]

Merci pour ta réponse Trap D

Je ne comprends pas une ligne à la solution que tu proposes, mais au moins tu as la mérite de m'avoir appris l'existence de prolog. Malheureusement, je n'ai pas le choix du langage de programmation à utiliser, le C m'est imposé.

[Trap D]

mais au moins tu as la mérite de m'avoir appris l'existence de prolog.

quoi !!!!

[pseudocode]

quoi !!!!