What is the best algorithm to get all possible string combinations from a given array with a minimum & maximum length value.
Note: This adds complexity since the value is variable unlike the questions these are linked to.
For example:
$letters = array('a','b','c','1','2','3');
$min_length = 1;
$max_length = 4;
a
b
c
1
2
3
.
.
.
aaaa
a123
b123
c123
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.
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
an,an-1,...,a1,a0
in the new base is equal to
an*bn+an-1*bn-1+...+a1*b1+a0*b0
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:
a0 = m - q0k
where k is the new base, m is the integer to convert, and q0 = ceiling(m/k)-1. Note the similarity to a normal base conversion where the only difference is that q0 would be floor(m/k) or ordinary integer division. Subsequent "digits" are computed similarly, using q0 instead of m to find a1, etc.
This formula can be broken down into two cases:
This is the heart of the algorithm. For any integer m we can iteratively apply this formula until the resulting qp == 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
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 $perArr
function 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 - maxLen
function 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:
a
b
c
1
2
3
aa
ab
ac
a1
a2
a3
ba
bb
bc
b1
b2
b3
ca
cb
cc
c1
c2
c3
1a
1b
1c
11
12
13
2a
2b
2c
21
22
23
3a
3b
3c
31
32
33
aaa
aab
aac
aa1
aa2
aa3
aba
abb
abc
ab1
ab2
ab3
aca
acb
acc
ac1
ac2
ac3
a1a
a1b
a1c
a11
a12
a13
a2a
a2b
a2c
a21
a22
a23
a3a
a3b
a3c
a31
a32
a33
baa
bab
bac
ba1
ba2
ba3
bba
bbb
bbc
bb1
bb2
bb3
bca
bcb
bcc
bc1
bc2
bc3
b1a
b1b
b1c
b11
b12
b13
b2a
b2b
b2c
b21
b22
b23
b3a
b3b
b3c
b31
b32
b33
caa
cab
cac
ca1
ca2
ca3
cba
cbb
cbc
cb1
cb2
cb3
cca
ccb
ccc
cc1
cc2
cc3
c1a
c1b
c1c
c11
c12
c13
c2a
c2b
c2c
c21
c22
c23
c3a
c3b
c3c
c31
c32
c33
1aa
1ab
1ac
1a1
1a2
1a3
1ba
1bb
1bc
1b1
1b2
1b3
1ca
1cb
1cc
1c1
1c2
1c3
11a
11b
11c
111
112
113
12a
12b
12c
121
122
123
13a
13b
13c
131
132
133
2aa
2ab
2ac
2a1
2a2
2a3
2ba
2bb
2bc
2b1
2b2
2b3
2ca
2cb
2cc
2c1
2c2
2c3
21a
21b
21c
211
212
213
22a
22b
22c
221
222
223
23a
23b
23c
231
232
233
3aa
3ab
3ac
3a1
3a2
3a3
3ba
3bb
3bc
3b1
3b2
3b3
3ca
3cb
3cc
3c1
3c2
3c3
31a
31b
31c
311
312
313
32a
32b
32c
321
322
323
33a
33b
33c
331
332
333
aaaa
aaab
aaac
aaa1
aaa2
aaa3
aaba
aabb
aabc
aab1
aab2
aab3
aaca
aacb
aacc
aac1
aac2
aac3
aa1a
aa1b
aa1c
aa11
aa12
aa13
aa2a
aa2b
aa2c
aa21
aa22
aa23
aa3a
aa3b
aa3c
aa31
aa32
aa33
abaa
abab
abac
aba1
aba2
aba3
abba
abbb
abbc
abb1
abb2
abb3
abca
abcb
abcc
abc1
abc2
abc3
ab1a
ab1b
ab1c
ab11
ab12
ab13
ab2a
ab2b
ab2c
ab21
ab22
ab23
ab3a
ab3b
ab3c
ab31
ab32
ab33
acaa
acab
acac
aca1
aca2
aca3
acba
acbb
acbc
acb1
acb2
acb3
acca
accb
accc
acc1
acc2
acc3
ac1a
ac1b
ac1c
ac11
ac12
ac13
ac2a
ac2b
ac2c
ac21
ac22
ac23
ac3a
ac3b
ac3c
ac31
ac32
ac33
a1aa
a1ab
a1ac
a1a1
a1a2
a1a3
a1ba
a1bb
a1bc
a1b1
a1b2
a1b3
a1ca
a1cb
a1cc
a1c1
a1c2
a1c3
a11a
a11b
a11c
a111
a112
a113
a12a
a12b
a12c
a121
a122
a123
a13a
a13b
a13c
a131
a132
a133
a2aa
a2ab
a2ac
a2a1
a2a2
a2a3
a2ba
a2bb
a2bc
a2b1
a2b2
a2b3
a2ca
a2cb
a2cc
a2c1
a2c2
a2c3
a21a
a21b
a21c
a211
a212
a213
a22a
a22b
a22c
a221
a222
a223
a23a
a23b
a23c
a231
a232
a233
a3aa
a3ab
a3ac
a3a1
a3a2
a3a3
a3ba
a3bb
a3bc
a3b1
a3b2
a3b3
a3ca
a3cb
a3cc
a3c1
a3c2
a3c3
a31a
a31b
a31c
a311
a312
a313
a32a
a32b
a32c
a321
a322
a323
a33a
a33b
a33c
a331
a332
a333
baaa
baab
baac
baa1
baa2
baa3
baba
babb
babc
bab1
bab2
bab3
baca
bacb
bacc
bac1
bac2
bac3
ba1a
ba1b
ba1c
ba11
ba12
ba13
ba2a
ba2b
ba2c
ba21
ba22
ba23
ba3a
ba3b
ba3c
ba31
ba32
ba33
bbaa
bbab
bbac
bba1
bba2
bba3
bbba
bbbb
bbbc
bbb1
bbb2
bbb3
bbca
bbcb
bbcc
bbc1
bbc2
bbc3
bb1a
bb1b
bb1c
bb11
bb12
bb13
bb2a
bb2b
bb2c
bb21
bb22
bb23
bb3a
bb3b
bb3c
bb31
bb32
bb33
bcaa
bcab
bcac
bca1
bca2
bca3
bcba
bcbb
bcbc
bcb1
bcb2
bcb3
bcca
bccb
bccc
bcc1
bcc2
bcc3
bc1a
bc1b
bc1c
bc11
bc12
bc13
bc2a
bc2b
bc2c
bc21
bc22
bc23
bc3a
bc3b
bc3c
bc31
bc32
bc33
b1aa
b1ab
b1ac
b1a1
b1a2
b1a3
b1ba
b1bb
b1bc
b1b1
b1b2
b1b3
b1ca
b1cb
b1cc
b1c1
b1c2
b1c3
b11a
b11b
b11c
b111
b112
b113
b12a
b12b
b12c
b121
b122
b123
b13a
b13b
b13c
b131
b132
b133
b2aa
b2ab
b2ac
b2a1
b2a2
b2a3
b2ba
b2bb
b2bc
b2b1
b2b2
b2b3
b2ca
b2cb
b2cc
b2c1
b2c2
b2c3
b21a
b21b
b21c
b211
b212
b213
b22a
b22b
b22c
b221
b222
b223
b23a
b23b
b23c
b231
b232
b233
b3aa
b3ab
b3ac
b3a1
b3a2
b3a3
b3ba
b3bb
b3bc
b3b1
b3b2
b3b3
b3ca
b3cb
b3cc
b3c1
b3c2
b3c3
b31a
b31b
b31c
b311
b312
b313
b32a
b32b
b32c
b321
b322
b323
b33a
b33b
b33c
b331
b332
b333
caaa
caab
caac
caa1
caa2
caa3
caba
cabb
cabc
cab1
cab2
cab3
caca
cacb
cacc
cac1
cac2
cac3
ca1a
ca1b
ca1c
ca11
ca12
ca13
ca2a
ca2b
ca2c
ca21
ca22
ca23
ca3a
ca3b
ca3c
ca31
ca32
ca33
cbaa
cbab
cbac
cba1
cba2
cba3
cbba
cbbb
cbbc
cbb1
cbb2
cbb3
cbca
cbcb
cbcc
cbc1
cbc2
cbc3
cb1a
cb1b
cb1c
cb11
cb12
cb13
cb2a
cb2b
cb2c
cb21
cb22
cb23
cb3a
cb3b
cb3c
cb31
cb32
cb33
ccaa
ccab
ccac
cca1
cca2
cca3
ccba
ccbb
ccbc
ccb1
ccb2
ccb3
ccca
cccb
cccc
ccc1
ccc2
ccc3
cc1a
cc1b
cc1c
cc11
cc12
cc13
cc2a
cc2b
cc2c
cc21
cc22
cc23
cc3a
cc3b
cc3c
cc31
cc32
cc33
c1aa
c1ab
c1ac
c1a1
c1a2
c1a3
c1ba
c1bb
c1bc
c1b1
c1b2
c1b3
c1ca
c1cb
c1cc
c1c1
c1c2
c1c3
c11a
c11b
c11c
c111
c112
c113
c12a
c12b
c12c
c121
c122
c123
c13a
c13b
c13c
c131
c132
c133
c2aa
c2ab
c2ac
c2a1
c2a2
c2a3
c2ba
c2bb
c2bc
c2b1
c2b2
c2b3
c2ca
c2cb
c2cc
c2c1
c2c2
c2c3
c21a
c21b
c21c
c211
c212
c213
c22a
c22b
c22c
c221
c222
c223
c23a
c23b
c23c
c231
c232
c233
c3aa
c3ab
c3ac
c3a1
c3a2
c3a3
c3ba
c3bb
c3bc
c3b1
c3b2
c3b3
c3ca
c3cb
c3cc
c3c1
c3c2
c3c3
c31a
c31b
c31c
c311
c312
c313
c32a
c32b
c32c
c321
c322
c323
c33a
c33b
c33c
c331
c332
c333
1aaa
1aab
1aac
1aa1
1aa2
1aa3
1aba
1abb
1abc
1ab1
1ab2
1ab3
1aca
1acb
1acc
1ac1
1ac2
1ac3
1a1a
1a1b
1a1c
1a11
1a12
1a13
1a2a
1a2b
1a2c
1a21
1a22
1a23
1a3a
1a3b
1a3c
1a31
1a32
1a33
1baa
1bab
1bac
1ba1
1ba2
1ba3
1bba
1bbb
1bbc
1bb1
1bb2
1bb3
1bca
1bcb
1bcc
1bc1
1bc2
1bc3
1b1a
1b1b
1b1c
1b11
1b12
1b13
1b2a
1b2b
1b2c
1b21
1b22
1b23
1b3a
1b3b
1b3c
1b31
1b32
1b33
1caa
1cab
1cac
1ca1
1ca2
1ca3
1cba
1cbb
1cbc
1cb1
1cb2
1cb3
1cca
1ccb
1ccc
1cc1
1cc2
1cc3
1c1a
1c1b
1c1c
1c11
1c12
1c13
1c2a
1c2b
1c2c
1c21
1c22
1c23
1c3a
1c3b
1c3c
1c31
1c32
1c33
11aa
11ab
11ac
11a1
11a2
11a3
11ba
11bb
11bc
11b1
11b2
11b3
11ca
11cb
11cc
11c1
11c2
11c3
111a
111b
111c
1111
1112
1113
112a
112b
112c
1121
1122
1123
113a
113b
113c
1131
1132
1133
12aa
12ab
12ac
12a1
12a2
12a3
12ba
12bb
12bc
12b1
12b2
12b3
12ca
12cb
12cc
12c1
12c2
12c3
121a
121b
121c
1211
1212
1213
122a
122b
122c
1221
1222
1223
123a
123b
123c
1231
1232
1233
13aa
13ab
13ac
13a1
13a2
13a3
13ba
13bb
13bc
13b1
13b2
13b3
13ca
13cb
13cc
13c1
13c2
13c3
131a
131b
131c
1311
1312
1313
132a
132b
132c
1321
1322
1323
133a
133b
133c
1331
1332
1333
2aaa
2aab
2aac
2aa1
2aa2
2aa3
2aba
2abb
2abc
2ab1
2ab2
2ab3
2aca
2acb
2acc
2ac1
2ac2
2ac3
2a1a
2a1b
2a1c
2a11
2a12
2a13
2a2a
2a2b
2a2c
2a21
2a22
2a23
2a3a
2a3b
2a3c
2a31
2a32
2a33
2baa
2bab
2bac
2ba1
2ba2
2ba3
2bba
2bbb
2bbc
2bb1
2bb2
2bb3
2bca
2bcb
2bcc
2bc1
2bc2
2bc3
2b1a
2b1b
2b1c
2b11
2b12
2b13
2b2a
2b2b
2b2c
2b21
2b22
2b23
2b3a
2b3b
2b3c
2b31
2b32
2b33
2caa
2cab
2cac
2ca1
2ca2
2ca3
2cba
2cbb
2cbc
2cb1
2cb2
2cb3
2cca
2ccb
2ccc
2cc1
2cc2
2cc3
2c1a
2c1b
2c1c
2c11
2c12
2c13
2c2a
2c2b
2c2c
2c21
2c22
2c23
2c3a
2c3b
2c3c
2c31
2c32
2c33
21aa
21ab
21ac
21a1
21a2
21a3
21ba
21bb
21bc
21b1
21b2
21b3
21ca
21cb
21cc
21c1
21c2
21c3
211a
211b
211c
2111
2112
2113
212a
212b
212c
2121
2122
2123
213a
213b
213c
2131
2132
2133
22aa
22ab
22ac
22a1
22a2
22a3
22ba
22bb
22bc
22b1
22b2
22b3
22ca
22cb
22cc
22c1
22c2
22c3
221a
221b
221c
2211
2212
2213
222a
222b
222c
2221
2222
2223
223a
223b
223c
2231
2232
2233
23aa
23ab
23ac
23a1
23a2
23a3
23ba
23bb
23bc
23b1
23b2
23b3
23ca
23cb
23cc
23c1
23c2
23c3
231a
231b
231c
2311
2312
2313
232a
232b
232c
2321
2322
2323
233a
233b
233c
2331
2332
2333
3aaa
3aab
3aac
3aa1
3aa2
3aa3
3aba
3abb
3abc
3ab1
3ab2
3ab3
3aca
3acb
3acc
3ac1
3ac2
3ac3
3a1a
3a1b
3a1c
3a11
3a12
3a13
3a2a
3a2b
3a2c
3a21
3a22
3a23
3a3a
3a3b
3a3c
3a31
3a32
3a33
3baa
3bab
3bac
3ba1
3ba2
3ba3
3bba
3bbb
3bbc
3bb1
3bb2
3bb3
3bca
3bcb
3bcc
3bc1
3bc2
3bc3
3b1a
3b1b
3b1c
3b11
3b12
3b13
3b2a
3b2b
3b2c
3b21
3b22
3b23
3b3a
3b3b
3b3c
3b31
3b32
3b33
3caa
3cab
3cac
3ca1
3ca2
3ca3
3cba
3cbb
3cbc
3cb1
3cb2
3cb3
3cca
3ccb
3ccc
3cc1
3cc2
3cc3
3c1a
3c1b
3c1c
3c11
3c12
3c13
3c2a
3c2b
3c2c
3c21
3c22
3c23
3c3a
3c3b
3c3c
3c31
3c32
3c33
31aa
31ab
31ac
31a1
31a2
31a3
31ba
31bb
31bc
31b1
31b2
31b3
31ca
31cb
31cc
31c1
31c2
31c3
311a
311b
311c
3111
3112
3113
312a
312b
312c
3121
3122
3123
313a
313b
313c
3131
3132
3133
32aa
32ab
32ac
32a1
32a2
32a3
32ba
32bb
32bc
32b1
32b2
32b3
32ca
32cb
32cc
32c1
32c2
32c3
321a
321b
321c
3211
3212
3213
322a
322b
322c
3221
3222
3223
323a
323b
323c
3231
3232
3233
33aa
33ab
33ac
33a1
33a2
33a3
33ba
33bb
33bc
33b1
33b2
33b3
33ca
33cb
33cc
33c1
33c2
33c3
331a
331b
331c
3311
3312
3313
332a
332b
332c
3321
3322
3323
333a
333b
333c
3331
3332
3333
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:
a
aa
aaa
aab
aac
aad
aae
ab
aba
abb
abc
abd
abe
ac
aca
acb
acc
acd
ace
ad
ada
adb
adc
add
ade
ae
aea
aeb
aec
aed
aee
b
ba
baa
bab
bac
bad
bae
bb
bba
bbb
bbc
bbd
bbe
bc
bca
bcb
bcc
bcd
bce
bd
bda
bdb
bdc
bdd
bde
be
bea
beb
bec
bed
bee
c
ca
caa
cab
cac
cad
cae
cb
cba
cbb
cbc
cbd
cbe
cc
cca
ccb
ccc
ccd
cce
cd
cda
cdb
cdc
cdd
cde
ce
cea
ceb
cec
ced
cee
d
da
daa
dab
dac
dad
dae
db
dba
dbb
dbc
dbd
dbe
dc
dca
dcb
dcc
dcd
dce
dd
dda
ddb
ddc
ddd
dde
de
dea
deb
dec
ded
dee
e
ea
eaa
eab
eac
ead
eae
eb
eba
ebb
ebc
ebd
ebe
ec
eca
ecb
ecc
ecd
ece
ed
eda
edb
edc
edd
ede
ee
eea
eeb
eec
eed
eee
One thing that is for sure is that what ever the algo use for this , the best time complexity for generation of all the numbers is around O((n^m+1)/(n-1)) (Assuming that you are not using any paralleled programming . ) . (Where n is size of array , m is max length .)
For which any of the above stated algo suits better .
Solution
function combinationsByLenth($arr, $len) {
$combinations = [];
$select = array_fill(0, $len, 0);
$selectCount = count($select);
$arrCount = count($arr);
$possibleCombinations = pow($arrCount, $selectCount);
while ($possibleCombinations-- > 0) {
$combination = '';
foreach ($select as $index) {
$combination .= $arr[$index];
}
$combinations[] = $combination;
for ($i = $selectCount - 1; $i >= 0; $i--) {
if ($select[$i] !== ($arrCount - 1)) {
$select[$i]++;
break;
} else {
$select[$i] = 0;
}
}
}
return $combinations;
}
function combinationsByMinMax($arr, $min, $max) {
$combinations = [];
for ($i = $min; $i <= $max; $i++) {
$combinations = array_merge($combinations, combinationsByLenth($arr, $i));
}
return $combinations;
}
print_r(combinationsByMinMax($arr, 1, 5));
Output
Array
(
[0] => a
[1] => b
[2] => c
[3] => 1
[4] => 2
[5] => 3
[6] => aa
[7] => ab
[8] => ac
[9] => a1
...
[9320] => 3332c
[9321] => 33321
[9322] => 33322
[9323] => 33323
[9324] => 3333a
[9325] => 3333b
[9326] => 3333c
[9327] => 33331
[9328] => 33332
[9329] => 33333
)
Rationale
How I Developed This Solution
I started out with a function that handled the specific case of combinations of length 5, refactored to generalize the algorithm, refactored to generalize the algorithm, etc. I've put up a quick gist so you can see the iterations to get to this working version as a case study of how to approach building this type of algorithm:
A non recursive PHP solution based on the simple counting algorithm, with as many possible digits as the $letters array has elements. So for an array of 5 elements, having max length as 3, the counting array has 1 (first) to 3 (end) elements, like
0, 1, ..., 4 then
00, 01, ..., 04, 10, ... 14, ... 44
When 00 is array(0,0) (actually to optimize the loop the counting goes like 00, 10, 20, ..., 34, 44)
Then the string is built from that 'counting' array.
<?php
function andcounting($letters, $len) {
$lastindex = count($letters) - 1;
$n = array(0); // counting array
while(true) {
// display current result
for ($i=count($n)-1 ; $i>=0 ; $i--) echo $letters[$n[$i]];
echo "\n";
// increment $n
for ($i=count($n)-1 ; $i>=0 ; $i--) {
if (++$n[$i] <= $lastindex) break;
$n[$i] = 0;
}
// check if need to add a dim (or exit)
if ($i < 0) {
if (count($n) == $len) break;
$n[] = 0;
}
}
}
Running the function
andcounting( array('a','b','c','d','e'), 3);
that gives (left to right and top to bottom)
a b c d e aa ba ca da ea ab bb cb db eb ac bc cc dc ec
ad bd cd dd ed ae be ce de ee aaa baa caa daa eaa aba bba cba dba eba
aca bca cca dca eca ada bda cda dda eda aea bea cea dea eea aab bab cab dab eab
abb bbb cbb dbb ebb acb bcb ccb dcb ecb adb bdb cdb ddb edb aeb beb ceb deb eeb
aac bac cac dac eac abc bbc cbc dbc ebc acc bcc ccc dcc ecc adc bdc cdc ddc edc
aec bec cec dec eec aad bad cad dad ead abd bbd cbd dbd ebd acd bcd ccd dcd ecd
add bdd cdd ddd edd aed bed ced ded eed aae bae cae dae eae abe bbe cbe dbe ebe
ace bce cce dce ece ade bde cde dde ede aee bee cee dee eee
Accumulative set product for k times with a set S which is empty initially will produce all permutations up to k-long, with n = |S| ..
Time: O(kn^2)
Space: O(kn^2)
// Enumerate all permutations, PHP
// by Khaled A Khunaifer, 25/3/2013
function setProduct($a, $b)
{
$arr = array();
foreach ($a as $s)
{
foreach ($b as $t)
{
$arr[] = $s . $t;
}
}
return $arr;
}
function enumerate ($arrary, $maxLen)
{
$enumeration = array();
for (var $i = 1; $i <= $maxLen; $i++)
{
$enumeration += setProduct($enumeration, $array);
}
}
This is a different language, but is this the results that you are looking for in the end?
>>> import itertools
>>> def my_combinations(string, max_length):
for repeat in range(1, max_length + 1):
for result in itertools.product(string, repeat=repeat):
yield ''.join(result)
>>> print(*my_combinations('abc123', 4), sep='\n')
a
b
c
1
2
3
aa
ab
ac
a1
a2
a3
ba
bb
bc
b1
b2
b3
ca
cb
cc
c1
c2
c3
1a
1b
1c
11
12
13
2a
2b
2c
21
22
23
3a
3b
3c
31
32
33
aaa
aab
aac
aa1
aa2
aa3
aba
abb
abc
ab1
ab2
ab3
aca
acb
acc
ac1
ac2
ac3
a1a
a1b
a1c
a11
a12
a13
a2a
a2b
a2c
a21
a22
a23
a3a
a3b
a3c
a31
a32
a33
baa
bab
bac
ba1
ba2
ba3
bba
bbb
bbc
bb1
bb2
bb3
bca
bcb
bcc
bc1
bc2
bc3
b1a
b1b
b1c
b11
b12
b13
b2a
b2b
b2c
b21
b22
b23
b3a
b3b
b3c
b31
b32
b33
caa
cab
cac
ca1
ca2
ca3
cba
cbb
cbc
cb1
cb2
cb3
cca
ccb
ccc
cc1
cc2
cc3
c1a
c1b
c1c
c11
c12
c13
c2a
c2b
c2c
c21
c22
c23
c3a
c3b
c3c
c31
c32
c33
1aa
1ab
1ac
1a1
1a2
1a3
1ba
1bb
1bc
1b1
1b2
1b3
1ca
1cb
1cc
1c1
1c2
1c3
11a
11b
11c
111
112
113
12a
12b
12c
121
122
123
13a
13b
13c
131
132
133
2aa
2ab
2ac
2a1
2a2
2a3
2ba
2bb
2bc
2b1
2b2
2b3
2ca
2cb
2cc
2c1
2c2
2c3
21a
21b
21c
211
212
213
22a
22b
22c
221
222
223
23a
23b
23c
231
232
233
3aa
3ab
3ac
3a1
3a2
3a3
3ba
3bb
3bc
3b1
3b2
3b3
3ca
3cb
3cc
3c1
3c2
3c3
31a
31b
31c
311
312
313
32a
32b
32c
321
322
323
33a
33b
33c
331
332
333
aaaa
aaab
aaac
aaa1
aaa2
aaa3
aaba
aabb
aabc
aab1
aab2
aab3
aaca
aacb
aacc
aac1
aac2
aac3
aa1a
aa1b
aa1c
aa11
aa12
aa13
aa2a
aa2b
aa2c
aa21
aa22
aa23
aa3a
aa3b
aa3c
aa31
aa32
aa33
abaa
abab
abac
aba1
aba2
aba3
abba
abbb
abbc
abb1
abb2
abb3
abca
abcb
abcc
abc1
abc2
abc3
ab1a
ab1b
ab1c
ab11
ab12
ab13
ab2a
ab2b
ab2c
ab21
ab22
ab23
ab3a
ab3b
ab3c
ab31
ab32
ab33
acaa
acab
acac
aca1
aca2
aca3
acba
acbb
acbc
acb1
acb2
acb3
acca
accb
accc
acc1
acc2
acc3
ac1a
ac1b
ac1c
ac11
ac12
ac13
ac2a
ac2b
ac2c
ac21
ac22
ac23
ac3a
ac3b
ac3c
ac31
ac32
ac33
a1aa
a1ab
a1ac
a1a1
a1a2
a1a3
a1ba
a1bb
a1bc
a1b1
a1b2
a1b3
a1ca
a1cb
a1cc
a1c1
a1c2
a1c3
a11a
a11b
a11c
a111
a112
a113
a12a
a12b
a12c
a121
a122
a123
a13a
a13b
a13c
a131
a132
a133
a2aa
a2ab
a2ac
a2a1
a2a2
a2a3
a2ba
a2bb
a2bc
a2b1
a2b2
a2b3
a2ca
a2cb
a2cc
a2c1
a2c2
a2c3
a21a
a21b
a21c
a211
a212
a213
a22a
a22b
a22c
a221
a222
a223
a23a
a23b
a23c
a231
a232
a233
a3aa
a3ab
a3ac
a3a1
a3a2
a3a3
a3ba
a3bb
a3bc
a3b1
a3b2
a3b3
a3ca
a3cb
a3cc
a3c1
a3c2
a3c3
a31a
a31b
a31c
a311
a312
a313
a32a
a32b
a32c
a321
a322
a323
a33a
a33b
a33c
a331
a332
a333
baaa
baab
baac
baa1
baa2
baa3
baba
babb
babc
bab1
bab2
bab3
baca
bacb
bacc
bac1
bac2
bac3
ba1a
ba1b
ba1c
ba11
ba12
ba13
ba2a
ba2b
ba2c
ba21
ba22
ba23
ba3a
ba3b
ba3c
ba31
ba32
ba33
bbaa
bbab
bbac
bba1
bba2
bba3
bbba
bbbb
bbbc
bbb1
bbb2
bbb3
bbca
bbcb
bbcc
bbc1
bbc2
bbc3
bb1a
bb1b
bb1c
bb11
bb12
bb13
bb2a
bb2b
bb2c
bb21
bb22
bb23
bb3a
bb3b
bb3c
bb31
bb32
bb33
bcaa
bcab
bcac
bca1
bca2
bca3
bcba
bcbb
bcbc
bcb1
bcb2
bcb3
bcca
bccb
bccc
bcc1
bcc2
bcc3
bc1a
bc1b
bc1c
bc11
bc12
bc13
bc2a
bc2b
bc2c
bc21
bc22
bc23
bc3a
bc3b
bc3c
bc31
bc32
bc33
b1aa
b1ab
b1ac
b1a1
b1a2
b1a3
b1ba
b1bb
b1bc
b1b1
b1b2
b1b3
b1ca
b1cb
b1cc
b1c1
b1c2
b1c3
b11a
b11b
b11c
b111
b112
b113
b12a
b12b
b12c
b121
b122
b123
b13a
b13b
b13c
b131
b132
b133
b2aa
b2ab
b2ac
b2a1
b2a2
b2a3
b2ba
b2bb
b2bc
b2b1
b2b2
b2b3
b2ca
b2cb
b2cc
b2c1
b2c2
b2c3
b21a
b21b
b21c
b211
b212
b213
b22a
b22b
b22c
b221
b222
b223
b23a
b23b
b23c
b231
b232
b233
b3aa
b3ab
b3ac
b3a1
b3a2
b3a3
b3ba
b3bb
b3bc
b3b1
b3b2
b3b3
b3ca
b3cb
b3cc
b3c1
b3c2
b3c3
b31a
b31b
b31c
b311
b312
b313
b32a
b32b
b32c
b321
b322
b323
b33a
b33b
b33c
b331
b332
b333
caaa
caab
caac
caa1
caa2
caa3
caba
cabb
cabc
cab1
cab2
cab3
caca
cacb
cacc
cac1
cac2
cac3
ca1a
ca1b
ca1c
ca11
ca12
ca13
ca2a
ca2b
ca2c
ca21
ca22
ca23
ca3a
ca3b
ca3c
ca31
ca32
ca33
cbaa
cbab
cbac
cba1
cba2
cba3
cbba
cbbb
cbbc
cbb1
cbb2
cbb3
cbca
cbcb
cbcc
cbc1
cbc2
cbc3
cb1a
cb1b
cb1c
cb11
cb12
cb13
cb2a
cb2b
cb2c
cb21
cb22
cb23
cb3a
cb3b
cb3c
cb31
cb32
cb33
ccaa
ccab
ccac
cca1
cca2
cca3
ccba
ccbb
ccbc
ccb1
ccb2
ccb3
ccca
cccb
cccc
ccc1
ccc2
ccc3
cc1a
cc1b
cc1c
cc11
cc12
cc13
cc2a
cc2b
cc2c
cc21
cc22
cc23
cc3a
cc3b
cc3c
cc31
cc32
cc33
c1aa
c1ab
c1ac
c1a1
c1a2
c1a3
c1ba
c1bb
c1bc
c1b1
c1b2
c1b3
c1ca
c1cb
c1cc
c1c1
c1c2
c1c3
c11a
c11b
c11c
c111
c112
c113
c12a
c12b
c12c
c121
c122
c123
c13a
c13b
c13c
c131
c132
c133
c2aa
c2ab
c2ac
c2a1
c2a2
c2a3
c2ba
c2bb
c2bc
c2b1
c2b2
c2b3
c2ca
c2cb
c2cc
c2c1
c2c2
c2c3
c21a
c21b
c21c
c211
c212
c213
c22a
c22b
c22c
c221
c222
c223
c23a
c23b
c23c
c231
c232
c233
c3aa
c3ab
c3ac
c3a1
c3a2
c3a3
c3ba
c3bb
c3bc
c3b1
c3b2
c3b3
c3ca
c3cb
c3cc
c3c1
c3c2
c3c3
c31a
c31b
c31c
c311
c312
c313
c32a
c32b
c32c
c321
c322
c323
c33a
c33b
c33c
c331
c332
c333
1aaa
1aab
1aac
1aa1
1aa2
1aa3
1aba
1abb
1abc
1ab1
1ab2
1ab3
1aca
1acb
1acc
1ac1
1ac2
1ac3
1a1a
1a1b
1a1c
1a11
1a12
1a13
1a2a
1a2b
1a2c
1a21
1a22
1a23
1a3a
1a3b
1a3c
1a31
1a32
1a33
1baa
1bab
1bac
1ba1
1ba2
1ba3
1bba
1bbb
1bbc
1bb1
1bb2
1bb3
1bca
1bcb
1bcc
1bc1
1bc2
1bc3
1b1a
1b1b
1b1c
1b11
1b12
1b13
1b2a
1b2b
1b2c
1b21
1b22
1b23
1b3a
1b3b
1b3c
1b31
1b32
1b33
1caa
1cab
1cac
1ca1
1ca2
1ca3
1cba
1cbb
1cbc
1cb1
1cb2
1cb3
1cca
1ccb
1ccc
1cc1
1cc2
1cc3
1c1a
1c1b
1c1c
1c11
1c12
1c13
1c2a
1c2b
1c2c
1c21
1c22
1c23
1c3a
1c3b
1c3c
1c31
1c32
1c33
11aa
11ab
11ac
11a1
11a2
11a3
11ba
11bb
11bc
11b1
11b2
11b3
11ca
11cb
11cc
11c1
11c2
11c3
111a
111b
111c
1111
1112
1113
112a
112b
112c
1121
1122
1123
113a
113b
113c
1131
1132
1133
12aa
12ab
12ac
12a1
12a2
12a3
12ba
12bb
12bc
12b1
12b2
12b3
12ca
12cb
12cc
12c1
12c2
12c3
121a
121b
121c
1211
1212
1213
122a
122b
122c
1221
1222
1223
123a
123b
123c
1231
1232
1233
13aa
13ab
13ac
13a1
13a2
13a3
13ba
13bb
13bc
13b1
13b2
13b3
13ca
13cb
13cc
13c1
13c2
13c3
131a
131b
131c
1311
1312
1313
132a
132b
132c
1321
1322
1323
133a
133b
133c
1331
1332
1333
2aaa
2aab
2aac
2aa1
2aa2
2aa3
2aba
2abb
2abc
2ab1
2ab2
2ab3
2aca
2acb
2acc
2ac1
2ac2
2ac3
2a1a
2a1b
2a1c
2a11
2a12
2a13
2a2a
2a2b
2a2c
2a21
2a22
2a23
2a3a
2a3b
2a3c
2a31
2a32
2a33
2baa
2bab
2bac
2ba1
2ba2
2ba3
2bba
2bbb
2bbc
2bb1
2bb2
2bb3
2bca
2bcb
2bcc
2bc1
2bc2
2bc3
2b1a
2b1b
2b1c
2b11
2b12
2b13
2b2a
2b2b
2b2c
2b21
2b22
2b23
2b3a
2b3b
2b3c
2b31
2b32
2b33
2caa
2cab
2cac
2ca1
2ca2
2ca3
2cba
2cbb
2cbc
2cb1
2cb2
2cb3
2cca
2ccb
2ccc
2cc1
2cc2
2cc3
2c1a
2c1b
2c1c
2c11
2c12
2c13
2c2a
2c2b
2c2c
2c21
2c22
2c23
2c3a
2c3b
2c3c
2c31
2c32
2c33
21aa
21ab
21ac
21a1
21a2
21a3
21ba
21bb
21bc
21b1
21b2
21b3
21ca
21cb
21cc
21c1
21c2
21c3
211a
211b
211c
2111
2112
2113
212a
212b
212c
2121
2122
2123
213a
213b
213c
2131
2132
2133
22aa
22ab
22ac
22a1
22a2
22a3
22ba
22bb
22bc
22b1
22b2
22b3
22ca
22cb
22cc
22c1
22c2
22c3
221a
221b
221c
2211
2212
2213
222a
222b
222c
2221
2222
2223
223a
223b
223c
2231
2232
2233
23aa
23ab
23ac
23a1
23a2
23a3
23ba
23bb
23bc
23b1
23b2
23b3
23ca
23cb
23cc
23c1
23c2
23c3
231a
231b
231c
2311
2312
2313
232a
232b
232c
2321
2322
2323
233a
233b
233c
2331
2332
2333
3aaa
3aab
3aac
3aa1
3aa2
3aa3
3aba
3abb
3abc
3ab1
3ab2
3ab3
3aca
3acb
3acc
3ac1
3ac2
3ac3
3a1a
3a1b
3a1c
3a11
3a12
3a13
3a2a
3a2b
3a2c
3a21
3a22
3a23
3a3a
3a3b
3a3c
3a31
3a32
3a33
3baa
3bab
3bac
3ba1
3ba2
3ba3
3bba
3bbb
3bbc
3bb1
3bb2
3bb3
3bca
3bcb
3bcc
3bc1
3bc2
3bc3
3b1a
3b1b
3b1c
3b11
3b12
3b13
3b2a
3b2b
3b2c
3b21
3b22
3b23
3b3a
3b3b
3b3c
3b31
3b32
3b33
3caa
3cab
3cac
3ca1
3ca2
3ca3
3cba
3cbb
3cbc
3cb1
3cb2
3cb3
3cca
3ccb
3ccc
3cc1
3cc2
3cc3
3c1a
3c1b
3c1c
3c11
3c12
3c13
3c2a
3c2b
3c2c
3c21
3c22
3c23
3c3a
3c3b
3c3c
3c31
3c32
3c33
31aa
31ab
31ac
31a1
31a2
31a3
31ba
31bb
31bc
31b1
31b2
31b3
31ca
31cb
31cc
31c1
31c2
31c3
311a
311b
311c
3111
3112
3113
312a
312b
312c
3121
3122
3123
313a
313b
313c
3131
3132
3133
32aa
32ab
32ac
32a1
32a2
32a3
32ba
32bb
32bc
32b1
32b2
32b3
32ca
32cb
32cc
32c1
32c2
32c3
321a
321b
321c
3211
3212
3213
322a
322b
322c
3221
3222
3223
323a
323b
323c
3231
3232
3233
33aa
33ab
33ac
33a1
33a2
33a3
33ba
33bb
33bc
33b1
33b2
33b3
33ca
33cb
33cc
33c1
33c2
33c3
331a
331b
331c
3311
3312
3313
332a
332b
332c
3321
3322
3323
333a
333b
333c
3331
3332
3333
>>>
It is more peace of code than Algorithm :) but it works! I found it usefull to have sequence iterator.
$characters = implode('', $letters_array); // string as character set
$seq = new Sequence($characters, $min_length, $max_length);
while (($s = $seq->fetch()) !== false) {
echo $s . "\n";
}
This is a class:
<?php
class Sequence
{
private $_set, $_min, $_max;
private $_string;
public function __construct($set, $min, $max)
{
$this->_set = $set;
$this->_min = $min;
$this->_max = $max;
$this->_string = str_repeat($set{0}, $min);
}
public function fetch()
{
// get current value and calculate next one
$result = $this->_string;
// while current value is not "finish mark"
if ($this->_string !== false) {
$l = strlen($this->_string);
// move from left to right and try to "increment" characters
for ($p = 0; $p < $l; ++$p) {
$c = $this->_string{$p};
$i = strpos($this->_set, $c);
if ($i < strlen($this->_set) - 1) {
$this->_string{$p} = $this->_set{++$i};
break;
}
// we've try all characters here, drop this and go to the next one
$this->_string{$p} = $this->_set{0};
}
// if string is ended (cycle not breaked)
if ($p == $l) {
// $l is new string length. if it's too long, make "finish mark"
if ($l > $this->_max)
$this->_string = false;
else
$this->_string .= $this->_set{0};
}
}
return $result;
}
}
Result is
a
b
c
1
2
3
aa
ba
...
23333
33333
Here is a simple solution
Assumption:
$source = array(
'a',
'b',
'c',
'1',
'2',
'3'
);
Example 1
$c = new FindCombination($source);
echo $c->find(4,true); //returns all resul in json
echo count($c), PHP_EOL; //returns total
Example 2
If you want it sorted use
echo $c->find(4,true);
Output
[
"1",
"2",
"3",
"a",
"b",
"c",
"12",
"13",
"1a",
"1b",
"1c",
"21",
"23",
"2a",
"2b",
"2c",
"31",
"32",
"3a",
"3b",
"3c",
"a1",
"a2",
"a3",
"ab",
"ac",
"b1",
"b2",
"b3",
"ba",
"bc",
"c1",
"c2",
"c3",
"ca",
"cb",
"123",
"12a",
"12b",
"12c",
"132",
"13a",
"13b",
"13c",
"1a2",
"1a3",
"1ab",
"1ac",
"1b2",
"1b3",
"1ba",
"1bc",
"1c2",
"1c3",
"1ca",
"1cb",
"213",
"21a",
"21b",
"21c",
"231",
"23a",
"23b",
"23c",
"2a1",
"2a3",
"2ab",
"2ac",
"2b1",
"2b3",
"2ba",
"2bc",
"2c1",
"2c3",
"2ca",
"2cb",
"312",
"31a",
"31b",
"31c",
"321",
"32a",
"32b",
"32c",
"3a1",
"3a2",
"3ab",
"3ac",
"3b1",
"3b2",
"3ba",
"3bc",
"3c1",
"3c2",
"3ca",
"3cb",
"a12",
"a13",
"a1b",
"a1c",
"a21",
"a23",
"a2b",
"a2c",
"a31",
"a32",
"a3b",
"a3c",
"ab1",
"ab2",
"ab3",
"abc",
"ac1",
"ac2",
"ac3",
"acb",
"b12",
"b13",
"b1a",
"b1c",
"b21",
"b23",
"b2a",
"b2c",
"b31",
"b32",
"b3a",
"b3c",
"ba1",
"ba2",
"ba3",
"bac",
"bc1",
"bc2",
"bc3",
"bca",
"c12",
"c13",
"c1a",
"c1b",
"c21",
"c23",
"c2a",
"c2b",
"c31",
"c32",
"c3a",
"c3b",
"ca1",
"ca2",
"ca3",
"cab",
"cb1",
"cb2",
"cb3",
"cba",
"123a",
"123b",
"123c",
"12a3",
"12ab",
"12ac",
"12b3",
"12ba",
"12bc",
"12c3",
"12ca",
"12cb",
"132a",
"132b",
"132c",
"13a2",
"13ab",
"13ac",
"13b2",
"13ba",
"13bc",
"13c2",
"13ca",
"13cb",
"1a23",
"1a2b",
"1a2c",
"1a32",
"1a3b",
"1a3c",
"1ab2",
"1ab3",
"1abc",
"1ac2",
"1ac3",
"1acb",
"1b23",
"1b2a",
"1b2c",
"1b32",
"1b3a",
"1b3c",
"1ba2",
"1ba3",
"1bac",
"1bc2",
"1bc3",
"1bca",
"1c23",
"1c2a",
"1c2b",
"1c32",
"1c3a",
"1c3b",
"1ca2",
"1ca3",
"1cab",
"1cb2",
"1cb3",
"1cba",
"213a",
"213b",
"213c",
"21a3",
"21ab",
"21ac",
"21b3",
"21ba",
"21bc",
"21c3",
"21ca",
"21cb",
"231a",
"231b",
"231c",
"23a1",
"23ab",
"23ac",
"23b1",
"23ba",
"23bc",
"23c1",
"23ca",
"23cb",
"2a13",
"2a1b",
"2a1c",
"2a31",
"2a3b",
"2a3c",
"2ab1",
"2ab3",
"2abc",
"2ac1",
"2ac3",
"2acb",
"2b13",
"2b1a",
"2b1c",
"2b31",
"2b3a",
"2b3c",
"2ba1",
"2ba3",
"2bac",
"2bc1",
"2bc3",
"2bca",
"2c13",
"2c1a",
"2c1b",
"2c31",
"2c3a",
"2c3b",
"2ca1",
"2ca3",
"2cab",
"2cb1",
"2cb3",
"2cba",
"312a",
"312b",
"312c",
"31a2",
"31ab",
"31ac",
"31b2",
"31ba",
"31bc",
"31c2",
"31ca",
"31cb",
"321a",
"321b",
"321c",
"32a1",
"32ab",
"32ac",
"32b1",
"32ba",
"32bc",
"32c1",
"32ca",
"32cb",
"3a12",
"3a1b",
"3a1c",
"3a21",
"3a2b",
"3a2c",
"3ab1",
"3ab2",
"3abc",
"3ac1",
"3ac2",
"3acb",
"3b12",
"3b1a",
"3b1c",
"3b21",
"3b2a",
"3b2c",
"3ba1",
"3ba2",
"3bac",
"3bc1",
"3bc2",
"3bca",
"3c12",
"3c1a",
"3c1b",
"3c21",
"3c2a",
"3c2b",
"3ca1",
"3ca2",
"3cab",
"3cb1",
"3cb2",
"3cba",
"a123",
"a12b",
"a12c",
"a132",
"a13b",
"a13c",
"a1b2",
"a1b3",
"a1bc",
"a1c2",
"a1c3",
"a1cb",
"a213",
"a21b",
"a21c",
"a231",
"a23b",
"a23c",
"a2b1",
"a2b3",
"a2bc",
"a2c1",
"a2c3",
"a2cb",
"a312",
"a31b",
"a31c",
"a321",
"a32b",
"a32c",
"a3b1",
"a3b2",
"a3bc",
"a3c1",
"a3c2",
"a3cb",
"ab12",
"ab13",
"ab1c",
"ab21",
"ab23",
"ab2c",
"ab31",
"ab32",
"ab3c",
"abc1",
"abc2",
"abc3",
"ac12",
"ac13",
"ac1b",
"ac21",
"ac23",
"ac2b",
"ac31",
"ac32",
"ac3b",
"acb1",
"acb2",
"acb3",
"b123",
"b12a",
"b12c",
"b132",
"b13a",
"b13c",
"b1a2",
"b1a3",
"b1ac",
"b1c2",
"b1c3",
"b1ca",
"b213",
"b21a",
"b21c",
"b231",
"b23a",
"b23c",
"b2a1",
"b2a3",
"b2ac",
"b2c1",
"b2c3",
"b2ca",
"b312",
"b31a",
"b31c",
"b321",
"b32a",
"b32c",
"b3a1",
"b3a2",
"b3ac",
"b3c1",
"b3c2",
"b3ca",
"ba12",
"ba13",
"ba1c",
"ba21",
"ba23",
"ba2c",
"ba31",
"ba32",
"ba3c",
"bac1",
"bac2",
"bac3",
"bc12",
"bc13",
"bc1a",
"bc21",
"bc23",
"bc2a",
"bc31",
"bc32",
"bc3a",
"bca1",
"bca2",
"bca3",
"c123",
"c12a",
"c12b",
"c132",
"c13a",
"c13b",
"c1a2",
"c1a3",
"c1ab",
"c1b2",
"c1b3",
"c1ba",
"c213",
"c21a",
"c21b",
"c231",
"c23a",
"c23b",
"c2a1",
"c2a3",
"c2ab",
"c2b1",
"c2b3",
"c2ba",
"c312",
"c31a",
"c31b",
"c321",
"c32a",
"c32b",
"c3a1",
"c3a2",
"c3ab",
"c3b1",
"c3b2",
"c3ba",
"ca12",
"ca13",
"ca1b",
"ca21",
"ca23",
"ca2b",
"ca31",
"ca32",
"ca3b",
"cab1",
"cab2",
"cab3",
"cb12",
"cb13",
"cb1a",
"cb21",
"cb23",
"cb2a",
"cb31",
"cb32",
"cb3a",
"cba1",
"cba2",
"cba3"
]
Example 3
You can loop through the result
$c = new FindCombination($source);
foreach ( $c->find(4, true) as $v ) {
echo $v . "|";
}
Class Used
class FindCombination implements IteratorAggregate, JsonSerializable, Countable {
private $source;
private $sink = array();
private $max = 0;
function __construct(&$source) {
$this->source = $source;
}
public function jsonSerialize() {
return json_encode($this->sink, 128);
}
public function getIterator() {
return new ArrayIterator($this->sink);
}
public function count() {
return count($this->sink);
}
public function __toString() {
return $this->jsonSerialize();
}
public function find($max = 0, $sort = false) {
$this->sink = array(); // reset sink
$this->max = $max;
$this->parse($this->source);
if ($sort) {
usort($this->sink, function ($a, $b) {
$al = strlen($a);
$bl = strlen($b);
return $al == $bl ? strcmp($a, $b) : strcmp($al, $bl);
});
}
return $this;
}
private function parse($source, $tempString = "") {
if ($tempString != "")
$this->sink[] = $tempString;
for($i = 0; $i < count($source); $i ++) {
$copy = $source;
$elem = array_splice($copy, $i, 1);
$tempModified = $tempString . $elem[0];
if (strlen($tempModified) > $this->max && $this->max > 0)
continue;
if (count($copy) > 0) {
$this->parse($copy, $tempModified);
} else {
$this->sink[] = $tempModified;
}
}
}
}
I suggest you find an implementation of pythons itertools.product feature in php. (or just copy the implementation yourself).
The following code gets all permutations of the specified length. You would want lengths 1, 2, 3, 4.
The final concern is that there are no duplicate characters, so you could add "letters = set(letters)" just to make sure.
>>> letters = "abc123"
>>> length = 3
>>> from itertools import product
>>> dimensions = [letters]*length
>>> for point in product(*dimensions):
... print "".join(point)
...
aaa
aab
aac
aa1
aa2
aa3
aba
abb
abc
ab1
ab2
ab3
aca
acb
acc
ac1
ac2
ac3
a1a
a1b
a1c
a11
a12
a13
a2a
a2b
a2c
a21
a22
a23
a3a
a3b
a3c
a31
a32
a33
baa
bab
bac
ba1
ba2
ba3
bba
bbb
bbc
bb1
bb2
bb3
bca
bcb
bcc
bc1
bc2
bc3
b1a
b1b
b1c
b11
b12
b13
b2a
b2b
b2c
b21
b22
b23
b3a
b3b
b3c
b31
b32
b33
caa
cab
cac
ca1
ca2
ca3
cba
cbb
cbc
cb1
cb2
cb3
cca
ccb
ccc
cc1
cc2
cc3
c1a
c1b
c1c
c11
c12
c13
c2a
c2b
c2c
c21
c22
c23
c3a
c3b
c3c
c31
c32
c33
1aa
1ab
1ac
1a1
1a2
1a3
1ba
1bb
1bc
1b1
1b2
1b3
1ca
1cb
1cc
1c1
1c2
1c3
11a
11b
11c
111
112
113
12a
12b
12c
121
122
123
13a
13b
13c
131
132
133
2aa
2ab
2ac
2a1
2a2
2a3
2ba
2bb
2bc
2b1
2b2
2b3
2ca
2cb
2cc
2c1
2c2
2c3
21a
21b
21c
211
212
213
22a
22b
22c
221
222
223
23a
23b
23c
231
232
233
3aa
3ab
3ac
3a1
3a2
3a3
3ba
3bb
3bc
3b1
3b2
3b3
3ca
3cb
3cc
3c1
3c2
3c3
31a
31b
31c
311
312
313
32a
32b
32c
321
322
323
33a
33b
33c
331
332
333
Algorithm to get all possible string combinations from array up to certain length.
The algorithm is based on finding the Power set of indexes, which is in turn based on finding all the combinations (without repetition) of indexes with size: 1, 2,..., n.
As my skills in your language of preference "tend to zero", here is a C# implementation that could be used as a benchmark:
using System;
namespace Combinatorics
{
class StringPowerSet
{
static string[] set = { "a", "b", "c" };
static int[] subSetIndexes;
//-------------------------------------------------------------
static void Main(string[] args)
{
PrintSet(set, "Initial set");
FindPowerSet(set.Length);
}
//-------------------------------------------------------------
private static void FindPowerSet(int n)
{
// Super set - all sets with size: 0, 1, ..., n - 1
for (int k = 0; k <= n - 1; k++)
{
subSetIndexes = new int[k];
CombinationsNoRepetition(k, 0, n - 1);
}
}
//-------------------------------------------------------------
private static void CombinationsNoRepetition(int k, int iBegin, int iEnd)
{
if (k == 0)
{
PrintSubSet();
return;
}
for (int i = iBegin; i <= iEnd; i++)
{
subSetIndexes[k - 1] = i;
++iBegin;
CombinationsNoRepetition(k - 1, iBegin, iEnd);
}
}
}
}
Here are the helper print functions:
//-------------------------------------------------------------
private static void PrintSubSet()
{
Console.Write("(");
for (int i = subSetIndexes.Length - 1; i >= 0; i--)
{
Console.Write(set[subSetIndexes[i]]);
if (i > 0)
{
Console.Write(" ,");
}
}
Console.WriteLine(")");
}
//-------------------------------------------------------------
private static void PrintSet(string[] arr, string label = "")
{
Console.WriteLine(label);
Console.Write("(");
for (int i = 0; i < arr.Length; i++)
{
Console.Write(arr[i]);
if (i < arr.Length - 1)
{
Console.Write(" ,");
}
}
Console.WriteLine(")");
}
Input:
{a, b, c}
Output:
() (a) (b) (c) (a, b) (a, c) (b, c)
Variables k and n in the call of function CombinationsNoRepetition determine the length of the first set and the last sets, i.e. there are your min and max.
