Bonjour,

Je dois manipuler des tables qui contiennent toutes les séquences non
décroissantes possibles. Les paramètres de ces tables sont:
.. B : taille des séquences
.. S : nombre de symboles possibles
.. N : taille finale de la table

exemple: pour B=3, S=4:
0 0 0, 0 0 1, 0 0 2, 0 0 3,
0 1 1, 0 1 2, 0 1 3,
0 2 2, 0 2 3,
0 3 3,
1 1 1, 1 1 2, 1 1 3,
1 2 2, 1 2 3,
1 3 3,
2 2 2, 2 2 3, 2 3 3,
3 3 3.
=> N = 20

J'ai trouvé comment générer la table, et comment trouver N en fonction de
(B, S); c'était pas trop dur.

Là, je cherche / je me demande s'il existe:
1/ une fonction qui donne l'index dans la table d'une sequence quelconque, et
2/ une fonction qui donne la séquence en fonction de son index dans latable.

Pour le moment, je mémorise les sequences elles-mêmes dans la table, ce qui
fait que 2/ est trival, en O(1), et 1/ est implémenté avec une dichotomie;
Le problème est que ça nécessite O(N*S) en mémoire, et la taille de la
table, comme on peut s'en douter, croit vite:
Pour (3, 256), c'est 2.829.056 d'elements;
Pour (4, 256), c'est 183.181.376; au-delà, ça tient pas dans ma RAM.

Comment faire..
Merci.

Je n'ai pas tellement le temps d'étudier ton problème de près, mais une
première lecture me fait penser àa la structure de données appelée trie
(ou l'un de ses variantes avec compression).

Je te laisse regarder si son utilisation pourrait t'être utile :
[..]

xtof pernod écrivit :
[..]
> fait que 2/ est trival, en O(1), et 1/ est implémenté avec une dichotomie;
> Le problème est que ça nécessite O(N*S) en mémoire, et la taille de la
> table, comme on peut s'en douter, croit vite:
> Pour (3, 256), c'est 2.829.056 d'elements;
> Pour (4, 256), c'est 183.181.376; au-delà, ça tient pas dans ma RAM.
>> Comment faire..
> Merci.

Si on résout 1) et 2) par une fonction, non pas algorithmique mais
analytique, on n'a plus besoin de stocker la table.

Je commencerais par modifier les séquences en remplaçant tous les
chiffres par la différence avec le précédent, en supposant un 0 à gauche.
111 -> 100, 233 -> 210, 112 -> 101, etc.
Le problème 1) est alors ramené à trouver, pour un nombre en base S,
combien de nombres inférieurs sont tels que la somme de leurs chiffres
soit inférieure ou égale à B. Je n'ai pas le temps là, mais à mon avis
ça doit se trouver, et ça doit pouvoir s'inverser pour résoudre 2).

Le Wed, 22 Jan 2014 16:47:54 +0100,
Damien Wyart <damien.wyart> a écrit :
> Je n'ai pas tellement le temps d'étudier ton problème de près, mais une
> première lecture me fait penser àa la structure de donnéesappelée trie
> (ou l'un de ses variantes avec compression).
> Je te laisse regarder si son utilisation pourrait t'être utile :
> [..]

Un trie.. J'avoue, je n'avais pas pensé à cette structure, qui sert à stocker
de manière optimale un ensemble de chaînes ayant un début commun, le
reste étant variable (si j'ai bien suivi)

Je vois pas comment l'appliquer, as-tu le temps de me préciser comment
tu voyais la chose ?

Merci en tout cas,,

Le Wed, 22 Jan 2014 16:48:28 +0100,
Michel Olagnon <molagnon> a écrit :
> xtof pernod écrivit :
> > (...)
> > Comment faire..
> Si on résout 1) et 2) par une fonction, non pas algorithmique mais
> analytique, on n'a plus besoin de stocker la table.

Impeccable, c'est bien ça qu'il me faut..

> Je commencerais par modifier les séquences en remplaçant tous les
> chiffres par la différence avec le précédent, en supposantun 0 à gauche.
> 111 -> 100, 233 -> 210, 112 -> 101, etc.

