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!

I believe those are technically "*permutations*" rather than combinations. https://www.mathsisfun.com/combinatorics/combinations-permutations.html — RBarryYoung, May 19 '16 at 15:23

score 0 · Accepted Answer · answered May 19 '16 at 15:51

0

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

answered May 19 '16 at 15:51

Arturo Menchaca

15,783
1
29
53

thank you for answering..what do you mean with COMBINATION and VISIT? or what would be the php equivalent? – 3Descape May 19 '16 at 16:49
@3Descape: You're welcome. If the answer helps you please consider mark as accepted. Thanks – Arturo Menchaca May 19 '16 at 16:52
hmm.. just found that one: http://stackoverflow.com/questions/3742506/php-array-combinations – 3Descape May 19 '16 at 16:54
@3Descape: This is pseudocode since you don't add any language tag, COMBINATIONS is just the name of the functions, with VISIT I means what you want to do with the generated combination (add it to a list, print in console) – Arturo Menchaca May 19 '16 at 16:57
yea I got that it is pseudocode, but what does this do? COMBINATIONS(array, length): COMBINATIONS("", array, length) – 3Descape May 19 '16 at 17:19
it's calling the other COMBINATIONS function below – Arturo Menchaca May 19 '16 at 17:21

Algorithm for creating all possible strings with x characters

1 Answers1