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 = a1 = b...1294 = 33321295 = 3333

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

aa...a1aa1aaa1

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:

babaabaaab

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 61          12          2...6          67          118          12...11         1512         1613         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.

abc123aabaca1a2a3aabbbcb1b2b3bacbccc1c2c3ca1b1c1112131a2b2c2122232a3b3c3132333aaabaacaa1aa2aa3aaababbacba1ba2ba3baacabcacca1ca2ca3caa1ab1ac1a11a21a31aa2ab2ac2a12a22a32aa3ab3ac3a13a23a33aaabbabcab1ab2ab3ababbbbbcbb1bb2bb3bbacbbcbccb1cb2cb3cba1bb1bc1b11b21b31ba2bb2bc2b12b22b32ba3bb3bc3b13b23b33baacbaccac1ac2ac3acabcbbccbc1bc2bc3bcaccbccccc1cc2cc3cca1cb1cc1c11c21c31ca2cb2cc2c12c22c32ca3cb3cc3c13c23c33caa1ba1ca11a12a13a1ab1bb1cb11b12b13b1ac1bc1cc11c12c13c1a11b11c11111211311a21b21c21121221321a31b31c31131231331aa2ba2ca21a22a23a2ab2bb2cb21b22b23b2ac2bc2cc21c22c23c2a12b12c12112212312a22b22c22122222322a32b32c32132232332aa3ba3ca31a32a33a3ab3bb3cb31b32b33b3ac3bc3cc31c32c33c3a13b13c13113213313a23b23c23123223323a33b33c33133233333aaaabaaacaaa1aaa2aaa3aaaabaabbaacbaa1baa2baa3baaacaabcaaccaa1caa2caa3caaa1aab1aac1aa11aa21aa31aaa2aab2aac2aa12aa22aa32aaa3aab3aac3aa13aa23aa33aaaabababacaba1aba2aba3abaabbabbbacbba1bba2bba3bbaacbabcbaccba1cba2cba3cbaa1bab1bac1ba11ba21ba31baa2bab2bac2ba12ba22ba32baa3bab3bac3ba13ba23ba33baaacabacacaca1aca2aca3acaabcabbcacbca1bca2bca3bcaaccabccaccca1cca2cca3ccaa1cab1cac1ca11ca21ca31caa2cab2cac2ca12ca22ca32caa3cab3cac3ca13ca23ca33caaa1aba1aca1a1a1a2a1a3a1aab1abb1acb1a1b1a2b1a3b1aac1abc1acc1a1c1a2c1a3c1aa11ab11ac11a111a211a311aa21ab21ac21a121a221a321aa31ab31ac31a131a231a331aaa2aba2aca2a1a2a2a2a3a2aab2abb2acb2a1b2a2b2a3b2aac2abc2acc2a1c2a2c2a3c2aa12ab12ac12a112a212a312aa22ab22ac22a122a222a322aa32ab32ac32a132a232a332aaa3aba3aca3a1a3a2a3a3a3aab3abb3acb3a1b3a2b3a3b3aac3abc3acc3a1c3a2c3a3c3aa13ab13ac13a113a213a313aa23ab23ac23a123a223a323aa33ab33ac33a133a233a333aaaabbaabcaab1aab2aab3aabababbbabcbab1bab2bab3babacabbcabccab1cab2cab3caba1abb1abc1ab11ab21ab31aba2abb2abc2ab12ab22ab32aba3abb3abc3ab13ab23ab33abaabbbabbcabb1abb2abb3abbabbbbbbbcbbb1bbb2bbb3bbbacbbbcbbccbb1cbb2cbb3cbba1bbb1bbc1bb11bb21bb31bba2bbb2bbc2bb12bb22bb32bba3bbb3bbc3bb13bb23bb33bbaacbbacbcacb1acb2acb3acbabcbbbcbcbcb1bcb2bcb3bcbaccbbccbcccb1ccb2ccb3ccba1cbb1cbc1cb11cb21cb31cba2cbb2cbc2cb12cb22cb32cba3cbb3cbc3cb13cb23cb33cbaa1bba1bca1b1a1b2a1b3a1bab1bbb1bcb1b1b1b2b1b3b1bac1bbc1bcc1b1c1b2c1b3c1ba11bb11bc11b111b211b311ba21bb21bc21b121b221b321ba31bb31bc31b131b231b331baa2bba2bca2b1a2b2a2b3a2bab2bbb2bcb2b1b2b2b2b3b2bac2bbc2bcc2b1c2b2c2b3c2ba12bb12bc12b112b212b312ba22bb22bc22b122b222b322ba32bb32bc32b132b232b332baa3bba3bca3b1a3b2a3b3a3bab3bbb3bcb3b1b3b2b3b3b3bac3bbc3bcc3b1c3b2c3b3c3ba13bb13bc13b113b213b313ba23bb23bc23b123b223b323ba33bb33bc33b133b233b333baaacbaaccaac1aac2aac3aacabacbbaccbac1bac2bac3bacacacbcacccac1cac2cac3caca1acb1acc1ac11ac21ac31aca2acb2acc2ac12ac22ac32aca3acb3acc3ac13ac23ac33acaabcbabccabc1abc2abc3abcabbcbbbccbbc1bbc2bbc3bbcacbcbcbcccbc1cbc2cbc3cbca1bcb1bcc1bc11bc21bc31bca2bcb2bcc2bc12bc22bc32bca3bcb3bcc3bc13bc23bc33bcaaccbacccacc1acc2acc3accabccbbcccbcc1bcc2bcc3bccacccbccccccc1ccc2ccc3ccca1ccb1ccc1cc11cc21cc31cca2ccb2ccc2cc12cc22cc32cca3ccb3ccc3cc13cc23cc33ccaa1cba1cca1c1a1c2a1c3a1cab1cbb1ccb1c1b1c2b1c3b1cac1cbc1ccc1c1c1c2c1c3c1ca11cb11cc11c111c211c311ca21cb21cc21c121c221c321ca31cb31cc31c131c231c331caa2cba2cca2c1a2c2a2c3a2cab2cbb2ccb2c1b2c2b2c3b2cac2cbc2ccc2c1c2c2c2c3c2ca12cb12cc12c112c212c312ca22cb22cc22c122c222c322ca32cb32cc32c132c232c332caa3cba3cca3c1a3c2a3c3a3cab3cbb3ccb3c1b3c2b3c3b3cac3cbc3ccc3c1c3c2c3c3c3ca13cb13cc13c113c213c313ca23cb23cc23c123c223c323ca33cb33cc33c133c233c333caaa1baa1caa11aa12aa13aa1aba1bba1cba11ba12ba13ba1aca1bca1cca11ca12ca13ca1a1a1b1a1c1a111a121a131a1a2a1b2a1c2a112a122a132a1a3a1b3a1c3a113a123a133a1aab1bab1cab11ab12ab13ab1abb1bbb1cbb11bb12bb13bb1acb1bcb1ccb11cb12cb13cb1a1b1b1b1c1b111b121b131b1a2b1b2b1c2b112b122b132b1a3b1b3b1c3b113b123b133b1aac1bac1cac11ac12ac13ac1abc1bbc1cbc11bc12bc13bc1acc1bcc1ccc11cc12cc13cc1a1c1b1c1c1c111c121c131c1a2c1b2c1c2c112c122c132c1a3c1b3c1c3c113c123c133c1aa11ba11ca111a112a113a11ab11bb11cb111b112b113b11ac11bc11cc111c112c113c11a111b111c111111121113111a211b211c211121122113211a311b311c311131123113311aa21ba21ca211a212a213a21ab21bb21cb211b212b213b21ac21bc21cc211c212c213c21a121b121c121112121213121a221b221c221122122213221a321b321c321132123213321aa31ba31ca311a312a313a31ab31bb31cb311b312b313b31ac31bc31cc311c312c313c31a131b131c131113121313131a231b231c231123122313231a331b331c331133123313331aaa2baa2caa21aa22aa23aa2aba2bba2cba21ba22ba23ba2aca2bca2cca21ca22ca23ca2a1a2b1a2c1a211a221a231a2a2a2b2a2c2a212a222a232a2a3a2b3a2c3a213a223a233a2aab2bab2cab21ab22ab23ab2abb2bbb2cbb21bb22bb23bb2acb2bcb2ccb21cb22cb23cb2a1b2b1b2c1b211b221b231b2a2b2b2b2c2b212b222b232b2a3b2b3b2c3b213b223b233b2aac2bac2cac21ac22ac23ac2abc2bbc2cbc21bc22bc23bc2acc2bcc2ccc21cc22cc23cc2a1c2b1c2c1c211c221c231c2a2c2b2c2c2c212c222c232c2a3c2b3c2c3c213c223c233c2aa12ba12ca121a122a123a12ab12bb12cb121b122b123b12ac12bc12cc121c122c123c12a112b112c112111221123112a212b212c212121222123212a312b312c312131223123312aa22ba22ca221a222a223a22ab22bb22cb221b222b223b22ac22bc22cc221c222c223c22a122b122c122112221223122a222b222c222122222223222a322b322c322132223223322aa32ba32ca321a322a323a32ab32bb32cb321b322b323b32ac32bc32cc321c322c323c32a132b132c132113221323132a232b232c232123222323232a332b332c332133223323332aaa3baa3caa31aa32aa33aa3aba3bba3cba31ba32ba33ba3aca3bca3cca31ca32ca33ca3a1a3b1a3c1a311a321a331a3a2a3b2a3c2a312a322a332a3a3a3b3a3c3a313a323a333a3aab3bab3cab31ab32ab33ab3abb3bbb3cbb31bb32bb33bb3acb3bcb3ccb31cb32cb33cb3a1b3b1b3c1b311b321b331b3a2b3b2b3c2b312b322b332b3a3b3b3b3c3b313b323b333b3aac3bac3cac31ac32ac33ac3abc3bbc3cbc31bc32bc33bc3acc3bcc3ccc31cc32cc33cc3a1c3b1c3c1c311c321c331c3a2c3b2c3c2c312c322c332c3a3c3b3c3c3c313c323c333c3aa13ba13ca131a132a133a13ab13bb13cb131b132b133b13ac13bc13cc131c132c133c13a113b113c113111321133113a213b213c213121322133213a313b313c313131323133313aa23ba23ca231a232a233a23ab23bb23cb231b232b233b23ac23bc23cc231c232c233c23a123b123c123112321233123a223b223c223122322233223a323b323c323132323233323aa33ba33ca331a332a333a33ab33bb33cb331b332b333b33ac33bc33cc331c332c333c33a133b133c133113321333133a233b233c233123322333233a333b333c333133323333333

