Algorithm to Get All Possible String Combinations from Array Up to Certain Length

Algorithm to get all possible string combinations from array up to certain length

Almost a Base Conversion

This solution is motivated by the observation that, if it were not for the possibility of repeating the character at array index 0 in the high-order position of a valid combination, this problem would simply be a base conversion from decimal to the new base of all integers from 0 to (base^length)-1. So,

0 = a
1 = b
...
1294 = 3332
1295 = 3333

The difficulty is that this misses combinations with one or more leading 'a', like:

aa
...
a1
aa1
aaa1

And these are the only solutions missing. So one could simply, for each generated combination with length less than max_length, add 'a' (or whatever is at letters[0]) to the front of the string, and output that string, repeating if necessary. So if you generate the string 'b', you'd output:

b
ab
aab
aaab

This works, but it is unsatisfying, first because it looks like a kludged solution. Second, it does not generate the solutions in lexicographical order, which may or may not be a problem. Third, it would be really nice if the function to generate the combinations was bijective so that we knew the unique combination that results from any given decimal integer and the unique index of any combination. This will be critical in a moment.

Imagine There's No Zero

If the zero index is giving us problems, then why not do away with it? Say we change the array to:

letters = {∅,'a','b','c','1','2','3'}

where ∅ is an arbitrary placeholder that will never be used. We will now attempt to represent the decimal integers from 1 to base^max_length in the new base (in this case still 6, not 7) without using the digit zero. We'll represent the numbers from 1 to base-1 as normal (1, 2, 3, ...) but when we get to the number equal to the base, rather than represent it as 10, we'll represent it as the base digit (e.g., 6 rather than 10 in base 6). The next number, base+1, would be 11, then 12 up to 16 (which is equal to 12 decimal) and then up to 21. Each number

a_n,a_n-1,...,a₁,a₀

in the new base is equal to

a_n*bⁿ+a_n-1*b^n-1+...+a₁*b¹+a₀*b⁰

in decimal, where b is the new base.

As I've come to learn, this is fittingly called a bijective numeration. Taking an example, in base 6 we would have:

Base 10    Base 6
1          1
2          2
...
6          6
7          11
8          12
...
11         15
12         16
13         21
...
36         56

From the Wikipedia link above, the first "digit" of the number in the new base is:

a₀ = m - q₀k

where k is the new base, m is the integer to convert, and q₀ = ceiling(m/k)-1. Note the similarity to a normal base conversion where the only difference is that q₀ would be floor(m/k) or ordinary integer division. Subsequent "digits" are computed similarly, using q₀ instead of m to find a₁, etc.

This formula can be broken down into two cases:

• (m mod k) == 0: a₀ = k and q₀ = (m div k) - 1
• (m mod k) != 0: a₀ = (m mod k) and q₀ = (m div k)

This is the heart of the algorithm. For any integer m we can iteratively apply this formula until the resulting q_p == 0. Also note that the conversion is, naturally, reversible. Given a number 6666 in base 6, the decimal value is:

(6*6^3)+(6*6^2)+(6*6^1)+(6*6^0)=1554

We use this fact to find the range of integers to convert in order to get all combinations of a certain length. Sorry, but my PHP skills are non-existent. Hopefully the Java code is clear enough. Given:

    char [] letters = new char [] {'0','a','b','c','1','2','3'};
    int max_length = 4;

we have the function:

    int b = letters.length - 1;  // base to convert to
    int n = 0;
    for (int k = 0; k < max_length; k++)
        n = (n*b)+b;  // number of combinations

    int remainder;
    for (int i = 1; i <= n; i++) {
        int current = i;  // m and q_n in the formula
        String combination = "";
        do {
            remainder = current % b;
            if (remainder == 0) {
                combination += letters[b];
                current = current/b - 1;
            } else {
                combination += letters[remainder];
                current = current/b;
            }
        } while (current > 0);
        System.out.println(combination);
    }

where / represents integer division, or floor(a/b).

The function relies only on the input integer and not on the results of previous calculations, so the possibilities for parallel processing are pretty good.

Here is the output with the above input. Least significant digit is first, as per your example.

