C'est presque une publication croisée de Math SE - alors que l'explication de mon problème est identique, sur Math.SE je demandais une solution mathématique à mon problème.

Mon problème est que la solution que j'ai obtenue sur Math.SE était "convertir en base 35", ce qui est probablement une très bonne réponse, mais je suis vraiment horrible avec les mathématiques et je ne comprends pas comment appliquer la solution dans mon code. J'ai essayé de chercher une leçon sur la conversion vers différentes bases, et c'est assez déroutant pour moi . Même en regardant une question sur la conversion de nombres en bases en JavaScript n'a pas précisé comment je l'utiliserais exactement pour ce que je dois faire.

Existe-t-il un moyen simple de gérer cela en JavaScript? Voici la question dans son intégralité:

J'ai un problème de programmation inhabituel et le côté mathématique me laisse perplexe.

J'ai généré une chaîne unique de sept caractères qui sont chacun choisis au hasard parmi ces possibilités: ABCDEFGHIJKLMNOPQRSTUVWXYZ123456789 par exemple A6HJ92B et je dois la convertir en une valeur numérique unique. Une fois convertie, deux versions de cette chaîne aléatoire ne peuvent pas être le numéro de nom.

Je pourrais simplement générer un nombre plutôt que d'inclure des lettres dans l'ID d'origine, mais bien sûr, cela signifie que je dois augmenter la longueur de ma chaîne, et il est possible que l'utilisateur de mon application veuille taper cette chaîne, car il identifie son "session" dans une application, donc je veux être bref.

Mon idée était donc de construire une table comme celle-ci:

A : 1,
B : 2,
C : 3,
D : 4,
E : 5,
F : 6,
G : 7,
H : 8,

... you get the idea ...

5 : 31,
6 : 32,
7 : 33,
8 : 34,
9 : 35

Et puis j'ajouterais tous les chiffres ...

A6HJ92B:

A : 1
6 : 32
H : 8
J : 10
9 : 35
2 : 28
B : 2

1+32+8+10+35+28+2 = 116

... mais j'ai réalisé que c'est une idée erronée car de nombreuses chaînes possibles "entreront en collision" ou égaleront le même nombre. J'ai besoin que chaque chaîne unique soit égale à un nombre unique.

Donc, même si j'ai multiplié la valeur de chaque personnage (1*32*8*10*35*28*2 = 5,017,600), je pense qu'il pourrait y avoir des collisions possibles là aussi.

Existe-t-il un moyen de calculer cela de manière à éliminer les collisions? Si les collisions ne peuvent pas être éliminées, quelles méthodes puis-je utiliser pour les minimiser?

13
user5536767 6 mars 2016 à 02:31

3 réponses

Meilleure réponse

Fondamentalement, vous voulez une transformation injective f : S → N, où S est le ensemble de chaînes JS de longueur 7 avec les caractères A-Z1-9, et N est l'ensemble de tous les nombres JS.

Une approche possible consiste à considérer que les chaînes de S sont un positionnel codage de nombres, comme vous l'avez tenté.

Cependant, afin d'être injectif (éviter les collisions), vous devez multiplier la valeur de chaque caractère par la base à la puissance de la position.

Par exemple, étant donné le tableau suivant des valeurs de caractères

0 ⟶  0
1 ⟶  1
⋮      ⋮
9 ⟶  9
A ⟶ 10
B ⟶ 11
⋮      ⋮
Z ⟶ 35

A6HJ92B deviendrait 10×36⁶ + 6×36⁵ + 17×36⁴ + 19×36³ + 9×36² + 2×36 + 11, c'est-à-dire 22160072099.

Vous pouvez effectuer la conversion facilement avec parseInt et toString:

parseInt('A6HJ92B', 36); // 22160072099
(22160072099).toString(36).toUpperCase(); // "A6HJ92B"

Si vous souhaitez utiliser une table de valeurs arbitraires, vous devrez coder les transformations manuellement.

Notez que dans JS, les nombres sont des flottants double précision de 64 bits. Cela signifie qu'il existe une précision finie et que vous ne pouvez pas stocker de grands nombres arbitraires. Cela ne fonctionnera pas correctement au-delà de ce maximum

Number.MAX_SAFE_INTEGER; // 9007199254740991
Number.MAX_SAFE_INTEGER.toString(36).toUpperCase(); // "2GOSA7PA2GV"

Mais comme vos chaînes n'ont que 7 caractères, cela devrait suffire.

17
Oriol 6 mars 2016 à 15:13

Vous pouvez multiplier par la puissance de position:

function StringAdder(obj){
  this.vals = obj;
  this.add = function(str){
    var s = str.split(''), l = s.length, p = Math.pow(10, (l-1)), r = 0;
    for(var i=0; i<l; i++){
      r += this.vals[s[i]]*p; p = p/10;
    }
    return r;
  }
}
var vals = {
  A: 1,
  6: 32,
  H: 8,
  J: 10,
  9: 35,
  2: 28,
  B: 2
}
var sa = new StringAdder(vals);
console.log(sa.add('A6HJ92B')); console.log(sa.add('HJA6B29'));
4
StackSlave 6 mars 2016 à 00:33

Vous ne pensez tout simplement pas au problème de la bonne façon. Commençons par quelque chose que vous connaissez mieux; décimal ou base 10.

Le numéro 7158 est composé de:

  7 x 10 ^ 3
 +1 x 10 ^ 2
 +5 x 10 ^ 1
 +8 x 10 ^ 0

Pour représenter le nombre en base X, vous remplacez le 10 par X.

Alors maintenant, la question devient comment convertir entre les bases. La solution la plus simple consiste à diviser par X à plusieurs reprises - à chaque fois convertir le reste en base X et l'ajouter à l'avant de votre chaîne de sortie jusqu'à ce qu'il ne reste plus rien, puis utilisez la partie entière de la division pour l'itération suivante:

7158 /35 = 204 remainder 18
204 / 35 = 5 remainder 29
5 / 35 = 0 remainder 5

Donc en base 35, le nombre décimal 7158 est représenté par les symboles que vous choisissez pour [5] [29] [18]

Si vous essayez vous-même l'exemple ci-dessus en multipliant la partie fractionnaire de chaque division par 35, vous pouvez obtenir des résultats qui ne sont pas des entiers - les ordinateurs fonctionnent en binaire (et effectuent automatiquement la conversion de base) et ne fonctionnent qu'avec un nombre fixe de chiffres - C'est à dire selon la façon dont vous effectuez le calcul, vous devrez peut-être arrondir d'environ 0,00001 pour obtenir le reste sous forme d'entier.

5
symcbean 6 mars 2016 à 00:01