Algorithm for creating all possible strings with x characters

Question

I can't wrap my head around the algorithm for making the following:

I have an array for all possible characters: array("a", "b", "c",...."z", " ", "!"...) you get the idea.

Now I would like to generate all possible compinations of these characters with the length of x.

so for example the array("a", "b", "c") with the length of 4: aaaa abaa acaa aaba aaca aaab aaac abba abca acba acca (....) baaa caaa

and so on...

Thanks in advice!

Answer 1

You can try it with recursion:

COMBINATIONS(array, length):
    COMBINATIONS("", array, length)

COMBINATIONS(string, array, length):
    IF length == 0
        VISIT(string)
    ELSE
        FOR EACH c IN array
            COMBINATIONS(string + c, array, length - 1)

The basic idea is start with an empty string, then in each execution, call recursively for each character in the array. This will generate for each string previously generated a new string for each character in the array concatenated at the end.

When you reach the desired length then 'visit' the generated combination.

For example, for array = ['a', 'b', 'c'] and length = 3:

aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc