我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
我发现这个线程很有用,我想我会添加一个Javascript解决方案,你可以弹出到Firebug。取决于你的JS引擎,如果起始字符串很大,可能会花一点时间。
function string_recurse(active, rest) {
if (rest.length == 0) {
console.log(active);
} else {
string_recurse(active + rest.charAt(0), rest.substring(1, rest.length));
string_recurse(active, rest.substring(1, rest.length));
}
}
string_recurse("", "abc");
输出如下:
abc
ab
ac
a
bc
b
c
其他回答
在c#中:
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
return k == 0 ? new[] { new T[0] } :
elements.SelectMany((e, i) =>
elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}
用法:
var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);
结果:
123
124
125
134
135
145
234
235
245
345
static IEnumerable<string> Combinations(List<string> characters, int length)
{
for (int i = 0; i < characters.Count; i++)
{
// only want 1 character, just return this one
if (length == 1)
yield return characters[i];
// want more than one character, return this one plus all combinations one shorter
// only use characters after the current one for the rest of the combinations
else
foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
yield return characters[i] + next;
}
}
也许我错过了重点(你需要的是算法,而不是现成的解决方案),但看起来scala已经开箱即用了(现在):
def combis(str:String, k:Int):Array[String] = {
str.combinations(k).toArray
}
使用这样的方法:
println(combis("abcd",2).toList)
会产生:
List(ab, ac, ad, bc, bd, cd)
在Python中,利用递归的优势和所有事情都是通过引用完成的事实。对于非常大的集合,这将占用大量内存,但其优点是初始集合可以是一个复杂的对象。它只会找到唯一的组合。
import copy
def find_combinations( length, set, combinations = None, candidate = None ):
# recursive function to calculate all unique combinations of unique values
# from [set], given combinations of [length]. The result is populated
# into the 'combinations' list.
#
if combinations == None:
combinations = []
if candidate == None:
candidate = []
for item in set:
if item in candidate:
# this item already appears in the current combination somewhere.
# skip it
continue
attempt = copy.deepcopy(candidate)
attempt.append(item)
# sorting the subset is what gives us completely unique combinations,
# so that [1, 2, 3] and [1, 3, 2] will be treated as equals
attempt.sort()
if len(attempt) < length:
# the current attempt at finding a new combination is still too
# short, so add another item to the end of the set
# yay recursion!
find_combinations( length, set, combinations, attempt )
else:
# the current combination attempt is the right length. If it
# already appears in the list of found combinations then we'll
# skip it.
if attempt in combinations:
continue
else:
# otherwise, we append it to the list of found combinations
# and move on.
combinations.append(attempt)
continue
return len(combinations)
你可以这样使用它。传递'result'是可选的,所以你可以用它来获取可能组合的数量…尽管这样做效率很低(最好通过计算来完成)。
size = 3
set = [1, 2, 3, 4, 5]
result = []
num = find_combinations( size, set, result )
print "size %d results in %d sets" % (size, num)
print "result: %s" % (result,)
您应该从测试数据中得到以下输出:
size 3 results in 10 sets
result: [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]
如果你的集合是这样的,它也会工作得很好:
set = [
[ 'vanilla', 'cupcake' ],
[ 'chocolate', 'pudding' ],
[ 'vanilla', 'pudding' ],
[ 'chocolate', 'cookie' ],
[ 'mint', 'cookie' ]
]
短快C实现
#include <stdio.h>
void main(int argc, char *argv[]) {
const int n = 6; /* The size of the set; for {1, 2, 3, 4} it's 4 */
const int p = 4; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */
int i = 0;
for (int j = 0; j <= n; j++) comb[j] = 0;
while (i >= 0) {
if (comb[i] < n + i - p + 1) {
comb[i]++;
if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); }
else { comb[++i] = comb[i - 1]; }
} else i--; }
}
要查看它有多快,请使用这段代码并测试它
#include <time.h>
#include <stdio.h>
void main(int argc, char *argv[]) {
const int n = 32; /* The size of the set; for {1, 2, 3, 4} it's 4 */
const int p = 16; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */
int c = 0; int i = 0;
for (int j = 0; j <= n; j++) comb[j] = 0;
while (i >= 0) {
if (comb[i] < n + i - p + 1) {
comb[i]++;
/* if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); } */
if (i == p - 1) c++;
else { comb[++i] = comb[i - 1]; }
} else i--; }
printf("%d!%d == %d combination(s) in %15.3f second(s)\n ", p, n, c, clock()/1000.0);
}
使用cmd.exe (windows)测试:
Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.
c:\Program Files\lcc\projects>combination
16!32 == 601080390 combination(s) in 5.781 second(s)
c:\Program Files\lcc\projects>
祝你有愉快的一天。