Comme du codage-delta, donc.. ok.

> Le problème 1) est alors ramené à trouver, pour un nombre en base S,
> combien de nombres inférieurs sont tels que la somme de leurs chiffres
> soit inférieure ou égale à B. Je n'ai pas le temps là, mais à mon avis
> ça doit se trouver, et ça doit pouvoir s'inverser pour résoudre 2).

Bon sang tout le monde est surbooké, aujourd'hui, dans ce groupe =)

J'avais entrevu une solution de ce genre, pour le cas (trivial) B=2, mais
je n'ai pas réussi à généraliser. Certainement s'il y une soluce, elle sera
de ce type, je pense.

Si ça peut aider, on peut fixer B à 3 ou 4(il n'ira pas tellementplus haut(?)

Donc si, quand tu as le temps bien sur, tu entrevois comment faire,
je suis preneur.

Merci encore,,

* xtof pernod <xtof.pernod> in fr.comp.algorithmes:
> Je vois pas comment l'appliquer, as-tu le temps de me préciser comment
> tu voyais la chose ?

J'ai répondu ça de façon un peu intuitive, mais effectivement, je n'ai
pas d'idée très précise sur la façon dont on pourrait profiter de cette
structure sur ton problème.

Désolé si j'ai suscité un faux espoir :)

Le Wed, 22 Jan 2014 21:13:59 +0100,
Damien Wyart <damien.wyart> a écrit :
> Désolé si j'ai suscité un faux espoir :)

Pas de soucis, mon bon monsieur.
Merci pour ta réponse,

[xtof, excuse-moi, je t'ai envoyé par erreur ma réponse par mail au lieu
d'ici...]

On 22/01/14 14:55, xtof pernod wrote:
[..]
> 2 2 2, 2 2 3, 2 3 3,
> 3 3 3.
> => N = 20

À vue d'oeil et en regardant ton exemple, si tu pars de la table (B, S),
le premier symbole est 0 pour les (B'=B-1, S'=S) (i.e. c'est 0 suivi de
toutes les séquences avec le même alphabet et plus courtes de 1). De
même, le premier symbole est 1 pour un nombre de séquences (B-1, S-1) :
0 est exclu, on garde toutes les séquences avec un symbole de moins et
une longueur plus courte de 1. En continuant dans l'alphabet, le premier
symbole est 2 pour un nombre de séquences (B-1, S-2), etc.

Ça doit pouvoir se continuer récursivement, par exemple une fois le premier
symbole fixé, le deuxième symbole est 2 (par exemple) pour (B-2, S-2)
séquences, qui commencent après les (B-2, S-1) séquences dont le deuxième
symbole est 1, elles-mêmes après les (B-2, S) séquences dont le deuxième
symbole est 0.

Ce qui doit pouvoir permettre de construire des algos... À la louche et
sans trop réfléchir :

> 1/ une fonction qui donne l'index dans la table d'une sequence quelconque, et

Si le premier symbole est k, l'index est entre :
min = (B-1, S) + (B-1, S-1) + ... + (B-1, S-k)
et (la même chose avec un terme de plus) :
max = (B-1, S) + (B-1, S-1) + ... + (B-1, S-k) + (B-1, S-k-1)

Puis tu recommences avec le 2ème symbole, qui va être dans (B-2, S) +
.... en partant correctement de l'index de départ calculé pour le 1er
symbole, i.e. si tu cherches la séquence "12.." tu commences le calcul
de la position de 2 à partir de la première position de 1 (i.e. 10 dans
ton exemple -- avec un index qui commence à 0).

Si tu continues jusqu'à la fin, ça devrait permettre de reconstruire
l'index complet.

Je ne sais pas si je suis très clair, dans ma tête ça a l'air de marcher

> 2/ une fonction qui donne la séquence en fonction de son index dans la table.

Calculer les (B-1, k) pour k=0...S (ou S-1, j'ai la flemme de réfléchir
en détail...), chaque intervalle correspond au premier symbole de la
séquence.

Puis enlever l'index du début de l'intervalle et recommencer avec des
séquences plus courtes de 1 (i.e. (B-2, k) -- peut-être avec une valeur
max de k différente ?), ce qui devrait donner le 2ème symbole, etc.

Je ne garantis pas du tout le résultat, c'est juste une idée basée
essentiellement sur ton exemple et en supposant que ça se généralise
bien, je dis peut-être des bêtises... et je te laisse vérifier et régler
tous les "détails" genre les bornes à utiliser, des +1 ou -1 qui peuvent
trainer...

[... blanc ...]

En fait j'étais en train de me relire avant d'envoyer quand je me suis
dit qu'avec mon raisonnement, c'est même encore plus simple :

Les séquences qui commencent par 0 commencent à l'index 0 dans la table.
Les séquences qui commencent par 1 commencent à l'index (B-1, S)
....
Les séquences qui commencent par n commencent à l'index "somme de k=1 à
n-1 des (B-1, S-k)"

On recommence avec B-2 pour le deuxième symbole, et on additionne.

Au final, ça doit donner, pour une séquence "n_1 n_2 n_3 ... n_p" un
index de :
index = somme de i=1 à B de ( somme de k=1 à n_i des (B-i, S-k) )

Bon, là encore, je suis à peu près sûr de m'être planté sur les index
et bornes de mes sommes, mais l'idée m'a l'air correcte. La formule
donne directement la réponse à ta question 1, pour la 2 je ne vois pas
d'autre manière que de décomposer comme ce que je décris plus haut.

xtof pernod écrivit :
[..]
> J'avais entrevu une solution de ce genre, pour le cas (trivial) B=2, mais
> je n'ai pas réussi à généraliser. Certainement s'il y une soluce, elle sera
> de ce type, je pense.
> Si ça peut aider, on peut fixer B à 3 ou 4(il n'ira pas tellement plus haut(?)
> Donc si, quand tu as le temps bien sur, tu entrevois comment faire,
> je suis preneur.

Posons Y(n,b) le nombre de nombres de n chiffres en base s (zéros à
gauche compris) tels que leur somme soit inférieure ou égale à b.
Y(n,b) = Y(n-1,b) + Y(n-1,b-1) + ... + Y(n-1,b-s+1) (avec Y(p,q) = 1 si
q=0, 0 si q<0)
Il est donc facile de construire la table Y.
Maintenant, prenons le nombre klmn... de r chiffres en base S. Pour
obtenir le nombre X(r,b,klmn...) cherché, on ajoute :
Y(r-1,b) pour traiter ceux qui commencent par 0
+ Y(r-1,b-1) pour traiter ceux qui commencent par 1
+ etc. jusqu'à k-1
+ X(r-1,b-k,lmn...) pour traiter ceux qui commencent par k

X(r-1,b-k,lmn...) se décompose pareil, et on doit donc facilement
déterminer quels termes du tableau Y il faut sommer.

En sens inverse, on procède comme pour une division, on cherche k tel
que l'indice donné soit compris entre la somme des Y(r-1,b-i) pour i
allant de 0 à k-1 et de 0 à k, on enlève la somme jusqu'à k-1, et on
cherche les chiffres suivants de la même manière.

Le Wed, 22 Jan 2014 23:13:02 +0000,
Rémi Moyen <rmoyen+news> a écrit :
> On 22/01/14 14:55, xtof pernod wrote:
> À vue d'oeil et en regardant ton exemple, si tu pars de la table (B,S),
> le premier symbole est 0 pour les (B'=B-1, S'=S) (i.e. c'est 0 suivi de
> toutes les séquences avec le même alphabet et plus courtes de 1). De
> même, le premier symbole est 1 pour un nombre de séquences (B-1, S-1) :
> 0 est exclu, on garde toutes les séquences avec un symbole de moins et
> une longueur plus courte de 1. En continuant dans l'alphabet, le premier
> symbole est 2 pour un nombre de séquences (B-1, S-2), etc.

La notation "(a, b)", c'est une sous-table ? Virtuelle / n'ayant pas besoin
d'exister en mémoire ?
Ou ça représente juste le nombre d'éléments de cette sous-table ?
(avec "élément" = "sequence non décroissante", toujours)

> Ça doit pouvoir se continuer récursivement, par exemple une fois le premier
> symbole fixé, le deuxième symbole est 2 (par exemple) pour (B-2, S-2)
> séquences, qui commencent après les (B-2, S-1) séquences dont le deuxième
> symbole est 1, elles-mêmes après les (B-2, S) séquences dont le deuxième
> symbole est 0.

L'index du premier symbole: il est calculé algorithmiquement, récursivement,
ou il doit être connu par avance (ce qui peut se faire, mais en O(N)) ?..

> Ce qui doit pouvoir permettre de construire des algos... (...)
> > 1/ une fonction qui donne l'index dans la table d'une sequence
> > quelconque, et
> Si le premier symbole est k, l'index est entre :
> min = (B-1, S) + (B-1, S-1) + ... + (B-1, S-k)
> et (la même chose avec un terme de plus) :
> max = (B-1, S) + (B-1, S-1) + ... + (B-1, S-k) + (B-1, S-k-1)

J'ai du louper une marche: je vois pas comment on calcule "(a, b)"
(désolé!)
C'est peut-être possible par récursivité, mais je ne vois pas comment
amorcer la récursion.

Par ex: B=3, S=4, toujours, et j'ai en entrée: 1 1 3 (index = 12)
Comment on procède ?..

> Puis tu recommences avec le 2ème symbole, qui va être dans (B-2, S) +
> ... en partant correctement de l'index de départ calculé pour le 1er
> symbole, i.e. si tu cherches la séquence "12.." tu commences le calcul
> de la position de 2 à partir de la première position de 1 (i.e.10 dans
> ton exemple -- avec un index qui commence à 0).
> Si tu continues jusqu'à la fin, ça devrait permettre de reconstruire
> l'index complet.
> Je ne sais pas si je suis très clair, dans ma tête ça a l'air de marcher

Si une solution existe, c'est génial. Il me reste plus qu'à
> > 2/ une fonction qui donne la séquence en fonction de son index dans la
> > table.
> Calculer les (B-1, k) pour k=0...S (ou S-1, j'ai la flemme de réfléchir
> en détail...), chaque intervalle correspond au premier symbole de la
> séquence.

Toujours le calcul de "(a, b)", à déterminer..

> Puis enlever l'index du début de l'intervalle et recommencer avec des
> séquences plus courtes de 1 (i.e. (B-2, k) -- peut-être avec une valeur
> max de k différente ?), ce qui devrait donner le 2ème symbole, etc.
> Je ne garantis pas du tout le résultat, c'est juste une idée basée
> essentiellement sur ton exemple et en supposant que ça se généralise
> bien, je dis peut-être des bêtises... et je te laisse vérifier et régler
> tous les "détails" genre les bornes à utiliser, des +1 ou -1 qui peuvent
> trainer...

Quand j'en serai là, pas de soucis =)

> [... blanc ...]
> En fait j'étais en train de me relire avant d'envoyer quand je me suis
> dit qu'avec mon raisonnement, c'est même encore plus simple :
> Les séquences qui commencent par 0 commencent à l'index 0 dans la table.
> Les séquences qui commencent par 1 commencent à l'index (B-1, S)

Calcul de "(a, b)"..
Vital, car cette solution a l'air encore plus simple.
[..]

Le 23/01/2014 15:03, xtof pernod a écrit :
> J'ai du louper une marche: je vois pas comment on calcule "(a, b)"
> (désolé!)
> C'est peut-être possible par récursivité, mais je ne vois pas comment
> amorcer la récursion.

Ne s'agirait-il pas de la notation actuelle pour ce qui s'écrivait
à mon époque C(a, b) (ou plutôt :
b
C
a
) ?

Si oui, (a, b) = a!/(b!(a-b)!)

Michel Olagnon écrivit :
[..]
> + X(r-1,b-k,lmn...) pour traiter ceux qui commencent par k
> X(r-1,b-k,lmn...) se décompose pareil, et on doit donc facilement
> déterminer quels termes du tableau Y il faut sommer.

J'ai fait un petit programme Fortran, ça a l'air de marcher. En tout
cas, il donne bien à partir de la table Y la même chose que le calcul
bestial pour le nombre de valeurs de B chiffres en base S dont la somme
des chiffres est inférieure ou égale à S. On peut donc trouver à partir
d'une séquence son index.

> En sens inverse, on procède comme pour une division, on cherche k tel
> que l'indice donné soit compris entre la somme des Y(r-1,b-i) pour i
> allant de 0 à k-1 et de 0 à k, on enlève la somme jusqu'à k-1, et on
> cherche les chiffres suivants de la même manière.

J'ai essayé "à la main", et ça marche, a priori.

Par exemple, B=5, S=10, "56689" donne 51021, qui donne l'index 1919

L'index 1919 donne 715+495+330+210+126 -> 5 termes et un reste de 43
43 pour B=4,S=10-5 donne 35 -> 1 terme et un reste de 8
8 pour B=3,S=10-5-1 donne -> 0 terme et un reste de 8
8 pour B=2,S=10-5-1 donne 4+3 -> 2 termes et un reste de 1
1 pour B=1,S=10-5-1-2 donne 1 -> 1 terme

J'ai bien reconstruit 51021, et donc "56689", à partir de l'index 1919.

Le Thu, 23 Jan 2014 18:03:59 +0100,
Michel Olagnon <molagnon> a écrit :

> Michel Olagnon écrivit :
> J'ai fait un petit programme Fortran, ça a l'air de marcher. En tout
> cas, il donne bien à partir de la table Y la même chose que le calcul
> bestial pour le nombre de valeurs de B chiffres en base S dont la somme
> des chiffres est inférieure ou égale à S. On peut donc trouver à partir
> d'une séquence son index.

Super ! Tu me le confies, contre bons traitements (en gros, le torturer pour
qu'il crache tout ce qu'il a dans le ventre;) ?
Du Fortran, ça doit faire qu'une trentaine d'années que je n'ai rien perforé.
Je verrai si j'ai bien tout oublié !

> J'ai essayé "à la main", et ça marche, a priori.
> Par exemple, B=5, S=10, "56689" donne 51021, qui donne l'index 1919
> L'index 1919 donne 715+495+330+210+126 -> 5 termes et un reste de 43
> 43 pour B=4,S=10-5 donne 35 -> 1 terme et un reste de 8
> 8 pour B=3,S=10-5-1 donne -> 0 terme et un reste de 8
> 8 pour B=2,S=10-5-1 donne 4+3 -> 2 termes et un reste de 1
> 1 pour B=1,S=10-5-1-2 donne 1 -> 1 terme
> J'ai bien reconstruit 51021, et donc "56689", à partir de l'index 1919.

56689 a bien l'index 1919, mais je ne vois pas comment tu passes de
56689 à 51021 ? et inversement..

Ni en fait comment 1919 est décomposé en 715+495+3330+210+126

(en gros, lapin comprit grand chose, le gârs)
Si tu veux bien continuer d'éclairer ma lanterne..

xtof pernod wrote:

> Le Wed, 22 Jan 2014 21:13:59 +0100,
> Damien Wyart <damien.wyart> a écrit :
>> Désolé si j'ai suscité un faux espoir :)
> Pas de soucis, mon bon monsieur.
> Merci pour ta réponse,

Il y a un concept/"data structure", qui s'appelle "sparse matrix".

On peut l'implementer en structure avec des "pointers", ou meme dans un matrix classique ..
[..]

"amusez vous".
les logiciels se trouvent dans les depots de debian, (x/k/edu/l/..)ubuntu, ...
je ne connais pas le nom en francais, mais les logiciels comme ... Octave contiennent des libraries .

ou metis:
METIS is a set of serial programs for partitioning graphs, partitioning finite
element meshes, and producing fill reducing orderings for sparse matrices.
The algorithms implemented in METIS are based on the multilevel
recursive-bisection, multilevel k-way, and multi-constraint partitioning
schemes. The package contains some binaries for graph analyzing.

r-cran-matrix
GNU R package of classes for dense and sparse matrices

This CRAN package provides S4 classes and methods for numerical
linear algebra using dense or sparse matrices. The sparse matrix
implementation uses code from the LDL sparse matrix package and
code from the Metis package of partitioning algorithms.

ergo:
ErgoSCF is a quantum chemistry program for large-scale self-consistent field
calculations. It employs modern linear scaling techniques like fast multipole
methods, hierarchic sparse matrix algebra, density matrix purification, and
efficient integral screening. Linear scaling is achieved not only in terms of
CPU usage but also memory utilization. It uses Gaussian basis sets.

It can compute single-point energies for the following methods:
* Restricted and unrestricted Hartree-Fock (HF) theory
* Restricted and unrestricted Kohn-Sham density functional theory (DFT)
* Full Configuration-Interaction (FCI)

The following Exchange-Correlational (XC) density functionals are included:
* Local Density Approximation (LDA)
* Gradient-corrected (GGA) XC functionals BLYP, BP86, PW91 and PBE
* Hybrid XC functionals B3LYP, BHandHLYP, PBE0 and CAMB3LYP

Further features include:
* Linear response calculations (polarizabilities and excitation energies) for
restricted reference densities
* External electric fields
* Electron dynamics via Time-Dependent Hartree-Fock (TDHF)

--

Je pense que Michel Olagnon propose exactement la même méthode que moi
(ce qui prouve soit qu'on est sur la bonne piste, soit qu'on s'est tous
les deux planté de la même manière :-) ), mais je réponds quand même
pour donner des détails.

On 23/01/14 14:03, xtof pernod wrote:
> Le Wed, 22 Jan 2014 23:13:02 +0000,
> Rémi Moyen <rmoyen+news> a écrit :
> La notation "(a, b)", c'est une sous-table ? Virtuelle / n'ayant pas besoin
> d'exister en mémoire ?
> Ou ça représente juste le nombre d'éléments de cette sous-table ?
> (avec "élément" = "sequence non décroissante", toujours)

Oui, juste la longueur de la table avec ces paramètres. Tu disais dans
ton premier message que tu avais trouvé la formule, donc je suis parti
sur cette piste. Si ça n'est pas le cas, trouve cette formule et tout
sera réglé :-)

Et je suis prêt à parier qu'Olivier a raison, c'est un truc à base de
C(n,p) (pas directement C(B,S), puisque dans ton exemple avec B=3, S=4,
tu as 20 combinaisons et C(3,4) = 4...) et/ou de coefficients binomiaux,
ce qui revient au même.

J'ai donc noté (B, S) le nombre de séquences avec S symboles et de
longueur B (pour garder tes notations) et supposé que tu savais calculer
ce nombre quelque soient B et S.

>> Ça doit pouvoir se continuer récursivement, par exemple une fois le premier
>> symbole fixé, le deuxième symbole est 2 (par exemple) pour (B-2, S-2)
>> séquences, qui commencent après les (B-2, S-1) séquences dont le deuxième
>> symbole est 1, elles-mêmes après les (B-2, S) séquences dont le deuxième
>> symbole est 0.
> L'index du premier symbole: il est calculé algorithmiquement, récursivement,
> ou il doit être connu par avance (ce qui peut se faire, mais en O(N)) ?..

Calculé en faisant la somme des (B-1, S-k) comme expliqué ci-dessous. Je
sais, c'est pas très clair, mais j'ai écrit ça au fur et à mesure, sans
structurer.

> J'ai du louper une marche: je vois pas comment on calcule "(a, b)"
> (désolé!)

Ben tu dis que tu connais le nombre de séquences pour B et S fixé, donc
ça devrait être OK...

> C'est peut-être possible par récursivité, mais je ne vois pas comment
> amorcer la récursion.
> Par ex: B=3, S=4, toujours, et j'ai en entrée: 1 1 3 (index = 12)
> Comment on procède ?..

Oui, ça sera sans doute plus clair sur un exemple :

* Le premier symbole est 1, donc il faut chercher à partir de (B-1, S)
(cad sauter toutes les séquences qui commencent par 0). Donc sauter (2,
4), l'ensemble des séquences de longueur 2 avec 4 symboles, à vue d'oeil
il y en a 10 (00, 01, 02, 03, 11, 12, 13, 22, 23, 33). Index = 10 pour
l'instant (en comptant à partir de 0).

* À partir du deuxième symbole, il faut réduire l'alphabet, puisque si
le premier est 1, le deuxième et plus ne peuvent plus être 0. Donc on
continue sur un alphabet de S-1 (j'avais oublié ça dans mon premier
message, je pense).

* Le deuxième symbole est 1, ce qui est le premier symbole de notre
nouvel alphabet, donc l'index est 0, à ajouter à l'index du premier
symbole, index total = 10 toujours.

* Potentiellement, il faudrait aussi réduire l'alphabet pour passer au
troisième symbole, sauf que là le deuxième symbole étant déjà le début
de l'alphabet réduit, y'a rien de plus à faire, on garde S-1.

* Troisième symbole, 3, il faut sauter les séquences qui auraient 1 ou 2
comme troisième symbole, soit (B-3, S-1) + (B-3, S-2) (B-3 puisqu'on en
est au troisième symbole de la séquence, S-1 pour sauter le premier
symbole (ici 1) d'un alphabet de longueur S-1, S-2 pour sauter le
deuxième symbole (ici 2)). Soit (0, 3) + (0, 2), le nombre de séquences
de 0 symbole de long parmi 3 puis 2 possibles. Là, je pense qu'il faut
arbitrairement décider que (0, S) = 1 quelque soit S... Donc on ajoute
2, pour en arriver à un index final de 12.

Si je reprends ta table :
0 0 0, 0 0 1, 0 0 2, 0 0 3,
0 1 1, 0 1 2, 0 1 3,
0 2 2, 0 2 3,
0 3 3,
1 1 1, 1 1 2, 1 1 3,
1 2 2, 1 2 3,
1 3 3,
2 2 2, 2 2 3, 2 3 3,
3 3 3

Tu peux compter, 113 est bien la séquence d'index 12 (en comptant à
partir de 0).