a
b
c
1
2
3
aa
ba
ca
1a
2a
3a
ab
bb
cb
1b
2b
3b
ac
bc
cc
1c
2c
3c
a1
b1
c1
11
21
31
a2
b2
c2
12
22
32
a3
b3
c3
13
23
33
aaa
baa
caa
1aa
2aa
3aa
aba
bba
cba
1ba
2ba
3ba
aca
bca
cca
1ca
2ca
3ca
a1a
b1a
c1a
11a
21a
31a
a2a
b2a
c2a
12a
22a
32a
a3a
b3a
c3a
13a
23a
33a
aab
bab
cab
1ab
2ab
3ab
abb
bbb
cbb
1bb
2bb
3bb
acb
bcb
ccb
1cb
2cb
3cb
a1b
b1b
c1b
11b
21b
31b
a2b
b2b
c2b
12b
22b
32b
a3b
b3b
c3b
13b
23b
33b
aac
bac
cac
1ac
2ac
3ac
abc
bbc
cbc
1bc
2bc
3bc
acc
bcc
ccc
1cc
2cc
3cc
a1c
b1c
c1c
11c
21c
31c
a2c
b2c
c2c
12c
22c
32c
a3c
b3c
c3c
13c
23c
33c
aa1
ba1
ca1
1a1
2a1
3a1
ab1
bb1
cb1
1b1
2b1
3b1
ac1
bc1
cc1
1c1
2c1
3c1
a11
b11
c11
111
211
311
a21
b21
c21
121
221
321
a31
b31
c31
131
231
331
aa2
ba2
ca2
1a2
2a2
3a2
ab2
bb2
cb2
1b2
2b2
3b2
ac2
bc2
cc2
1c2
2c2
3c2
a12
b12
c12
112
212
312
a22
b22
c22
122
222
322
a32
b32
c32
132
232
332
aa3
ba3
ca3
1a3
2a3
3a3
ab3
bb3
cb3
1b3
2b3
3b3
ac3
bc3
cc3
1c3
2c3
3c3
a13
b13
c13
113
213
313
a23
b23
c23
123
223
323
a33
b33
c33
133
233
333
aaaa
baaa
caaa
1aaa
2aaa
3aaa
abaa
bbaa
cbaa
1baa
2baa
3baa
acaa
bcaa
ccaa
1caa
2caa
3caa
a1aa
b1aa
c1aa
11aa
21aa
31aa
a2aa
b2aa
c2aa
12aa
22aa
32aa
a3aa
b3aa
c3aa
13aa
23aa
33aa
aaba
baba
caba
1aba
2aba
3aba
abba
bbba
cbba
1bba
2bba
3bba
acba
bcba
ccba
1cba
2cba
3cba
a1ba
b1ba
c1ba
11ba
21ba
31ba
a2ba
b2ba
c2ba
12ba
22ba
32ba
a3ba
b3ba
c3ba
13ba
23ba
33ba
aaca
baca
caca
1aca
2aca
3aca
abca
bbca
cbca
1bca
2bca
3bca
acca
bcca
ccca
1cca
2cca
3cca
a1ca
b1ca
c1ca
11ca
21ca
31ca
a2ca
b2ca
c2ca
12ca
22ca
32ca
a3ca
b3ca
c3ca
13ca
23ca
33ca
aa1a
ba1a
ca1a
1a1a
2a1a
3a1a
ab1a
bb1a
cb1a
1b1a
2b1a
3b1a
ac1a
bc1a
cc1a
1c1a
2c1a
3c1a
a11a
b11a
c11a
111a
211a
311a
a21a
b21a
c21a
121a
221a
321a
a31a
b31a
c31a
131a
231a
331a
aa2a
ba2a
ca2a
1a2a
2a2a
3a2a
ab2a
bb2a
cb2a
1b2a
2b2a
3b2a
ac2a
bc2a
cc2a
1c2a
2c2a
3c2a
a12a
b12a
c12a
112a
212a
312a
a22a
b22a
c22a
122a
222a
322a
a32a
b32a
c32a
132a
232a
332a
aa3a
ba3a
ca3a
1a3a
2a3a
3a3a
ab3a
bb3a
cb3a
1b3a
2b3a
3b3a
ac3a
bc3a
cc3a
1c3a
2c3a
3c3a
a13a
b13a
c13a
113a
213a
313a
a23a
b23a
c23a
123a
223a
323a
a33a
b33a
c33a
133a
233a
333a
aaab
baab
caab
1aab
2aab
3aab
abab
bbab
cbab
1bab
2bab
3bab
acab
bcab
ccab
1cab
2cab
3cab
a1ab
b1ab
c1ab
11ab
21ab
31ab
a2ab
b2ab
c2ab
12ab
22ab
32ab
a3ab
b3ab
c3ab
13ab
23ab
33ab
aabb
babb
cabb
1abb
2abb
3abb
abbb
bbbb
cbbb
1bbb
2bbb
3bbb
acbb
bcbb
ccbb
1cbb
2cbb
3cbb
a1bb
b1bb
c1bb
11bb
21bb
31bb
a2bb
b2bb
c2bb
12bb
22bb
32bb
a3bb
b3bb
c3bb
13bb
23bb
33bb
aacb
bacb
cacb
1acb
2acb
3acb
abcb
bbcb
cbcb
1bcb
2bcb
3bcb
accb
bccb
cccb
1ccb
2ccb
3ccb
a1cb
b1cb
c1cb
11cb
21cb
31cb
a2cb
b2cb
c2cb
12cb
22cb
32cb
a3cb
b3cb
c3cb
13cb
23cb
33cb
aa1b
ba1b
ca1b
1a1b
2a1b
3a1b
ab1b
bb1b
cb1b
1b1b
2b1b
3b1b
ac1b
bc1b
cc1b
1c1b
2c1b
3c1b
a11b
b11b
c11b
111b
211b
311b
a21b
b21b
c21b
121b
221b
321b
a31b
b31b
c31b
131b
231b
331b
aa2b
ba2b
ca2b
1a2b
2a2b
3a2b
ab2b
bb2b
cb2b
1b2b
2b2b
3b2b
ac2b
bc2b
cc2b
1c2b
2c2b
3c2b
a12b
b12b
c12b
112b
212b
312b
a22b
b22b
c22b
122b
222b
322b
a32b
b32b
c32b
132b
232b
332b
aa3b
ba3b
ca3b
1a3b
2a3b
3a3b
ab3b
bb3b
cb3b
1b3b
2b3b
3b3b
ac3b
bc3b
cc3b
1c3b
2c3b
3c3b
a13b
b13b
c13b
113b
213b
313b
a23b
b23b
c23b
123b
223b
323b
a33b
b33b
c33b
133b
233b
333b
aaac
baac
caac
1aac
2aac
3aac
abac
bbac
cbac
1bac
2bac
3bac
acac
bcac
ccac
1cac
2cac
3cac
a1ac
b1ac
c1ac
11ac
21ac
31ac
a2ac
b2ac
c2ac
12ac
22ac
32ac
a3ac
b3ac
c3ac
13ac
23ac
33ac
aabc
babc
cabc
1abc
2abc
3abc
abbc
bbbc
cbbc
1bbc
2bbc
3bbc
acbc
bcbc
ccbc
1cbc
2cbc
3cbc
a1bc
b1bc
c1bc
11bc
21bc
31bc
a2bc
b2bc
c2bc
12bc
22bc
32bc
a3bc
b3bc
c3bc
13bc
23bc
33bc
aacc
bacc
cacc
1acc
2acc
3acc
abcc
bbcc
cbcc
1bcc
2bcc
3bcc
accc
bccc
cccc
1ccc
2ccc
3ccc
a1cc
b1cc
c1cc
11cc
21cc
31cc
a2cc
b2cc
c2cc
12cc
22cc
32cc
a3cc
b3cc
c3cc
13cc
23cc
33cc
aa1c
ba1c
ca1c
1a1c
2a1c
3a1c
ab1c
bb1c
cb1c
1b1c
2b1c
3b1c
ac1c
bc1c
cc1c
1c1c
2c1c
3c1c
a11c
b11c
c11c
111c
211c
311c
a21c
b21c
c21c
121c
221c
321c
a31c
b31c
c31c
131c
231c
331c
aa2c
ba2c
ca2c
1a2c
2a2c
3a2c
ab2c
bb2c
cb2c
1b2c
2b2c
3b2c
ac2c
bc2c
cc2c
1c2c
2c2c
3c2c
a12c
b12c
c12c
112c
212c
312c
a22c
b22c
c22c
122c
222c
322c
a32c
b32c
c32c
132c
232c
332c
aa3c
ba3c
ca3c
1a3c
2a3c
3a3c
ab3c
bb3c
cb3c
1b3c
2b3c
3b3c
ac3c
bc3c
cc3c
1c3c
2c3c
3c3c
a13c
b13c
c13c
113c
213c
313c
a23c
b23c
c23c
123c
223c
323c
a33c
b33c
c33c
133c
233c
333c
aaa1
baa1
caa1
1aa1
2aa1
3aa1
aba1
bba1
cba1
1ba1
2ba1
3ba1
aca1
bca1
cca1
1ca1
2ca1
3ca1
a1a1
b1a1
c1a1
11a1
21a1
31a1
a2a1
b2a1
c2a1
12a1
22a1
32a1
a3a1
b3a1
c3a1
13a1
23a1
33a1
aab1
bab1
cab1
1ab1
2ab1
3ab1
abb1
bbb1
cbb1
1bb1
2bb1
3bb1
acb1
bcb1
ccb1
1cb1
2cb1
3cb1
a1b1
b1b1
c1b1
11b1
21b1
31b1
a2b1
b2b1
c2b1
12b1
22b1
32b1
a3b1
b3b1
c3b1
13b1
23b1
33b1
aac1
bac1
cac1
1ac1
2ac1
3ac1
abc1
bbc1
cbc1
1bc1
2bc1
3bc1
acc1
bcc1
ccc1
1cc1
2cc1
3cc1
a1c1
b1c1
c1c1
11c1
21c1
31c1
a2c1
b2c1
c2c1
12c1
22c1
32c1
a3c1
b3c1
c3c1
13c1
23c1
33c1
aa11
ba11
ca11
1a11
2a11
3a11
ab11
bb11
cb11
1b11
2b11
3b11
ac11
bc11
cc11
1c11
2c11
3c11
a111
b111
c111
1111
2111
3111
a211
b211
c211
1211
2211
3211
a311
b311
c311
1311
2311
3311
aa21
ba21
ca21
1a21
2a21
3a21
ab21
bb21
cb21
1b21
2b21
3b21
ac21
bc21
cc21
1c21
2c21
3c21
a121
b121
c121
1121
2121
3121
a221
b221
c221
1221
2221
3221
a321
b321
c321
1321
2321
3321
aa31
ba31
ca31
1a31
2a31
3a31
ab31
bb31
cb31
1b31
2b31
3b31
ac31
bc31
cc31
1c31
2c31
3c31
a131
b131
c131
1131
2131
3131
a231
b231
c231
1231
2231
3231
a331
b331
c331
1331
2331
3331
aaa2
baa2
caa2
1aa2
2aa2
3aa2
aba2
bba2
cba2
1ba2
2ba2
3ba2
aca2
bca2
cca2
1ca2
2ca2
3ca2
a1a2
b1a2
c1a2
11a2
21a2
31a2
a2a2
b2a2
c2a2
12a2
22a2
32a2
a3a2
b3a2
c3a2
13a2
23a2
33a2
aab2
bab2
cab2
1ab2
2ab2
3ab2
abb2
bbb2
cbb2
1bb2
2bb2
3bb2
acb2
bcb2
ccb2
1cb2
2cb2
3cb2
a1b2
b1b2
c1b2
11b2
21b2
31b2
a2b2
b2b2
c2b2
12b2
22b2
32b2
a3b2
b3b2
c3b2
13b2
23b2
33b2
aac2
bac2
cac2
1ac2
2ac2
3ac2
abc2
bbc2
cbc2
1bc2
2bc2
3bc2
acc2
bcc2
ccc2
1cc2
2cc2
3cc2
a1c2
b1c2
c1c2
11c2
21c2
31c2
a2c2
b2c2
c2c2
12c2
22c2
32c2
a3c2
b3c2
c3c2
13c2
23c2
33c2
aa12
ba12
ca12
1a12
2a12
3a12
ab12
bb12
cb12
1b12
2b12
3b12
ac12
bc12
cc12
1c12
2c12
3c12
a112
b112
c112
1112
2112
3112
a212
b212
c212
1212
2212
3212
a312
b312
c312
1312
2312
3312
aa22
ba22
ca22
1a22
2a22
3a22
ab22
bb22
cb22
1b22
2b22
3b22
ac22
bc22
cc22
1c22
2c22
3c22
a122
b122
c122
1122
2122
3122
a222
b222
c222
1222
2222
3222
a322
b322
c322
1322
2322
3322
aa32
ba32
ca32
1a32
2a32
3a32
ab32
bb32
cb32
1b32
2b32
3b32
ac32
bc32
cc32
1c32
2c32
3c32
a132
b132
c132
1132
2132
3132
a232
b232
c232
1232
2232
3232
a332
b332
c332
1332
2332
3332
aaa3
baa3
caa3
1aa3
2aa3
3aa3
aba3
bba3
cba3
1ba3
2ba3
3ba3
aca3
bca3
cca3
1ca3
2ca3
3ca3
a1a3
b1a3
c1a3
11a3
21a3
31a3
a2a3
b2a3
c2a3
12a3
22a3
32a3
a3a3
b3a3
c3a3
13a3
23a3
33a3
aab3
bab3
cab3
1ab3
2ab3
3ab3
abb3
bbb3
cbb3
1bb3
2bb3
3bb3
acb3
bcb3
ccb3
1cb3
2cb3
3cb3
a1b3
b1b3
c1b3
11b3
21b3
31b3
a2b3
b2b3
c2b3
12b3
22b3
32b3
a3b3
b3b3
c3b3
13b3
23b3
33b3
aac3
bac3
cac3
1ac3
2ac3
3ac3
abc3
bbc3
cbc3
1bc3
2bc3
3bc3
acc3
bcc3
ccc3
1cc3
2cc3
3cc3
a1c3
b1c3
c1c3
11c3
21c3
31c3
a2c3
b2c3
c2c3
12c3
22c3
32c3
a3c3
b3c3
c3c3
13c3
23c3
33c3
aa13
ba13
ca13
1a13
2a13
3a13
ab13
bb13
cb13
1b13
2b13
3b13
ac13
bc13
cc13
1c13
2c13
3c13
a113
b113
c113
1113
2113
3113
a213
b213
c213
1213
2213
3213
a313
b313
c313
1313
2313
3313
aa23
ba23
ca23
1a23
2a23
3a23
ab23
bb23
cb23
1b23
2b23
3b23
ac23
bc23
cc23
1c23
2c23
3c23
a123
b123
c123
1123
2123
3123
a223
b223
c223
1223
2223
3223
a323
b323
c323
1323
2323
3323
aa33
ba33
ca33
1a33
2a33
3a33
ab33
bb33
cb33
1b33
2b33
3b33
ac33
bc33
cc33
1c33
2c33
3c33
a133
b133
c133
1133
2133
3133
a233
b233
c233
1233
2233
3233
a333
b333
c333
1333
2333
3333

