Discussion :

[Onimaru]

Salut à tous :

Soit F la fonction définie récursivement comme suit :

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

avec :
D un entier positif non nul.
I un entier dans [1, D].
J un entier dans [1, C(I, D)].
K un entier dans [1, I].

Je souhaite avoir une fonction F' égale à F mais qui soit moins couteuse en temps d'exécution.

[prgasp77]

Il n'est pas évident de deviner quelle forme possède F. Peut être pourrais tu nous indiquer sur sa fonction ou encore mieux, nous dire de quel problème / équation elle est solution.

Cdlt,

[Onimaru]

Voici des exemples des valeurs possibles de F pour d dans[1, 7] (dans l'ordre), étant donné que I, J et K dépendent de D :









Chaque case de chaque tableau = F(D, I, J, K).

Dans les tableaux il existe des colonnes qui ont la même couleur, je les appelle des bandes. Chaque bande représente les valeurs dépendantes de I.

Chaque bande d'ordre I contient I colonnes qui représentent les valeurs dépendantes de J.

Dans chaque colonne il y a exactement C(I, D) lignes qui représentent les valeurs dépendantes de K.

Le principe est le suivant : dans chaque bande on essaye de faire sortir les combinaisons possibles des éléments de l'ensemble [1, D] en respectant cette restriction : la valeur d'une case est strictement inférieure à la valeur de la même case dans la colonne qui la suit directement à droite.

Ce problème je l'ai imaginé moi même pour m'exercer mais il s'est avéré un peu dur

[pseudocode]

F(D, I, J, K) est le K-ième élément de J-ème combinaison C(I,D)

(les éléments et combinaisons étant dans l'ordre lexicographique)

[Onimaru]

F(D, I, J, K) est le K-ième élément de J-ème combinaison C(I,D)

(les éléments et combinaisons étant dans l'ordre lexicographique)

C'est ça , tu l'as dit d'une manière si simple

moi je l'ai dit de la façon dont j'ai imaginé le problème pour la première fois

[pseudocode]

C'est ça , tu l'as dit d'une manière si simple

moi je l'ai dit de la façon dont j'ai imaginé le problème pour la première fois

Ca peut se calculer assez rapidement en remarquant que le nombre d'occurrences d'un élément (dans une colonne) correspondent a une combinaison.

Par exemple, pour la bande "4" du tableau D=6 on observe qu'on a

10 combinaisons commencant par un "1" = C(3,5)
4 combinaisons commencant par un "2" = C(3,4)
1 combinaison commencant par un "3" = C(3,3)

Pour les 10 combinaisons commencant par un "1", les éléments suivants sont
6 combinaisons commencant par un "2" = C(2,4)
3 combinaisons commencant par un "3" = C(2,3)
1 combinaisons commencant par un "4" = C(2,2)

...

[Onimaru]

Ca peut se calculer assez rapidement en remarquant que le nombre d'occurrences d'un élément (dans une colonne) correspondent a une combinaison.

Par exemple, pour la bande "4" du tableau D=6 on observe qu'on a

10 combinaisons commencant par un "1" = C(3,5)
4 combinaisons commencant par un "2" = C(3,4)
1 combinaison commencant par un "3" = C(3,3)

Pour les 10 combinaisons commencant par un "1", les éléments suivants sont
6 combinaisons commencant par un "2" = C(2,4)
3 combinaisons commencant par un "3" = C(2,3)
1 combinaisons commencant par un "4" = C(2,2)

...

Oui je vois ça mais comment l'exploiter dans mon cas ?

[prgasp77]

Des constats suivants :

1. 
2. 
3. 
4. 
5. 

J'en suis arrivé à l'implémentation matlab suivante :

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
21
22
23
24
25
26
function result = f(d,i,j,k)
    if i > d | j > nchoosek(d,i) | k > i,
        error('f:args:nonvalide','Un des paramètres de f est non valide. RTFM !');
    end;    
    if d==1,
        result = 1;
        return;
    end;    
    if j==1,
        result = k;
        return;
    end;    
    if i==1,
        result = j;
        return;
    end;    
    delta = nchoosek(d-1,i-1);
    if j > delta,
        result = f(d-1,i,j-delta,k)+1;
        return;
    end;    
    if k == 1,
        result = 1;
        return;
    end;
    result = f(d-1,i-1,j,k-1)+1;

Cdlt,

[pseudocode]

Oui je vois ça mais comment l'exploiter dans mon cas ?

Cette propriété permet de calculer F(D, I, J, K) à partir de F(D, I, J, K-1). Ca reste une méthode de calcul récursive, mais c'est moins couteux que la formulation originelle si on veut directement connaitre la valeur d'un élément.

[Onimaru]

Cette propriété permet de calculer F(D, I, J, K) à partir de F(D, I, J, K-1). Ca reste une méthode de calcul récursive, mais c'est moins couteux que la formulation originelle si on veut directement connaitre la valeur d'un élément.

Pouvez vous m'expliquer comment est elle moins couteuse que la définition originale?

[Onimaru]

Des constats suivants :

1. 
2. 
3. 
4. 
5. 

J'en suis arrivé à l'implémentation matlab suivante :

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
21
22
23
24
25
26
function result = f(d,i,j,k)
    if i > d | j > nchoosek(d,i) | k > i,
        error('f:args:nonvalide','Un des paramètres de f est non valide. RTFM !');
    end;    
    if d==1,
        result = 1;
        return;
    end;    
    if j==1,
        result = k;
        return;
    end;    
    if i==1,
        result = j;
        return;
    end;    
    delta = nchoosek(d-1,i-1);
    if j > delta,
        result = f(d-1,i,j-delta,k)+1;
        return;
    end;    
    if k == 1,
        result = 1;
        return;
    end;
    result = f(d-1,i-1,j,k-1)+1;

Cdlt,

Merci, je vais l'essayer pour voir
Moi aussi j'ai pensé à agrandir le saut des 'J' :
-moi je regarde toujours la ligne précédente.
-toi tu as sauté beaucoup de lignes.

[Onimaru]

Effectivement l'algorithme de prgasp77 marche et est visiblement plus rapide :

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
 
function F(D, I, J, K : integer) : integer;
var Delta : integer;
begin
 if D = 1 then
  Result := 1
 else
  if J = 1 then
   Result := K
  else
   if I = 1 then
    Result := J
   else
    begin
     Delta := nCk(D - 1, I - 1);
     if J > Delta then
      Result := F(D - 1, I, J - Delta, K) + 1
     else
      if K = 1 then
       Result := 1
      else
       Result := F(D - 1, I - 1, J, K - 1) + 1
    end
end;

Est ce qu'on peut le réduire d'avantage ????

[pseudocode]

Pouvez vous m'expliquer comment est elle moins couteuse que la définition originale?

Et bien parce qu'on fait varier seulement "k".

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
int D=7, I=4, J=29;
 
long element=0, row=J;
for(int K=0;K<I;K++) {
 
	// jump to given row
	long pos = 0, startOfSeq=0;
	while(pos<row) {
		startOfSeq=pos;
		element++;
		pos+=nCk(D-element,I-K-1);
	}
 
	// print K-th element
	System.out.print(element+" ");
 
	// next sub-row 
	row=row-startOfSeq;
}

[prgasp77]

Est ce qu'on peut le réduire d'avantage ????

Oui mais j'ai la flemme ^^ L'idée c'est de remarquer que dans la plupart des cas, la remarque de pseudocode permet de déterminer f(d,i,j,k) directement. Sinon cela vaut f(d-1,i-1,j-delta,k)+1 qui est dans le cas précédent.

Deux choses restent à déterminer :

1. Le discriminant
2. La valeur de f() dans le cas favorable

Edit, le discriminant est évident, c'est :


Edit second, si je ne dis pas de bêtise, alors f(d,i,j,k) vaut

[prgasp77]

Mais au final, ça fait beaucoup de combinaisons à calculer, la version récursive proposée avant est sûrement meilleure. À vérifier.

[Onimaru]

Oui mais j'ai la flemme ^^ L'idée c'est de remarquer que dans la plupart des cas, la remarque de pseudocode permet de déterminer f(d,i,j,k) directement. Sinon cela vaut f(d-1,i-1,j-delta,k)+1 qui est dans le cas précédent.

Deux choses restent à déterminer :

1. Le discriminant
2. La valeur de f() dans le cas favorable

Edit, le discriminant est évident, c'est :


Edit second, si je ne dis pas de bêtise, alors f(d,i,j,k) vaut

Merci pour la solution, mais il y des choses que je ne comprends pas :
1) Le discriminant : c'est quoi la définition du discriminant dans ce cas ???
2) La fonction argmax c'est quoi ???

Je ne connais pas ces notions ou peut être je les connais sous une autre appellation.

Merci encore

[Onimaru]

Et bien parce qu'on fait varier seulement "k".

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
int D=7, I=4, J=29;
 
long element=0, row=J;
for(int K=0;K<I;K++) {
 
	// jump to given row
	long pos = 0, startOfSeq=0;
	while(pos<row) {
		startOfSeq=pos;
		element++;
		pos+=nCk(D-element,I-K-1);
	}
 
	// print K-th element
	System.out.print(element+" ");
 
	// next sub-row 
	row=row-startOfSeq;
}

Merci, je vais l'essayer pour voir.

[Onimaru]

J'ai essayé de réduire le nombre de conditions (si on appelle ça une réduction) et ça marche :


Je crois quand même que ça peut ralentir la fonction car j'ai enlevé des cas de base pour la récursivité.

Code Delphi :

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

1
2
3
4
5
6
7
8
9
10
11
 
function F(D, I, J, K : integer) : integer;
begin
 if J > nCk(D - 1, I - 1) then
  Result := F(D - 1, I, J - nCk(D - 1, I - 1), K) + 1
 else
  if K = 1 then
   Result := 1
  else
   Result := F(D - 1, I - 1, J, K - 1) + 1
end;

[prgasp77]

Dans mon message précédent, j'ai été un peu rapide. J'aimerais me rectifier. Je voulais dire qu'on différencie, en plus des cas triviaux les deux cas générés par le test


Si cette inégalité est vérifiée, alors

Sinon


Ces conjectures sont établies à partir des constats suivants (faits par pseudocode) :
À d et i fixé, si on établie la relation f(d,i,j,k) en fonction de j et k, on s'aperçoit que pour une pseudo-moitié du tableau les valeurs sont facilement prédictibles. Exemple pour d=5 et i=3

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
d=5, i=3
      k
j | 1 2 3
--+------
1 | 1 2 3
2 | 1 2 4
3 | 1 2 5
4 | 1 3
5 | 1 3
6 | 1 4
7 | 2
8 | 2
9 | 2
10| 3

Pour la colonne k=1, il y a C_2^4=6 '1', puis C_3^1=3 '2', et enfin C_2^0=1 '3'. Généralisions, dans la colonne k il y a C_{d-k}^{i-1} 'k', puis C_{d-k-1}^{i-1-1} 'k+1' ... jusqu'à ce que l'indice ou l'exposant du C soit nul.

Ainsi, si j est inférieur ou égal à la somme des C_{d-k-n+1}^{i-n}, alors f() est prédictible par cette méthode et vaut la somme de k-1 et du nombre maximum de "sauts de valeur" que l'on peut faire en restant inférieur ou égal à j.

Exemple, pour f(5,3,5,2), on vérifie notre condition de validité :
j=5 <= C_{d-k+1}^{i-k+1} = C_4^2 = 6
Combien faut-il de "sauts de valeur" pour dépasser j ?
on a C_{d-k-1+1}^{i-1} = C_3^2 = 3 '2', on continue car 3 <= j
suivi de C_{d-k-2+1}^{i-2} = C_2^1 = 2 '3', on continue car 3+2=5 <= j
suivi de C_{d-k-3+1}^{i-3} = C_1^0 = 1 '4', on stoppe car 3+2+1=6 > j
On a donc pu faire 2 "sauts de valeur", on a donc f(5,3,5,2) = 2-1 + 2=3




Mais cette méthode est très couteuse en calcul étant donné qu'il faut calculer beaucoup de combinaisons (il est possible d'établir le nombre moyen de combinaison que l'on calcul) contre c-1 combinaisons dans la version full-tail-récursive proposée ci-avant où c est la profondeur de la récursivité, qui ne dépasse pas 3 pour des "petites" valeurs de d (<=10).

Enfin, les informations que j'ai données dans ce messages n'ont pas été vraiment vérifiées. Je te conseille quelque tests

[Onimaru]

Dans mon message précédent, j'ai été un peu rapide. J'aimerais me rectifier. Je voulais dire qu'on différencie, en plus des cas triviaux les deux cas générés par le test


Si cette inégalité est vérifiée, alors

Sinon


Ces conjectures sont établies à partir des constats suivants (faits par pseudocode) :
À d et i fixé, si on établie la relation f(d,i,j,k) en fonction de j et k, on s'aperçoit que pour une pseudo-moitié du tableau les valeurs sont facilement prédictibles. Exemple pour d=5 et i=3

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
d=5, i=3
      k
j | 1 2 3
--+------
1 | 1 2 3
2 | 1 2 4
3 | 1 2 5
4 | 1 3
5 | 1 3
6 | 1 4
7 | 2
8 | 2
9 | 2
10| 3

Pour la colonne k=1, il y a C_2^4=6 '1', puis C_3^1=3 '2', et enfin C_2^0=1 '3'. Généralisions, dans la colonne k il y a C_{d-k}^{i-1} 'k', puis C_{d-k-1}^{i-1-1} 'k+1' ... jusqu'à ce que l'indice ou l'exposant du C soit nul.

Ainsi, si j est inférieur ou égal à la somme des C_{d-k-n+1}^{i-n}, alors f() est prédictible par cette méthode et vaut la somme de k-1 et du nombre maximum de "sauts de valeur" que l'on peut faire en restant inférieur ou égal à j.

Exemple, pour f(5,3,5,2), on vérifie notre condition de validité :
j=5 <= C_{d-k+1}^{i-k+1} = C_4^2 = 6
Combien faut-il de "sauts de valeur" pour dépasser j ?
on a C_{d-k-1+1}^{i-1} = C_3^2 = 3 '2', on continue car 3 <= j
suivi de C_{d-k-2+1}^{i-2} = C_2^1 = 2 '3', on continue car 3+2=5 <= j
suivi de C_{d-k-3+1}^{i-3} = C_1^0 = 1 '4', on stoppe car 3+2+1=6 > j
On a donc pu faire 2 "sauts de valeur", on a donc f(5,3,5,2) = 2-1 + 2=3




Mais cette méthode est très couteuse en calcul étant donné qu'il faut calculer beaucoup de combinaisons (il est possible d'établir le nombre moyen de combinaison que l'on calcul) contre c-1 combinaisons dans la version full-tail-récursive proposée ci-avant où c est la profondeur de la récursivité, qui ne dépasse pas 3 pour des "petites" valeurs de d (<=10).

Enfin, les informations que j'ai données dans ce messages n'ont pas été vraiment vérifiées. Je te conseille quelque tests

Finalement vous avez raison, si on essaye d'aller plus loin les choses deviennent compliquées
Merci.