从具有最小和最大长度值的给定数组中获取所有可能的字符串组合的最佳算法是什么。
注意：这增加了复杂性，因为与这些链接到的问题不同，该值是可变的。
例如：
$letters = array('a','b','c','1','2','3');
$min_length = 1;
$max_length = 4;
a
b
c
1
2
3
.
.
.
aaaa
a123
b123
c123
问问题
11485 次
12 回答
25
几乎是基本转换
这个解决方案的动机是观察到，如果不是因为在有效组合的高位位置重复数组索引 0 处的字符的可能性，这个问题将只是从十进制到新基的基转换从 0 到 (base^length)-1 的所有整数。所以，
0 = a
1 = b
...
1294 = 3332
1295 = 3333
困难在于这会错过与一个或多个前导“a”的组合，例如：
aa
...
a1
aa1
aaa1
这些是唯一缺少的解决方案。因此，可以简单地，对于每个生成的长度小于 max_length 的组合，将“a”（或字母 [0] 处的任何内容）添加到字符串的前面，并输出该字符串，如有必要，重复。所以如果你生成字符串'b'，你会输出：
b
ab
aab
aaab
这行得通，但并不令人满意，首先是因为它看起来像一个杂乱无章的解决方案。其次，它不会按字典顺序生成解决方案，这可能是也可能不是问题。第三，如果生成组合的函数是双射的，那就太好了，这样我们就可以知道任何给定十进制整数的唯一组合以及任何组合的唯一索引。这将是关键时刻。
想象一下没有零
如果零索引给我们带来了问题，那么为什么不取消它呢？假设我们将数组更改为：
字母 = {∅,'a','b','c','1','2','3'}
其中 ∅ 是一个永远不会使用的任意占位符。我们现在将尝试在不使用数字零的情况下以新的基数表示从 1 到 base^max_length 的十进制整数（在这种情况下仍然是 6，而不是 7）。我们将把从 1 到 base-1 的数字表示为正常的 (1, 2, 3, ...)，但是当我们得到等于底数的数字时，而不是将其表示为 10，我们将其表示为基数（例如，以 6 为基数的 6 而不是 10）。下一个数字 base+1 将是 11，然后是 12 到 16（等于十进制的 12），然后是 21。每个数字
一个n ,一个n-1 ,...,一个1 ,一个0
在新的基础上等于
a n *b n +a n-1 *b n-1 +...+a 1 *b 1 +a 0 *b 0
十进制，其中 b 是新的基数。
正如我所了解的，这被恰当地称为双射计数。举个例子，在 base 6 中，我们将有：
Base 10 Base 6
1 1
2 2
...
6 6
7 11
8 12
...
11 15
12 16
13 21
...
36 56
从上面的维基百科链接，新基数的第一个“数字”是：
一个0 = m - q 0 k
其中 k 是新基数，m 是要转换的整数，q 0 = ceiling(m/k)-1。请注意与普通基础转换的相似之处，其中唯一的区别是 q 0将是 floor(m/k) 或普通整数除法。随后的“数字”以类似方式计算，使用 q 0而不是 m 来找到1等。
这个公式可以分为两种情况：
- (m mod k) == 0: a 0 = k 和 q 0 = (m div k) - 1
- (m mod k) != 0: a 0 = (m mod k) 和 q 0 = (m div k)
这是算法的核心。对于任何整数 m，我们可以迭代地应用这个公式，直到得到 q p == 0。还要注意，转换自然是可逆的。给定一个6666以 6 为底的数字，十进制值为：
(6*6^3)+(6*6^2)+(6*6^1)+(6*6^0)=1554
我们使用这个事实来找到要转换的整数范围，以获得一定长度的所有组合。抱歉，我的 PHP 技能不存在。希望 Java 代码足够清晰。鉴于：
char [] letters = new char [] {'0','a','b','c','1','2','3'};
int max_length = 4;
我们有这个功能：
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);
}
其中 / 表示整数除法，或 floor(a/b)。
该函数仅依赖于输入整数，而不依赖于先前计算的结果，因此并行处理的可能性非常好。
这是具有上述输入的输出。根据您的示例，最低有效位是第一位的。
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
于 2013-03-25T22:14:56.680 回答
7
解决此问题的最佳且简洁的方法是使用递归解决方案，希望行内注释足以理解解决方案：
<?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);
?>
如果您有兴趣，这里是上述代码的非常大的输出：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
于 2013-03-25T05:57:27.753 回答
6
我会选择递归解决方案。
“猜测”第一个元素是什么，并递归以下元素。
重复所有可能的猜测。
伪代码：
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 代码：
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);
}
调用：
char[] arr = "abcde".toCharArray();
findCombinations(arr, 3);
结果是：
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
于 2012-09-06T06:16:49.867 回答
6
可以肯定的一件事是，无论算法使用什么，生成所有数字的最佳时间复杂度大约是 O((n^m+1)/(n-1)) （假设你不是使用任何并行编程。）。（其中 n 是数组的大小，m 是最大长度。）
对于上述任何一种算法都更适合。
于 2013-03-25T11:49:09.597 回答
6
解决方案
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));
输出
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
)
基本原理
- 避免在 PHP 中针对此类问题使用递归解决方案（注意，我喜欢使用经过优化以更好地处理它的语言中的递归）以避免随着长度的增长而出现堆栈问题。
- 将函数分解为两个单独的函数，一个实现最小和最大长度，另一个获得特定长度的可能组合以促进重用和清晰。
- 尽可能限制 2 个函数内的函数调用以提高性能（这个算法很快就会变得很重！）
我是如何开发这个解决方案的
我从一个处理长度为 5 组合的特定情况的函数开始，重构以泛化算法，重构以泛化算法等。我提出了一个快速要点，以便您可以看到迭代以实现此工作版本作为如何构建此类算法的案例研究：
于 2013-03-30T21:52:59.843 回答
4
一种基于简单计数算法的非递归 PHP 解决方案，具有尽可能多的可能数字，因为$letters数组有元素。所以对于一个由 5 个元素组成的数组，最大长度为 3，计数数组有 1（第一个）到 3 个（结束）元素，比如
0, 1, ..., 4 then
00, 01, ..., 04, 10, ... 14, ... 44
什么时候（实际上00是array(0,0)为了优化循环，计数就像00, 10, 20, ..., 34, 44）
然后从那个“计数”数组构建字符串。
<?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;
}
}
}
运行函数
andcounting( array('a','b','c','d','e'), 3);
给出（从左到右和从上到下）
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
于 2013-03-25T08:42:49.387 回答
3
与最初为空的集合 S 的 k 次累积集合乘积将产生直到 k 长的所有排列，其中 n = |S| ..
时间：O(kn^2)
空间：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);
}
}
于 2013-03-25T07:01:57.463 回答
3
这是一种不同的语言，但这是您最终要寻找的结果吗？
>>> 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
>>>
于 2013-03-27T13:33:08.063 回答
3
它比算法更安静：）但它有效！我发现拥有序列迭代器很有用。
$characters = implode('', $letters_array); // string as character set
$seq = new Sequence($characters, $min_length, $max_length);
while (($s = $seq->fetch()) !== false) {
echo $s . "\n";
}
这是一个类：
<?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;
}
}
结果是
a
b
c
1
2
3
aa
ba
...
23333
33333
于 2013-03-29T09:13:47.187 回答
2
这是一个简单的解决方案
假设：
$source = array(
'a',
'b',
'c',
'1',
'2',
'3'
);
示例 1
$c = new FindCombination($source);
echo $c->find(4,true); //returns all resul in json
echo count($c), PHP_EOL; //returns total
示例 2
如果你想要它排序使用
echo $c->find(4,true);
输出
[
"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"
]
示例 3
您可以遍历结果
$c = new FindCombination($source);
foreach ( $c->find(4, true) as $v ) {
echo $v . "|";
}
使用的类
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;
}
}
}
}
于 2013-03-25T17:17:19.817 回答
2
我建议你在 php 中找到 pythons itertools.product 功能的实现。（或者只是自己复制实现）。
以下代码获取指定长度的所有排列。您需要长度为 1、2、3、4。
最后一个问题是没有重复的字符，所以你可以添加“letters = set(letters)”来确保。
>>> 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
于 2013-03-27T20:22:50.587 回答
0
从数组中获取所有可能的字符串组合到一定长度的算法。
该算法基于查找索引的Power 集，而这又基于查找具有大小的索引的所有组合（不重复）：1, 2,..., n。
由于我在您的偏好语言中的技能“趋于零”，这里有一个可以用作基准的 C# 实现：
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);
}
}
}
}
以下是辅助打印功能：
//-------------------------------------------------------------
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(")");
}
输入：
{a, b, c}
输出：
() (a) (b) (c) (a, b) (a, c) (b, c)
变量k和n函数调用CombinationsNoRepetition决定了第一组和最后一组的长度，即有你的min和max。
于 2017-09-07T14:16:55.260 回答