What are some ways I can relate an index to an N length string?

Question

Here's the situation:

I have 36 characters to choose from, a-z and 0-9.

char[] alphabet = "0123456789abcdefghijklmnopqrstuvwxyz".toCharArray();

And using an index, we want to create all possible strings of length N, from N = 1 to N = 2.

A length of 1 is rather simple,

private String generateString(int index){    
    if (index < 36){
        char word = alphabet[index];
        return String.valueOf(word);
    }

    if ( index < 1332) {
        //lost
    }
}

But what if we wanted a length of 2, well we can assume that all words of length 2 will have an index of > 36 and < 1332 (36 + (36^2)). But I am lost on how to relate these indexes to a word with length 2, and making sure all possible word combinations are hit.

I think there is a mathematical way to accomplish this, but I am just not seeing it.

Check out [this question](http://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string). — takendarkk, Mar 25 '14 at 18:08
Do you mean anything like: `553 -> "tx", 678 -> "yd"`, and so on? — VH-NZZ, Mar 25 '14 at 19:26

score 0 · Answer 1 · answered Mar 25 '14 at 20:22

I'm not sure if I got your question right. Do you want all combinations of letters in various string lengths (like in a brute force attack)? Then this might help you.

If your alphabet consists just of 0-z, then you can make use of Java's Integer.toString() method providing a radix of 36, and just do some counting and padding:

void start(int lengthFrom, int lengthTo) {
    for (int length = lengthFrom; length <= lengthTo; length++) {
        for (int i=0; i < Math.pow(36, length); i++) {
            result(String.format("%" + length + "s", Integer.toString(i, 36)).replace(' ', '0'));
        }
    }
}

void result(String s) {
    System.out.println(s);
}

If you need more flexibility in regard to your alphabet, check this code. Here you can add whatever characters, because it just fills them recursively from left to right:

char[] alphabet = "0123456789abcdefghijklmnopqrstuvwxyz".toCharArray();

void start(int lengthFrom, int lengthTo) {
    for (int length = lengthFrom; length <= lengthTo; length++) {
        char[] chars = new char[length];
        fill(chars, 0);
    }
}

void fill(char[] chars, int pos) {
    if (chars.length == pos) {
        result(new String(chars));
        return;
    }
    for (char c : alphabet) {
        chars[pos] = c;
        fill(chars, pos+1);
    }
}

void result(String s) {
    System.out.println(s);
}

This method uses recursion. All recursive algorithms can be transformed to iterative algorithms; which usually consume less memory but are also less easy to read.

If you want an "index" for your Strings, you could build it using the result() method as the passed strings are ordered.

score 0 · Answer 2 · answered Mar 25 '14 at 20:33

0

Oh, you're not talking about this, right?

Integer.parseInt(word, 36);
Integer.toString(index, 36);

So that

Integer.parseInt("1z", 36); // int(71)
Integer.toString(71, 36);   // "1z"

answered Mar 25 '14 at 20:33

steffen

16,138
4
42
81

score 0 · Answer 3 · answered Mar 25 '14 at 21:29

For the two letter words, create a mapping [1,2,...,1296] -> ["00","01",...,"zz"] by folding the 1d index into a 2d one of size 36, ie. [1,2,...,1296] -> [(1,1), (2,1), (3,1), ..., (36,36)]:

private String generateTwoLetterString(final int index) {
    if(index > 1296) 
        throw new IndexOutOfBoundsException("index is greater than 1296");

    int j = (int) Math.ceil(index/36f);
    int i = index % 36 == 0 ? 36 : index % 36;

    return String.format("%s%s", alphabet[j-1], alphabet[i-1]);
}

If you look at @steffen's shorter answer, my function above will output the same as `Integer.toString(index-1, 36)`. — VH-NZZ, Mar 25 '14 at 21:35

What are some ways I can relate an index to an N length string?

3 Answers3