Discussion :

[Onimaru]

Salut à tous,
Voici mon problème :
Soit l'application F : N x {1,...,d} x {1,...,dCi} x {1,...,i} -----> {1,...,d}
(d, i, j, k) -----> f(d, i, j, k)
où dCi est le nombre de combinaisons de i parmi d.
Les variables i, j et k dépendent de d.

Pour ses valeurs je vais donner des exemples :

pour d = 1 :
f(1, 1, 1, 1) = 1

pour d = 2 :
f(2, 1, 1, 1) = 1
f(2, 1, 2, 1) = 2
f(2, 2, 1, 1) = 1
f(2, 2, 1, 2) = 2

pour d = 3 :
f(3, 1, 1, 1) = 1
f(3, 1, 2, 1) = 2
f(3, 1, 3, 1) = 3
f(3, 2, 1, 1) = 1
f(3, 2, 1, 2) = 2
f(3, 2, 2, 1) = 1
f(3, 2, 2, 2) = 3
f(3, 2, 3, 1) = 2
f(3, 2, 3, 2) = 3
f(3, 3, 1, 1) = 1
f(3, 3, 1, 2) = 2
f(3, 3, 1, 3) = 3

et ainsi de suite.

J'ai écrit une fonction récursive (Delphi) qui la calcule mais il y a eu problème :

Code delphi :

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
function F(D, I, J, K : integer) : integer;
var Cpt, S, R : integer;
begin
 if J = 1 then
  Result := K
 else
  begin
   S := 0;
   R := 1;
   for Cpt := I downto K do
    begin
     S := F(D, I, J - 1, Cpt) + R;
     if S = D + Cpt - I + 1 then
      begin
       S := D + Cpt - I;
       R := 1
      end
     else
      R := 0;
     if F(D, I, J - 1, Cpt) = D + Cpt - I then
      S := Cpt + 1 // ici le problème 
    end;
   Result := S
  end;
end;

Toute aide sera la bienvenue.

Merci

[pseudocode]

Je reprend ce que j'ai compris

soit la fonction

F(d, i, j, k)

définie pour

d un entier (non nul)
i un entier dans [1,d]
j un entier dans [1,C(i,d)]
k un entier dans [1,i]

telle que

F(d, i, j, k) = ????

Que doit renvoyer cette fonction dans le cas où elle est définie ?

[Onimaru]

Comme j'ai dit les variables i, j et k dépendent exactement de d, il y a exactement d*2^(d-1) valeurs possibles pour F :

Le principe est :

les blocs varient selon i
-i=1--------------------
|1| j=1 les lignes varient selon j
|2| j=2
|3| j=3
|4| j=4
-i=2--------------------
|1|2| j=1
|1|3| j=2
|1|4| .
|2|3| .
|2|4| .
|3|4|
-i=3--------------------
|1|2|3|
|1|2|4|
|1|3|4|
|2|3|4|
-i=4--------------------
|1|2|3|4|
------------------------
et les colonnes varient selon k

On essaye dans chaque bloc de faire toutes les combinaisons possibles des entiers de [1..d] en prenant pour le bloc i, i éléments.

F renvoie les valeurs entre ||.

[pseudocode]

Non, décidément je ne comprend pas.

C'est quoi la finalité de cette fonction F() ? Calculer le nombre de ... quoi ?

[plegat]

Non, décidément je ne comprend pas.

Pas mieux...

[Onimaru]

Salut,
J'ai dessiné ces images pour bien comprendre :

chaque tableau est dépendant de d (d=1, d=2, ...)

Les colonnes qui ont une couleur unie (bloc) représentent les valeurs d i
les lignes représentent les j
les colonnes de chaque bloc représentent les k









L'application que je veux donne le contenu de chaque case dans le tableau.

Et comme ce travail est fastidieux le mieux serait de le faire avec trois boucles (i, j et k ; d étant un paramètre) et non à la main (comme ces tableaux).

Je crois que si vous regardez attentivement les tableaux vous pouvez deviner
facilement le tableau pour d=9 et d=10 et ....

Merci.

[plegat]

Salut,
J'ai dessiné ces images pour bien comprendre :

ça a dû bugguer quelque part, on n'a pas les images...

[Onimaru]

