Best way to get alphanumeric string by incrementing

Question

I'm working on Akka for F#. I want to sequentially generate alphanumeric strings.

For example: The first string is 0, the second is 1, then 2, etc. When it reaches 9 I want it to go to lowercase "a". When it reaches "z", I want it to go to uppercase "A". When it reaches "Z" it should become 00. And so on...

I want to search the whole space of these strings in order, I don't want to randomly generate them. Basically I'm asking for an increase function like i++, but instead of base 10 arithmetic, I want it to have base 62 arithmetic. What is the best way to go about it in a functional language like F#? Can I somehow take advantage of the fact that the ASCII representation of the letters is in order? But then the numbers are adjoint to the letter representation in ASCII.

Bonus question: How can I perform any arithmetic on this system, let's say x <- x+100?

Answer 1

The main question is whether you want to do the calculation using integers and then just convert it to your numerical format when you need to print the number, or whether you want to do arithmetic directly using your representation. In the former case, you can just use normal numerical operations on integers and you'll just need conversion function. In the latter case, you'll need to implement your own numerical operations.

For the s++ operation, a basic F# option could be a recursive function. Here, I'm representing the string as a list of characters (in a reverse order) so for example, plusplus ['Z';'Z'] becomes ['0';'0';'0']. The operation itself just needs alphabet and a dictionary of successors:

let alphabet = ['0' .. '9'] @ ['a' .. 'z'] @ ['A' .. 'Z']
let succ = Seq.zip alphabet (Seq.tail alphabet) |> dict

let rec plusplus l = 
  match l with 
  | [] -> [ List.head alphabet ]
  | x::xs ->
      if succ.ContainsKey(x) then
        succ.[x] :: xs
      else 
        (List.head alphabet) :: plusplus xs

plusplus ['Z'; 'Z']

Answer 2

What you basically need is just a way to convert a number to string representation and vice-versa. This task is by the way, always the same, for every base. Here a step-by-step solution.

To convert a number to binary, you can use the following algorithm.

let rec toBinary x =
    if x = 0 then "0"
    else
        let y = x % 2
        (toBinary ((x-y)/2)) + (string y)

As an example, this is how you convert to Octal representation.

let rec toOctal x =
    if x = 0 then "0"
    else
        let y = x % 8
        (toOctal ((x-y)/8)) + (string y)

As you see, its always the same. Make a module on the base, to get the right most number. Repeat on the subtraction and division of the base.

20

20 % 2 = 0  // 20 / 2
10 % 2 = 0  // 10 / 2
5  % 2 = 1  // (5-1) / 2
2  % 2 = 0  // 2 / 1
1  % 2 = 1  // (1-1) / 2
         0      

This way, you uild the number from right-to-left and it works for any base.

Now, instead of writing every version, you could make it more general, by providing the base as a number.

let rec toBase nbase x =
    if x = 0 then "0"
    else
        let y = x % nbase
        (toBase nbase ((x-y)/nbase)) + (string y)

And to make it even more general, you could provide a string list, with your mappings. Like this.

let rec toBase' nbase x =
    let bse = List.length nbase

    if x = 0 then 
        nbase.[0] 
    else
        let y = x % bse
        (toBase' nbase ((x-y)/bse)) + (nbase.[y])

Now, you can create arbitary mappings.

let toBin  = toBase' ["0";"1"]
let toABCD = toBase' ["A";"B";"C";"D"]
let toHex  = toBase' ["0";"1";"2";"3";"4";"5";"6";"7";"8";"9";"A";"B";"C";"D";"E";"F"]
let toOct  = toBase' ["0";"1";"2";"3";"4";"5";"6";"7"]

Next, you should do the reverse. Map a string, back to a number. The usually way, is to understand, that a number is a multiplication at a position. For example the binary number "1010" really means:

(1 * 8) + (0 * 4) + (1 * 2) + (0 * 1)

And as code:

let rec toInt nbase x =
    let bse = List.length nbase
    let mut = pown bse (String.length x - 1)

    if x = "" then 
        0 
    else
        let fc    = string (x.[0])
        let index = List.findIndex (fun e -> e = fc) nbase
        (toInt nbase (x.[1..])) + (index * mut)

Now you can define the reverse.

let toBin   = toBase' ["0";"1"]
let fromBin = toInt   ["0";"1"]

let toABCD   = toBase' ["A";"B";"C";"D"]
let fromABCD = toInt   ["A";"B";"C";"D"]

let toHex   = toBase' ["0";"1";"2";"3";"4";"5";"6";"7";"8";"9";"A";"B";"C";"D";"E";"F"]
let fromHex = toInt   ["0";"1";"2";"3";"4";"5";"6";"7";"8";"9";"A";"B";"C";"D";"E";"F"]

let toOct   = toBase' ["0";"1";"2";"3";"4";"5";"6";"7"]
let fromOct = toInt   ["0";"1";"2";"3";"4";"5";"6";"7"]

If you now want a stream of numbers, you just can List.map your numbers, or create a sequence from it. For example, a stream of binary numbers. This sequence is what you wanted as your "++" operation. A lazy sequence that counts up, all your variants.

let binaryStream = Seq.initInfinite toBin

for x in Seq.take 10 binaryStream do
    printfn "%s" x

// Will print
// 0
// 01
// 010
// 011
// 0100
// 0101
// 0110
// 0111
// 01000
// 01001

Will print the first, 10 binary numbers. If you want to add + 100 to a string, you first convert it to a number, to number multipliciation, and convert it back to a string. Or providers those functions you want. For example to add two binary strings.

let addBin x y =
    toBin ((fromBin x) + (fromBin y))

addBin "1000" "1010"  // 8 + 10

Now you can do your base62. For example, to print the first 200 strings.

let toB62 = 
    toBase' (
        List.map string [0..9]
        @ List.map string ['a' .. 'z']
        @ List.map string ['A' .. 'Z'])

let fromB62 =
    toInt (
        List.map string [0..9]
        @ List.map string ['a' .. 'z']
        @ List.map string ['A' .. 'Z'])

let b62stream = Seq.initInfinite toB62

for x in Seq.take 200 b62stream do
    printfn "%s" x

Answer 3

I add another answers, as i feel, my previous answer is not quit right. With the other code you can convert any number to any other base and vice-versa, but it doesn't do exactly what you needed.

In some case, i think what you really need, is the Cartesian Product.

In your case, you want to generate strings, and in your special case you would add/prepend every character to a string list. And you repeat this operation depending on how long your string should be.

let rec product depth xs = seq {
    if depth = 0 then 
        yield ""
    else
        for x in xs do
            for str in product (depth-1) xs do
                yield x + str
}

Examples:

product 1 ["0";"1"]
// seq ["0"; "1"]

product 2 ["0";"1"]
// seq ["00"; "01"; "10"; "11"]

product 3 ["0";"1"]
// seq ["000"; "001"; "010"; "011"
//      "100"; "101"; "110"; "111"

This generates all posible strings for a given size. But i guess you want to go through all combinations, up to a size. You can do this, like this.

let productUpto depth xs = seq {
    for x=1 to depth do
        yield! product x xs
}

Now the following code

for x in productUpto 4 ["A";"B"] do
    printfn "%s" x

Prints:

A
B
AA
AB
BA
BB
AAA
AAB
ABA
ABB
BAA
BAB
BBA
BBB
AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB

This generates the output in a sequence like you want. But with this version, it is not possible to do addition of strings.