npm install --save indexed-string-variation
Generally useful to create distributed brute-force password recovery tools or other software that might require distributed generation of all possible strings on a given alphabet.
const generator = generator;const variations = ;for let i=0; i < 23; i++console; // generates the i-th string in the alphabet 'abc1'
0 ''1 'a'2 'b'3 'c'4 '1'5 'aa'6 'ab'7 'ac'8 'a1'9 'ba'10 'bb'11 'bc'12 'b1'13 'ca'14 'cb'15 'cc'16 'c1'17 '1a'18 '1b'19 '1c'20 '11'21 'aaa'22 'aab'
indexed-string-variation exposes the following components:
generator(also aliased as
defaultfor ES2015 modules): the main generator function
defaultAlphabet: a constant string that contains the sequence of characters in the defaultAlphabet
As you can see in the usage example, the
generator function takes as input the
alphabet string (which is optional and it will default to
not provided) and returns a new function called
variations which can be
used to retrieve the indexed variation on the given alphabet.
a non-negative integer as input which represents the index of the variations
that we want to generate:
const variations = ;console; // "XYYZYZZZYYYZYZYXYYYYX"
How the algorithm works
The way the generation algorithm work is using an n-ary tree where n is the size of the alphabet.
For example, if we have an alphabet containing only
c and we want to generate all
the strings with a maximum length of 3 the algorithm will use the following tree:
The tree is to be considered "virtual", because it's never generated in its integrity, so the used space in memory is minimal.
In brevity we can describe the algorithm as follows:
Given an index i over an alphabet of length n and it's corresponding n-ary tree, the string associated to i corresponds to the string obtained by concatenating all the characters found in the path that goes from the root node to the i-th node.
For example, with the alphabet in the image we can generate the following strings:
Important note: The alphabet is always normalized (i.e. duplicates are removed)
Integers with more than 18 digits are approximated (e.g.
123456789012345680000 === 123456789012345678901), so at some
point the generator will start to generate a lot of duplicated strings and it will start to miss many cases.
To workaround this issue you can use indexes generated with the module big-integer. Internally the indexed-string-variation will take care of performing the correct operations using the library.
Let's see an example:
const bigInt = ; // install fromconst generator = generator;const variations = ;// generation using regular big numbers (same result)console; // XJZJYXXXYYJKYZZJKZKYJWJJYWconsole; // XJZJYXXXYYJKYZZJKZKYJWJJYW// generation using big-integer numbers (correct results)console; // XJZJYXXXYYJKYZZJKZKXZKJZZJconsole; // XJZJYXXXYYJKYZZJKZKXZWJJWK
Everyone is very welcome to contribute to this project. You can contribute just by submitting bugs or suggesting improvements by opening an issue on GitHub.
Licensed under MIT License. © Luciano Mammino.