ça a dû bugguer quelque part, on n'a pas les images...

Salut, je crois que le problème et réglé.

[Nebulix]

Si tu as pu faire un tableau à la main c'est que tu maitrises dejà l'algo.
Il suffit de décrire à l'ordi le cheminement de ta pensée.

[pseudocode]

Ca ressemble a une fonction qui donne le i-ième élément d'une combinaison C(n,k) des n premiers entiers

F(n,k,i) = i-ème élément de C(n,k) de {1,2,...,n}

[Onimaru]

Si tu as pu faire un tableau à la main c'est que tu maitrises dejà l'algo.
Il suffit de décrire à l'ordi le cheminement de ta pensée.

Salut,
Croyez moi si j'ai posté ce message ici c'est que je n'ai pas trouvé de solution.
En ce qui concerne à la main, je veux dire comme ça :

Code delphi :

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

1
2
3
4
5
6
7
8
9
 
with StringGrid do
  begin
    Cells[1, 1] := 1;
    Cells[1, 2] := 1;
    .
    .
    . 
  end;

Et ce n'est pas facile comme vous le savez

[Onimaru]

Ca ressemble a une fonction qui donne le i-ième élément d'une combinaison C(n,k) des n premiers entiers

F(n,k,i) = i-ème élément de C(n,k) de {1,2,...,n}

Je vois cette ressemblance mais je vois pas comment implémenter ça.

[pseudocode]

Je vois cette ressemblance mais je vois pas comment implémenter ça.

On à une contribution qui liste différents moyens d'obtenir toutes les combinaisons/permutations d'un ensemble d'élément:

http://www.developpez.net/forums/d22...n-combinaisons


Par contre, je ne crois pas qu'il y ai dedans le moyen d'avoir directement la i-ème combinaison/permutation.

[Onimaru]

On à une contribution qui liste différents moyens d'obtenir toutes les combinaisons/permutations d'un ensemble d'élément:

http://www.developpez.net/forums/d22...n-combinaisons


Par contre, je ne crois pas qu'il y ai dedans le moyen d'avoir directement la i-ème combinaison/permutation.

Merci,
Je vais vous dire ce que je pense moi :

pour d = 5, i=3
j=01 ---------> |1|2|3|
j=02 ---------> |1|2|4|

on ajoute un a la dernière position, le résultat est 4 pas de dépassement, on continue :

j=02 ---------> |1|2|4|
j=03 ---------> |1|2|5| la même chose

mais quand on arrive à j=04

j=03 ---------> |1|2|5|
j=04 ---------> |1|2|6| c'est faux, ici il y a un dépassement il y aura une retenue '1' qui passe à '2' et '6' sera '4'

j=03 ---------> |1|2|5|
j=04 ---------> |1|3|4|

Mon problème à moi est comment décider la nouvelle valeur après le dépassement.

Code Delphi :

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
 
function F(D, I, J, K : integer) : integer;
var Cpt, S, R : integer;
begin
 if J = 1 then // le cas de j=1 la première ligne toujours de la forme 1|2|3|...
  Result := K  // dans ce cas 'K'
 else
  begin
   S := 0; // la somme 
   R := 1; // la retenue initialisée à '1' car on va rechercher le suivant.
   for Cpt := I downto K do // on commence de la dernière position
    begin                          // jusqu'à la position 'K' qu'on veut sa valeur.
                                     // Cpt parcoure les colonnes de chaque bloc. 
     S := F(D, I, J - 1, Cpt) + R; // on doit toujours regarder en haut
                                           // pour décider.
     if S = D + Cpt - I + 1 then // condition pour dépassement
                                         // j'ai constaté que le maximum de chaque
                                         // position est D + Cpt - I, +1 pour 
                                         // le débordement.
      begin
       S := D + Cpt - I; // fixer S au maximum.
       R := 1 // retenue = 1
      end
     else
      R := 0; // pas de dépassement donc retenue = 0.
     if F(D, I, J - 1, Cpt) = D + Cpt - I then // ici le problème
                                                          // le cas où à l'étage précédent 
                                                          // avant l'incrémentation le 
                                                          // maximum est atteint.
      S := Cpt + 1 // il faut mettre autre chose ici.
    end;
   Result := S
  end;
