我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
下面的递归算法从有序集中选取所有k元素组合:
选择组合中的第一个元素I 将I与从大于I的元素集中递归选择的k-1个元素的组合组合。
对集合中的每一个i进行上述迭代。
为了避免重复,您必须选择比i大的其余元素。这样[3,5]将只被选中一次,即[3]与[5]结合,而不是两次(该条件消除了[5]+[3])。没有这个条件,你得到的是变化而不是组合。
其他回答
由于没有提到编程语言,我假设列表也是可以的。下面是一个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)
| [], _ -> []
算法:
从1数到2^n。 将每个数字转换为二进制表示。 根据位置,将每个“on”位转换为集合中的元素。
在c#中:
void Main()
{
var set = new [] {"A", "B", "C", "D" }; //, "E", "F", "G", "H", "I", "J" };
var kElement = 2;
for(var i = 1; i < Math.Pow(2, set.Length); i++) {
var result = Convert.ToString(i, 2).PadLeft(set.Length, '0');
var cnt = Regex.Matches(Regex.Escape(result), "1").Count;
if (cnt == kElement) {
for(int j = 0; j < set.Length; j++)
if ( Char.GetNumericValue(result[j]) == 1)
Console.Write(set[j]);
Console.WriteLine();
}
}
}
为什么它能起作用?
在n元素集的子集和n位序列之间存在双射。
这意味着我们可以通过数数序列来计算出有多少个子集。
例如,下面的四个元素集可以用{0,1}X {0,1} X {0,1} X{0,1}(或2^4)个不同的序列表示。
我们要做的就是从1数到2^n来找到所有的组合。(我们忽略空集。)接下来,将数字转换为二进制表示。然后将集合中的元素替换为“on”位。
如果只需要k个元素的结果,则只在k位为“on”时打印。
(如果你想要所有的子集,而不是k长度的子集,删除cnt/kElement部分。)
(有关证明,请参阅麻省理工学院免费课件计算机科学数学,雷曼等,第11.2.2节。https://ocw.mit.edu/courses/electrical -工程-和-计算机- science/6 - 042 j -数学- -计算机科学-下降- 2010/readings/)
下面是c++中的迭代算法,它不使用STL,也不使用递归,也不使用条件嵌套循环。这样更快,它不执行任何元素交换,也不会给堆栈带来递归负担,还可以通过分别用mallloc()、free()和printf()替换new、delete和std::cout轻松地移植到ANSI C。
如果你想用不同或更长的字母显示元素,那么改变*字母参数以指向不同于"abcdefg"的字符串。
void OutputArrayChar(unsigned int* ka, size_t n, const char *alphabet) {
for (int i = 0; i < n; i++)
std::cout << alphabet[ka[i]] << ",";
std::cout << endl;
}
void GenCombinations(const unsigned int N, const unsigned int K, const char *alphabet) {
unsigned int *ka = new unsigned int [K]; //dynamically allocate an array of UINTs
unsigned int ki = K-1; //Point ki to the last elemet of the array
ka[ki] = N-1; //Prime the last elemet of the array.
while (true) {
unsigned int tmp = ka[ki]; //Optimization to prevent reading ka[ki] repeatedly
while (ki) //Fill to the left with consecutive descending values (blue squares)
ka[--ki] = --tmp;
OutputArrayChar(ka, K, alphabet);
while (--ka[ki] == ki) { //Decrement and check if the resulting value equals the index (bright green squares)
OutputArrayChar(ka, K, alphabet);
if (++ki == K) { //Exit condition (all of the values in the array are flush to the left)
delete[] ka;
return;
}
}
}
}
int main(int argc, char *argv[])
{
GenCombinations(7, 4, "abcdefg");
return 0;
}
重要提示:字母参数*必须指向至少N个字符的字符串。你也可以传递一个在其他地方定义的字符串地址。
组合:从“7选4”中选择。
另一种python递归解决方案。
def combination_indicies(n, k, j = 0, stack = []):
if len(stack) == k:
yield list(stack)
return
for i in range(j, n):
stack.append(i)
for x in combination_indicies(n, k, i + 1, stack):
yield x
stack.pop()
list(combination_indicies(5, 3))
输出:
[[0, 1, 2],
[0, 1, 3],
[0, 1, 4],
[0, 2, 3],
[0, 2, 4],
[0, 3, 4],
[1, 2, 3],
[1, 2, 4],
[1, 3, 4],
[2, 3, 4]]
Clojure版本:
(defn comb [k l]
(if (= 1 k) (map vector l)
(apply concat
(map-indexed
#(map (fn [x] (conj x %2))
(comb (dec k) (drop (inc %1) l)))
l))))