Best and neat way to solve this problem is to use recursive solution, hope in-line comments are good enough to understand the solution:

<?php// Recursive method that print all permutation of a given length// @param $arr input array// @param $arrLen just the length of the above array// @param $size length or size for which we are making all permutation// @param $perArr this is a temporary array to hold the current permutation being created// @param $pos current position of $perArrfunction printPermutation($arr, $arrLen, $size, $perArr, $pos) {   if ($size==$pos) { //if $pos reach $size then we have found one permutation      for ($i=0; $i<$size; $i++) print $perArr[$i];      print ("\n");      return;   }   for ($i=0; $i<$arrLen; $i++) {      $perArr[$pos] = $arr[$i]; //put i'th char in current position      //The recursive call that move to next position with $pos+1      printPermutation($arr, $arrLen, $size, $perArr, $pos+1);    }}//all printPermutation method with 1 - maxLenfunction showAllPermutation($letters, $maxLen) {   $length = count($letters);   $perArr = array();   for ($i=1; $i<=$maxLen; $i++) {      printPermutation ($letters, $length, $i, $perArr, 0);   }}//main$letters = array('a','b','c','1','2','3');$max_length = 4;showAllPermutation ($letters, $max_length);?>

If you are interested, here is the very big output of the above code:stdout:

abc123aaabaca1a2a3babbbcb1b2b3cacbccc1c2c31a1b1c1112132a2b2c2122233a3b3c313233aaaaabaacaa1aa2aa3abaabbabcab1ab2ab3acaacbaccac1ac2ac3a1aa1ba1ca11a12a13a2aa2ba2ca21a22a23a3aa3ba3ca31a32a33baababbacba1ba2ba3bbabbbbbcbb1bb2bb3bcabcbbccbc1bc2bc3b1ab1bb1cb11b12b13b2ab2bb2cb21b22b23b3ab3bb3cb31b32b33caacabcacca1ca2ca3cbacbbcbccb1cb2cb3ccaccbccccc1cc2cc3c1ac1bc1cc11c12c13c2ac2bc2cc21c22c23c3ac3bc3cc31c32c331aa1ab1ac1a11a21a31ba1bb1bc1b11b21b31ca1cb1cc1c11c21c311a11b11c11111211312a12b12c12112212313a13b13c1311321332aa2ab2ac2a12a22a32ba2bb2bc2b12b22b32ca2cb2cc2c12c22c321a21b21c21121221322a22b22c22122222323a23b23c2312322333aa3ab3ac3a13a23a33ba3bb3bc3b13b23b33ca3cb3cc3c13c23c331a31b31c31131231332a32b32c32132232333a33b33c331332333aaaaaaabaaacaaa1aaa2aaa3aabaaabbaabcaab1aab2aab3aacaaacbaaccaac1aac2aac3aa1aaa1baa1caa11aa12aa13aa2aaa2baa2caa21aa22aa23aa3aaa3baa3caa31aa32aa33abaaabababacaba1aba2aba3abbaabbbabbcabb1abb2abb3abcaabcbabccabc1abc2abc3ab1aab1bab1cab11ab12ab13ab2aab2bab2cab21ab22ab23ab3aab3bab3cab31ab32ab33acaaacabacacaca1aca2aca3acbaacbbacbcacb1acb2acb3accaaccbacccacc1acc2acc3ac1aac1bac1cac11ac12ac13ac2aac2bac2cac21ac22ac23ac3aac3bac3cac31ac32ac33a1aaa1aba1aca1a1a1a2a1a3a1baa1bba1bca1b1a1b2a1b3a1caa1cba1cca1c1a1c2a1c3a11aa11ba11ca111a112a113a12aa12ba12ca121a122a123a13aa13ba13ca131a132a133a2aaa2aba2aca2a1a2a2a2a3a2baa2bba2bca2b1a2b2a2b3a2caa2cba2cca2c1a2c2a2c3a21aa21ba21ca211a212a213a22aa22ba22ca221a222a223a23aa23ba23ca231a232a233a3aaa3aba3aca3a1a3a2a3a3a3baa3bba3bca3b1a3b2a3b3a3caa3cba3cca3c1a3c2a3c3a31aa31ba31ca311a312a313a32aa32ba32ca321a322a323a33aa33ba33ca331a332a333baaabaabbaacbaa1baa2baa3babababbbabcbab1bab2bab3bacabacbbaccbac1bac2bac3ba1aba1bba1cba11ba12ba13ba2aba2bba2cba21ba22ba23ba3aba3bba3cba31ba32ba33bbaabbabbbacbba1bba2bba3bbbabbbbbbbcbbb1bbb2bbb3bbcabbcbbbccbbc1bbc2bbc3bb1abb1bbb1cbb11bb12bb13bb2abb2bbb2cbb21bb22bb23bb3abb3bbb3cbb31bb32bb33bcaabcabbcacbca1bca2bca3bcbabcbbbcbcbcb1bcb2bcb3bccabccbbcccbcc1bcc2bcc3bc1abc1bbc1cbc11bc12bc13bc2abc2bbc2cbc21bc22bc23bc3abc3bbc3cbc31bc32bc33b1aab1abb1acb1a1b1a2b1a3b1bab1bbb1bcb1b1b1b2b1b3b1cab1cbb1ccb1c1b1c2b1c3b11ab11bb11cb111b112b113b12ab12bb12cb121b122b123b13ab13bb13cb131b132b133b2aab2abb2acb2a1b2a2b2a3b2bab2bbb2bcb2b1b2b2b2b3b2cab2cbb2ccb2c1b2c2b2c3b21ab21bb21cb211b212b213b22ab22bb22cb221b222b223b23ab23bb23cb231b232b233b3aab3abb3acb3a1b3a2b3a3b3bab3bbb3bcb3b1b3b2b3b3b3cab3cbb3ccb3c1b3c2b3c3b31ab31bb31cb311b312b313b32ab32bb32cb321b322b323b33ab33bb33cb331b332b333caaacaabcaaccaa1caa2caa3cabacabbcabccab1cab2cab3cacacacbcacccac1cac2cac3ca1aca1bca1cca11ca12ca13ca2aca2bca2cca21ca22ca23ca3aca3bca3cca31ca32ca33cbaacbabcbaccba1cba2cba3cbbacbbbcbbccbb1cbb2cbb3cbcacbcbcbcccbc1cbc2cbc3cb1acb1bcb1ccb11cb12cb13cb2acb2bcb2ccb21cb22cb23cb3acb3bcb3ccb31cb32cb33ccaaccabccaccca1cca2cca3ccbaccbbccbcccb1ccb2ccb3cccacccbccccccc1ccc2ccc3cc1acc1bcc1ccc11cc12cc13cc2acc2bcc2ccc21cc22cc23cc3acc3bcc3ccc31cc32cc33c1aac1abc1acc1a1c1a2c1a3c1bac1bbc1bcc1b1c1b2c1b3c1cac1cbc1ccc1c1c1c2c1c3c11ac11bc11cc111c112c113c12ac12bc12cc121c122c123c13ac13bc13cc131c132c133c2aac2abc2acc2a1c2a2c2a3c2bac2bbc2bcc2b1c2b2c2b3c2cac2cbc2ccc2c1c2c2c2c3c21ac21bc21cc211c212c213c22ac22bc22cc221c222c223c23ac23bc23cc231c232c233c3aac3abc3acc3a1c3a2c3a3c3bac3bbc3bcc3b1c3b2c3b3c3cac3cbc3ccc3c1c3c2c3c3c31ac31bc31cc311c312c313c32ac32bc32cc321c322c323c33ac33bc33cc331c332c3331aaa1aab1aac1aa11aa21aa31aba1abb1abc1ab11ab21ab31aca1acb1acc1ac11ac21ac31a1a1a1b1a1c1a111a121a131a2a1a2b1a2c1a211a221a231a3a1a3b1a3c1a311a321a331baa1bab1bac1ba11ba21ba31bba1bbb1bbc1bb11bb21bb31bca1bcb1bcc1bc11bc21bc31b1a1b1b1b1c1b111b121b131b2a1b2b1b2c1b211b221b231b3a1b3b1b3c1b311b321b331caa1cab1cac1ca11ca21ca31cba1cbb1cbc1cb11cb21cb31cca1ccb1ccc1cc11cc21cc31c1a1c1b1c1c1c111c121c131c2a1c2b1c2c1c211c221c231c3a1c3b1c3c1c311c321c3311aa11ab11ac11a111a211a311ba11bb11bc11b111b211b311ca11cb11cc11c111c211c3111a111b111c111111121113112a112b112c112111221123113a113b113c11311132113312aa12ab12ac12a112a212a312ba12bb12bc12b112b212b312ca12cb12cc12c112c212c3121a121b121c121112121213122a122b122c122112221223123a123b123c12311232123313aa13ab13ac13a113a213a313ba13bb13bc13b113b213b313ca13cb13cc13c113c213c3131a131b131c131113121313132a132b132c132113221323133a133b133c1331133213332aaa2aab2aac2aa12aa22aa32aba2abb2abc2ab12ab22ab32aca2acb2acc2ac12ac22ac32a1a2a1b2a1c2a112a122a132a2a2a2b2a2c2a212a222a232a3a2a3b2a3c2a312a322a332baa2bab2bac2ba12ba22ba32bba2bbb2bbc2bb12bb22bb32bca2bcb2bcc2bc12bc22bc32b1a2b1b2b1c2b112b122b132b2a2b2b2b2c2b212b222b232b3a2b3b2b3c2b312b322b332caa2cab2cac2ca12ca22ca32cba2cbb2cbc2cb12cb22cb32cca2ccb2ccc2cc12cc22cc32c1a2c1b2c1c2c112c122c132c2a2c2b2c2c2c212c222c232c3a2c3b2c3c2c312c322c3321aa21ab21ac21a121a221a321ba21bb21bc21b121b221b321ca21cb21cc21c121c221c3211a211b211c211121122113212a212b212c212121222123213a213b213c21312132213322aa22ab22ac22a122a222a322ba22bb22bc22b122b222b322ca22cb22cc22c122c222c3221a221b221c221122122213222a222b222c222122222223223a223b223c22312232223323aa23ab23ac23a123a223a323ba23bb23bc23b123b223b323ca23cb23cc23c123c223c3231a231b231c231123122313232a232b232c232123222323233a233b233c2331233223333aaa3aab3aac3aa13aa23aa33aba3abb3abc3ab13ab23ab33aca3acb3acc3ac13ac23ac33a1a3a1b3a1c3a113a123a133a2a3a2b3a2c3a213a223a233a3a3a3b3a3c3a313a323a333baa3bab3bac3ba13ba23ba33bba3bbb3bbc3bb13bb23bb33bca3bcb3bcc3bc13bc23bc33b1a3b1b3b1c3b113b123b133b2a3b2b3b2c3b213b223b233b3a3b3b3b3c3b313b323b333caa3cab3cac3ca13ca23ca33cba3cbb3cbc3cb13cb23cb33cca3ccb3ccc3cc13cc23cc33c1a3c1b3c1c3c113c123c133c2a3c2b3c2c3c213c223c233c3a3c3b3c3c3c313c323c3331aa31ab31ac31a131a231a331ba31bb31bc31b131b231b331ca31cb31cc31c131c231c3311a311b311c311131123113312a312b312c312131223123313a313b313c31313132313332aa32ab32ac32a132a232a332ba32bb32bc32b132b232b332ca32cb32cc32c132c232c3321a321b321c321132123213322a322b322c322132223223323a323b323c32313232323333aa33ab33ac33a133a233a333ba33bb33bc33b133b233b333ca33cb33cc33c133c233c3331a331b331c331133123313332a332b332c332133223323333a333b333c333133323333