Donc si tu sais calculer (B, S) quelque soient B et S, tu peux trouver
l'index d'une séquence donnée avec cette méthode.

>>> 2/ une fonction qui donne la séquence en fonction de son index dans la
>>> table.
>> Calculer les (B-1, k) pour k=0...S (ou S-1, j'ai la flemme de réfléchir
>> en détail...), chaque intervalle correspond au premier symbole de la
>> séquence.

En gros, j'inverse l'algo ci-dessus en pré-calculant tous les index de
chaque changement de symbole. Par exemple, sur ta table d'exemple, je
pré-calcule :
- premier symbole = 0 -> index >= 0
- premier symbole = 1 -> index >= 10
- premier symbole = 2 -> index >= 16
- premier symbole = 3 -> index >= 20

Donc en regardant ton index, tu connais le premier symbole. Par exemple
en reprenant l'exemple au dessus, si index = 12, je sais que le premier
symbole est 1.

Ensuite, je refais les tables pour des séquences de longueur B-1, et
comme j'ai éliminé le 0 de mon alphabet, avec S-1 symboles. Il me reste
comme séquences (11, 12, 13, 22, 23, 33).

- symbole 1 -> index >= 0
- symbole 2 -> index >= 3
- symbole 3 -> index >= 6

Ce qui me reste de l'index initial est 2 (12-10), donc le deuxième
symbole est 1. Reste toujours 2 dans mon index.

Je refais les tables de longueur B-2=1, toujours avec S-1=3 symboles,
soit (1, 2, 3).

- symbole 1 -> index >= 0
- symbole 2 -> index >= 1
- symbole 3 -> index >= 2

Reste 2 dans mon index, donc le symbole est 3. Résultat, ma séquence
d'index 12 est 113.

> Toujours le calcul de "(a, b)", à déterminer..

Oui, c'est le coeur de tout l'algo.

>> En fait j'étais en train de me relire avant d'envoyer quand je me suis
>> dit qu'avec mon raisonnement, c'est même encore plus simple :
>> Les séquences qui commencent par 0 commencent à l'index 0 dans la table.
>> Les séquences qui commencent par 1 commencent à l'index (B-1, S)
> Calcul de "(a, b)"..
> Vital, car cette solution a l'air encore plus simple.

C'est juste une reformulation de l'algo ci-dessus, je pense.