Algorithm for generating all string combinations

Here's how I would do it in Javascript (I assume that every string contains no duplicate characters):

function getPermutations(arr)
{
  return getPermutationsHelper(arr, 0, "");
}

function getPermutationsHelper(arr, idx, prefix)
{
  var foundInCurrent = [];
  for(var i = 0; i < arr[idx].length; i++)
  {
    var str = prefix + arr[idx].charAt(i);

    if(idx < arr.length - 1)
    {
      foundInCurrent = foundInCurrent.concat(getPermutationsHelper(arr, idx + 1, str));
    }
    else
    {
      foundInCurrent.push(str);
    }
  }
  return foundInCurrent;
}

Basically, I'm using a recursive approach. My base case is when I have no more words left in my array, in which case I simply add prefix + c to my array for every c (character) in my last word.

Otherwise, I try each letter in the current word, and pass the prefix I've constructed on to the next word recursively.

For your example array, I got:

adg adh adi adj aeg aeh aei aej afg afh afi afj bdg bdh bdi 
bdj beg beh bei bej bfg bfh bfi bfj cdg cdh cdi cdj ceg ceh 
cei cej cfg cfh cfi cfj

Getting all combination of array elements that form a given string

You can use backtracking. Here is some pseudo code:

def generateSolutions(unusedWords, usedWords, string, position):
    if position == string.length():
        print(usedWords)
    else:
         for word in unusedWords:
             if word is a prefix of string[position ... s.length() - 1]:
                 generateSolutions(unusedWords - word, usedWords + word, 
                                   string, position + word.length())