I'd go with recursive solution.
"Guess" what is the first element, and recurse on the following elements.
Repeat for all possible guesses.

pseudo code:

findCombinations(array, candidate, length):  //base clause:  if (candidate.length == length):       return  for each i from 0to array.length:       //i is the next char to add       candidate.append(array[i])       //print the candidate, since it is a unique permutation smaller then length:       print candidate       //recursively find permutations for the remianing elements       findCombinations(array,candidate,length)       //clean up        candidate.removeLasElement()

Java Code:

private static void findCombinations(char[] array, StringBuilder candidate, int length) {       //base clause:      if (candidate.length() == length)           return;      for (int i = 0; i < array.length; i++) {            //i is the next char to add           candidate.append(array[i]);           //print the candidate, since it is a unique permutation smaller then length:           System.out.println(candidate);           //recursively find permutations for the remianing elements           findCombinations(array,candidate,length);           //clean up            candidate.deleteCharAt(candidate.length()-1);      }}public static void findCombinations(char[] array,int length) {     findCombinations(array, new StringBuilder(), length);}

Invoking:

    char[] arr = "abcde".toCharArray();    findCombinations(arr, 3);

results in:

aaaaaaaabaacaadaaeababaabbabcabdabeacacaacbaccacdaceadadaadbadcaddadeaeaeaaebaecaedaeebbabaababbacbadbaebbbbabbbbbcbbdbbebcbcabcbbccbcdbcebdbdabdbbdcbddbdebebeabebbecbedbeeccacaacabcaccadcaecbcbacbbcbccbdcbeccccaccbcccccdccecdcdacdbcdccddcdececeacebceccedceeddadaadabdacdaddaedbdbadbbdbcdbddbedcdcadcbdccdcddceddddaddbddcdddddededeadebdecdeddeeeeaeaaeabeaceadeaeebebaebbebcebdebeececaecbeccecdeceededaedbedceddedeeeeeaeebeeceedeee