end;

Il ne faut pas oublier que F donne la valeur de chaque case dans le tableau, les case sont séparées.

[pseudocode]

j=03 ---------> |1|2|5|
j=04 ---------> |1|2|6| c'est faux, ici il y a un dépassement il y aura une retenue '1' qui passe à '2' et '6' sera '4'

j=03 ---------> |1|2|5|
j=04 ---------> |1|3|4|

Mon problème à moi est comment décider la nouvelle valeur après le dépassement.

Ton ensemble doit toujours etre ordonné (strictement croissant). Donc la nouvelle valeur est le plus petit nombre qui conserve l'ordre croissant strict.

(C'est donc la valeur de la case précédente + 1)

[Onimaru]

Ton ensemble doit toujours etre ordonné (strictement croissant). Donc la nouvelle valeur est le plus petit nombre qui conserve l'ordre croissant strict.

(C'est donc la valeur de la case précédente + 1)

Pas toujours +1, regarde ici : '5' devient '4' et '1' reste '1' et '2' devient '3'

j=03 ---------> |1|2|5|
j=04 ---------> |1|3|4|

ou ici

j=06 ---------> |1|4|5|
j=07 ---------> |2|3|4|

'5' --> '4'
'4' --> '3'
'1' --> '2'

[pseudocode]

Pas toujours +1, regarde ici : '5' devient '4' et '1' reste '1' et '2' devient '3'

Par "case précédente" je veux dire celle qui est immédiatement gauche

|1|2|5|

on incrémente la dernière case

|1|2|5+1=6|

ca déborde -> on incrémente la case a gauche

|1|2+1=3|?|

on calcule la nouvelle valeur = case a gauche + 1

|1|3| 3+1=4 |

Ok, tout est bon

|1|3|4|

[Onimaru]

Par "case précédente" je veux dire celle qui est immédiatement gauche

|1|2|5|

on incrémente la dernière case

|1|2|5+1=6|

ca déborde -> on incrémente la case a gauche

|1|2+1=3|?|

on calcule la nouvelle valeur = case a gauche + 1

|1|3| 3+1=4 |

Ok, tout est bon

|1|3|4|

Oui merci, je vois maintenant, ce travail on doit le faire que si la case précédente (en haut) n'est pas au max.
par exemple :
1|2|4
1|2|5
mais pour
1|2|5
1|3|4 4 = 3 + 1
Je crois que c'est ça que je dois mettre à la place de

Code Delphi :

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

1
2
 
 S := Cpt + 1

Mais je crains un débordement, surtout que que c'est récursif.
Je vais essayer.

[Onimaru]

J'ai écrit :

Code Delphi :

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
 
function F(D, I, J, K : integer) : integer;
var Cpt, S, R : integer;
begin
 if J = 1 then
  Result := K
 else
  begin
   S := 0;
   R := 1;
   for Cpt := I downto K do
    begin
     S := F(D, I, J - 1, Cpt) + R;
     if S = D + Cpt - I + 1 then
      begin
       S := D + Cpt - I;
       R := 1
      end
     else
      R := 0;
     if (Cpt > 1) and (F(D, I, J - 1, Cpt) = D + Cpt - I) then
      S := F(D, I, J, Cpt - 1) + 1 // ici
    end;
   Result := S
  end;
end;

Et il y a eu un débordement de pile.

[pseudocode]

Le plus simple, c'est de raisonner par colonne.

|#1|#2|#3|...|#i|...|#k|


Si on veut incrémenter la colonne #i:

- cas 1 : la valeur est inférieure au maximum possible pour cette colonne. On incrémente la valeur et c'est fini.

- cas 2 : la valeur est égale au maximum possible. On essaye d'incrémenter la colonne précédente (appel récursif)

----- cas 2.a : l'incrémentation de la colonne précédente à réussie. On positionne la nouvelle valeur de la colonne actuelle (= valeur de la colonne précédente +1) et c'est fini.

----- cas 2.b : l'incrémentation de la colonne précédente a échouée. On sort avec une erreur.


Il te reste a déterminer quelle est la valeur maximum pour une colonne "i", et déterminer pour quelles raisons l'incrémentation de la colonne précédente pourrait échouer.