我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
一个简洁的Javascript解决方案:
Array.prototype.combine=function combine(k){
var toCombine=this;
var last;
function combi(n,comb){
var combs=[];
for ( var x=0,y=comb.length;x<y;x++){
for ( var l=0,m=toCombine.length;l<m;l++){
combs.push(comb[x]+toCombine[l]);
}
}
if (n<k-1){
n++;
combi(n,combs);
} else{last=combs;}
}
combi(1,toCombine);
return last;
}
// Example:
// var toCombine=['a','b','c'];
// var results=toCombine.combine(4);
其他回答
递归,一个很简单的答案,combo,在Free Pascal中。
procedure combinata (n, k :integer; producer :oneintproc);
procedure combo (ndx, nbr, len, lnd :integer);
begin
for nbr := nbr to len do begin
productarray[ndx] := nbr;
if len < lnd then
combo(ndx+1,nbr+1,len+1,lnd)
else
producer(k);
end;
end;
begin
combo (0, 0, n-k, n-1);
end;
“producer”处理为每个组合生成的产品数组。
由于没有提到编程语言,我假设列表也是可以的。下面是一个OCaml版本,适用于短列表(非尾递归)。给定一个包含任意类型元素的列表l和一个整数n,如果我们假设结果列表中元素的顺序被忽略,它将返回一个包含l的n个元素的所有可能列表的列表,即list ['a';'b']与['b';'a']相同,并且将报告一次。因此,结果列表的大小将是((list。长度l)选择n)。
递归的直观原理如下:取列表的头,然后进行两次递归调用:
递归调用1 (RC1):到列表的尾部,但选择n-1个元素 递归调用2 (RC2):到列表的尾部,但选择n个元素
要组合递归结果,list-乘(请使用奇数名称)列表的头部与RC1的结果,然后附加(@)RC2的结果。List-multiply是如下操作lmul:
a lmul [ l1 ; l2 ; l3] = [a::l1 ; a::l2 ; a::l3]
Lmul在下面的代码中实现
List.map (fun x -> h::x)
当列表的大小等于您想要选择的元素数量时,递归将终止,在这种情况下,您只需返回列表本身。
下面是OCaml中实现上述算法的四行代码:
let rec choose l n = match l, (List.length l) with
| _, lsize when n==lsize -> [l]
| h::t, _ -> (List.map (fun x-> h::x) (choose t (n-1))) @ (choose t n)
| [], _ -> []
下面的递归算法从有序集中选取所有k元素组合:
选择组合中的第一个元素I 将I与从大于I的元素集中递归选择的k-1个元素的组合组合。
对集合中的每一个i进行上述迭代。
为了避免重复,您必须选择比i大的其余元素。这样[3,5]将只被选中一次,即[3]与[5]结合,而不是两次(该条件消除了[5]+[3])。没有这个条件,你得到的是变化而不是组合。
像Andrea Ambu一样用Python写的,但不是硬编码来选择三个。
def combinations(list, k):
"""Choose combinations of list, choosing k elements(no repeats)"""
if len(list) < k:
return []
else:
seq = [i for i in range(k)]
while seq:
print [list[index] for index in seq]
seq = get_next_combination(len(list), k, seq)
def get_next_combination(num_elements, k, seq):
index_to_move = find_index_to_move(num_elements, seq)
if index_to_move == None:
return None
else:
seq[index_to_move] += 1
#for every element past this sequence, move it down
for i, elem in enumerate(seq[(index_to_move+1):]):
seq[i + 1 + index_to_move] = seq[index_to_move] + i + 1
return seq
def find_index_to_move(num_elements, seq):
"""Tells which index should be moved"""
for rev_index, elem in enumerate(reversed(seq)):
if elem < (num_elements - rev_index - 1):
return len(seq) - rev_index - 1
return None
这是一个优雅的Scala通用实现,如99个Scala问题所述。
object P26 {
def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] =
ls match {
case Nil => Nil
case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)
}
def combinations[A](n: Int, ls: List[A]): List[List[A]] =
if (n == 0) List(Nil)
else flatMapSublists(ls) { sl =>
combinations(n - 1, sl.tail) map {sl.head :: _}
}
}