generateSolution(words, an empty list, input string, 0)

The idea is very simple: we can just pick an unused word that matches a prefix of the rest of the input string and keep generating all valid combinations recursively(I assume that we can use each word from the given list of words only once). This solution has an exponential time complexity, but is not possible to do much better in the worst case. For instance, if the given string is abcdef...yz and the list of words is [a, b, c, ..., z, ab, cd, ..., yz], the number of such combinations is 2 ^ n / 2, where n is the length of the given string.

Algorithm to find all combinations of a string, maintain order, not fixed length

Here are two ways it could be done without making use of Array#combination. I've also included code for the case when combination is permitted (#3)¹.

1. Map each of the numbers between 1 and 2**n-1 (n being the length of the string) to a unique combination of characters from the string

def string_combinations(str)
  arr = str.chars
  (1..2**str.length-1).map do |n|
    pos = n.bit_length.times.map.with_object([]) { |i,a| a << i if n[i] == 1 }
    arr.values_at(*pos).join
  end.sort
end

string_combinations("wxyz")
  # => ["w", "wx", "wxy", "wxyz", "wxz", "wy", "wyz", "wz",
  #     "x", "xy", "xyz", "xz", "y", "yz", "z"] 

Discrete probability theory provides us with the equation

sum(i = 1 to n) ( |i| C(n,i) ) == 2^n - 1

