|
|
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. |
|
Fuseau horaire GMT +2. Il est actuellement 19h20. | Privacy Policy
|