where C(n,i) is "the number of combinations of n things taken i at a time".

If the given string is "wxyz", n = "wxyz".length #=> 4, so there are 2**4 - 1 #=> 15 combinations of one or more characters from this string. Now consider any of the numbers between 1 and 16, say 11, which is 0b1011 in binary. Converting this to an array of binary digits, we obtain:

bin_arr = [1,0,1,1]

We now pluck out each character of wxyz for which the corresponding index position in bin_arr equals 1, namely

["w", "y", "z"]

and then join those elements to form a string:

["w", "y", "z"].join #=> "wyz"

Since each number 1 to 15 corresponds to a distinct combination of one or more characters from this string, , we can obtain all such combinations by repeating the above calculation for each the numbers between 1 and 15.

No matter which method you use, the resulting array will contain 2**n - 1 elements, so you are looking at O(2**str.length).

2. Use recursion

def string_combinations(str)
  (combos(str) - [""]).sort
end

def combos(str)
  return [str, ""] if str.length==1
  forward = combos str[1..-1]
  [*forward, *[str[0]].product(forward).map(&:join)]
end

string_combinations("wxyz")
  # => ["w", "wx", "wxy", "wxyz", "wxz", "wy", "wyz", "wz",
  #     "x", "xy", "xyz", "xz", "y", "yz", "z"] 

Notice that

combos("wxyz")
  #=> ["z", "", "yz", "y", "xz", "x", "xyz", "xy",
  #    "wz", "w", "wyz", "wy", "wxz", "wx", "wxyz", "wxy"] 

includes an empty string, which must be removed, and the array needs sorting. Hence the need to separate out the recursive method combos.

3. Use Array#combination

Here we invoke arr.combination(n) for all values of n between 1 and arr.size and return a (flattened) array comprised of all n return values.

def string_combinations(str)
  a = str.chars
  (1..str.size).flat_map { |n| a.combination(n).map(&:join) }.sort
end

string_combinations "wxyz"
  # => ["w", "wx", "wxy", "wxyz", "wxz", "wy", "wyz", "wz",
  #     "x", "xy", "xyz", "xz", "y", "yz", "z"] 

^{_{1 Since I wrote it before realizing that's not what the OP wanted. ¯\_(ツ)_/¯}}

Iteratively find all combinations of size k of an array of characters (N choose K)

Here's another iterative solution:

You can create an array of integers of size K to act as a counter recording how far you are through the combinations, and a char array to store the current combination.

After printing each one, move on to the next combination by increasing one of the counter values, and if it "overflows" by reaching a value equal to the number of elements in E, then reset it to zero and perform a carry by incrementing the counter in the next position, checking for overflows there too and so on. Kind of like an odometer in a car, except that the numbers are tied to values in E. Once the last position overflows then you have generated all the possible combinations.

I've incremented the counters starting from the last value in the array and moving downwards to get the same output as in your example, but that isn't necessary of course. The algorithm doesn't check for duplicates.

You don't have to store an array of chars with the current combination, you could just re-generate it each time in a for loop based on the counters, but that might be less efficient. This approach only updates the values that change.

public static void buildStrings(char[] root, int length)
{
    // allocate an int array to hold the counts:
    int[] pos = new int[length];
    // allocate a char array to hold the current combination:
    char[] combo = new char[length];
    // initialize to the first value:
    for(int i = 0; i < length; i++)
        combo[i] = root[0];

    while(true)
    {
        // output the current combination:
        System.out.println(String.valueOf(combo));

        // move on to the next combination:
        int place = length - 1;
        while(place >= 0)
        {
            if(++pos[place] == root.length)
            {
                // overflow, reset to zero
                pos[place] = 0;
                combo[place] = root[0];
                place--; // and carry across to the next value
            }
            else
            {
                // no overflow, just set the char value and we're done
                combo[place] = root[pos[place]];
                break;
            }
        }
        if(place < 0)
            break;  // overflowed the last position, no more combinations
    }
}

ideone.com demo

PHP algorithm to generate all combinations of a specific size from a single set

I would use a recursive function. Here's a (working) example with comments. Hope this works for you!

function sampling($chars, $size, $combinations = array()) {

    # if it's the first iteration, the first set 
    # of combinations is the same as the set of characters
    if (empty($combinations)) {
        $combinations = $chars;
    }

    # we're done if we're at size 1
    if ($size == 1) {
        return $combinations;
    }

    # initialise array to put new values in
    $new_combinations = array();

    # loop through existing combinations and character set to create strings
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            $new_combinations[] = $combination . $char;
        }
    }

    # call same function again for the next iteration
    return sampling($chars, $size - 1, $new_combinations);

}

// example
$chars = array('a', 'b', 'c');
$output = sampling($chars, 2);
var_dump($output);
/*
array(9) {
  [0]=>
  string(2) "aa"
  [1]=>
  string(2) "ab"
  [2]=>
  string(2) "ac"
  [3]=>
  string(2) "ba"
  [4]=>
  string(2) "bb"
  [5]=>
  string(2) "bc"
  [6]=>
  string(2) "ca"
  [7]=>
  string(2) "cb"
  [8]=>
  string(2) "cc"
}
*/

Count all possible decoding Combination of the given binary String in Java

In essence, Dynamic Programming is an enhanced brute-force approach.

Like in the case of brute-force, we need to generate all possible results. But contrary to a plain brute-force the problem should be divided into smaller subproblems, and previously computed result of each subproblem should be stored and reused.

Since you are using recursion you need to apply so-called Memoization technic in order to store and reuse the intermediate results. In this case, HashMap would be a perfect mean of storing results.

But before applying the memoization in order to understand it better, it makes sense to start with a clean and simple recursive solution that works correctly, and only then enhance it with DP.

Plain Recursion

Every recursive implementation should contain two parts:

• Base case - that represents a simple edge-case (or a set of edge-cases) for which the outcome is known in advance. For this problem, there are two edge-cases: the length of the given string is 0 and result would be 1 (an empty binary string "" results into an empty string of letters ""), another case is when it's impossible to decode a given binary string and result will be 0 (in the solution below it resolves naturally when the recursive case is being executed).

• Recursive case - a part of a solution where recursive calls a made and when the main logic resides. In the recursive case, we need to find each binary "binary letter" at the beginning of the string and then call the method recursively by passing the substring (without the "letter"). Results of these recursive calls need to be accumulated in the total count that will returned from the method.

In order to implement this logic we need only two arguments: the binary string to analyze and a list of binary letters:

public static int count(String str, List<String> letters) {
    if (str.isEmpty()) { // base case - a combination was found
        return 1;
    }

    // recursive case
    int count = 0;
    
    for (String letter: letters) {
        if (str.startsWith(letter)) {
            count += count(str.substring(letter.length()), letters);
        }
    }        
    return count;
}

This concise solution is already capable of producing the correct result. Now, let's turn this brute-force version into a DP-based solution, by applying the memoization.

Dynamic Programming

As I've told earlier, a HashMap will be a perfect mean to store the intermediate results because allows to associate a count (number of combinations) with a particular string and then retrieve this number almost instantly (in O(1) time).

That how it might look like:

public static int count(String str, List<String> letters, Map<String, Integer> vocab) {
    if (str.isEmpty()) { // base case - a combination was found
        return 1;
    }
    if (vocab.containsKey(str)) { // result was already computed and present in the map 
        return vocab.get(str);
    }

    int count = 0;

    for (String letter: letters) {
        if (str.startsWith(letter)) {
            count += count(str.substring(letter.length()), letters, vocab);
        }
    }
    vocab.put(str, count); // storing the total `count` into the map

    return count;
}

main()

public static void main(String[] args) {
    
    List<String> letters = List.of("0", "00", "001", "010", "0010", "0100", "0110", "0001"); // binary letters

    System.out.println(count("00100", letters, new HashMap<>())); // DP
    System.out.println(count("00100", letters));                  // brute-force recursion
}

Output:

5   // DP
5   // plain recursion

A link to Online Demo

---

Related Topics