我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含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);
其他回答
基于java解决方案的短php算法返回k元素从n(二项式系数)的所有组合:
$array = array(1,2,3,4,5);
$array_result = NULL;
$array_general = NULL;
function combinations($array, $len, $start_position, $result_array, $result_len, &$general_array)
{
if($len == 0)
{
$general_array[] = $result_array;
return;
}
for ($i = $start_position; $i <= count($array) - $len; $i++)
{
$result_array[$result_len - $len] = $array[$i];
combinations($array, $len-1, $i+1, $result_array, $result_len, $general_array);
}
}
combinations($array, 3, 0, $array_result, 3, $array_general);
echo "<pre>";
print_r($array_general);
echo "</pre>";
相同的解决方案,但在javascript:
var newArray = [1, 2, 3, 4, 5];
var arrayResult = [];
var arrayGeneral = [];
function combinations(newArray, len, startPosition, resultArray, resultLen, arrayGeneral) {
if(len === 0) {
var tempArray = [];
resultArray.forEach(value => tempArray.push(value));
arrayGeneral.push(tempArray);
return;
}
for (var i = startPosition; i <= newArray.length - len; i++) {
resultArray[resultLen - len] = newArray[i];
combinations(newArray, len-1, i+1, resultArray, resultLen, arrayGeneral);
}
}
combinations(newArray, 3, 0, arrayResult, 3, arrayGeneral);
console.log(arrayGeneral);
也许我错过了重点(你需要的是算法,而不是现成的解决方案),但看起来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)
简单但缓慢的c++回溯算法。
#include <iostream>
void backtrack(int* numbers, int n, int k, int i, int s)
{
if (i == k)
{
for (int j = 0; j < k; ++j)
{
std::cout << numbers[j];
}
std::cout << std::endl;
return;
}
if (s > n)
{
return;
}
numbers[i] = s;
backtrack(numbers, n, k, i + 1, s + 1);
backtrack(numbers, n, k, i, s + 1);
}
int main(int argc, char* argv[])
{
int n = 5;
int k = 3;
int* numbers = new int[k];
backtrack(numbers, n, k, 0, 1);
delete[] numbers;
return 0;
}
我知道这个问题已经有很多答案了,但我想在JavaScript中添加我自己的贡献,它由两个函数组成——一个生成原始n元素集的所有可能不同的k子集,另一个使用第一个函数生成原始n元素集的幂集。
下面是这两个函数的代码:
//Generate combination subsets from a base set of elements (passed as an array). This function should generate an
//array containing nCr elements, where nCr = n!/[r! (n-r)!].
//Arguments:
//[1] baseSet : The base set to create the subsets from (e.g., ["a", "b", "c", "d", "e", "f"])
//[2] cnt : The number of elements each subset is to contain (e.g., 3)
function MakeCombinationSubsets(baseSet, cnt)
{
var bLen = baseSet.length;
var indices = [];
var subSet = [];
var done = false;
var result = []; //Contains all the combination subsets generated
var done = false;
var i = 0;
var idx = 0;
var tmpIdx = 0;
var incr = 0;
var test = 0;
var newIndex = 0;
var inBounds = false;
var tmpIndices = [];
var checkBounds = false;
//First, generate an array whose elements are indices into the base set ...
for (i=0; i<cnt; i++)
indices.push(i);
//Now create a clone of this array, to be used in the loop itself ...
tmpIndices = [];
tmpIndices = tmpIndices.concat(indices);
//Now initialise the loop ...
idx = cnt - 1; //point to the last element of the indices array
incr = 0;
done = false;
while (!done)
{
//Create the current subset ...
subSet = []; //Make sure we begin with a completely empty subset before continuing ...
for (i=0; i<cnt; i++)
subSet.push(baseSet[tmpIndices[i]]); //Create the current subset, using items selected from the
//base set, using the indices array (which will change as we
//continue scanning) ...
//Add the subset thus created to the result set ...
result.push(subSet);
//Now update the indices used to select the elements of the subset. At the start, idx will point to the
//rightmost index in the indices array, but the moment that index moves out of bounds with respect to the
//base set, attention will be shifted to the next left index.
test = tmpIndices[idx] + 1;
if (test >= bLen)
{
//Here, we're about to move out of bounds with respect to the base set. We therefore need to scan back,
//and update indices to the left of the current one. Find the leftmost index in the indices array that
//isn't going to move out of bounds with respect to the base set ...
tmpIdx = idx - 1;
incr = 1;
inBounds = false; //Assume at start that the index we're checking in the loop below is out of bounds
checkBounds = true;
while (checkBounds)
{
if (tmpIdx < 0)
{
checkBounds = false; //Exit immediately at this point
}
else
{
newIndex = tmpIndices[tmpIdx] + 1;
test = newIndex + incr;
if (test >= bLen)
{
//Here, incrementing the current selected index will take that index out of bounds, so
//we move on to the next index to the left ...
tmpIdx--;
incr++;
}
else
{
//Here, the index will remain in bounds if we increment it, so we
//exit the loop and signal that we're in bounds ...
inBounds = true;
checkBounds = false;
//End if/else
}
//End if
}
//End while
}
//At this point, if we'er still in bounds, then we continue generating subsets, but if not, we abort immediately.
if (!inBounds)
done = true;
else
{
//Here, we're still in bounds. We need to update the indices accordingly. NOTE: at this point, although a
//left positioned index in the indices array may still be in bounds, incrementing it to generate indices to
//the right may take those indices out of bounds. We therefore need to check this as we perform the index
//updating of the indices array.
tmpIndices[tmpIdx] = newIndex;
inBounds = true;
checking = true;
i = tmpIdx + 1;
while (checking)
{
test = tmpIndices[i - 1] + 1; //Find out if incrementing the left adjacent index takes it out of bounds
if (test >= bLen)
{
inBounds = false; //If we move out of bounds, exit NOW ...
checking = false;
}
else
{
tmpIndices[i] = test; //Otherwise, update the indices array ...
i++; //Now move on to the next index to the right in the indices array ...
checking = (i < cnt); //And continue until we've exhausted all the indices array elements ...
//End if/else
}
//End while
}
//At this point, if the above updating of the indices array has moved any of its elements out of bounds,
//we abort subset construction from this point ...
if (!inBounds)
done = true;
//End if/else
}
}
else
{
//Here, the rightmost index under consideration isn't moving out of bounds with respect to the base set when
//we increment it, so we simply increment and continue the loop ...
tmpIndices[idx] = test;
//End if
}
//End while
}
return(result);
//End function
}
function MakePowerSet(baseSet)
{
var bLen = baseSet.length;
var result = [];
var i = 0;
var partialSet = [];
result.push([]); //add the empty set to the power set
for (i=1; i<bLen; i++)
{
partialSet = MakeCombinationSubsets(baseSet, i);
result = result.concat(partialSet);
//End i loop
}
//Now, finally, add the base set itself to the power set to make it complete ...
partialSet = [];
partialSet.push(baseSet);
result = result.concat(partialSet);
return(result);
//End function
}
我用集合["a", "b", "c", "d", "e", "f"]作为基本集进行了测试,并运行代码以产生以下幂集:
[]
["a"]
["b"]
["c"]
["d"]
["e"]
["f"]
["a","b"]
["a","c"]
["a","d"]
["a","e"]
["a","f"]
["b","c"]
["b","d"]
["b","e"]
["b","f"]
["c","d"]
["c","e"]
["c","f"]
["d","e"]
["d","f"]
["e","f"]
["a","b","c"]
["a","b","d"]
["a","b","e"]
["a","b","f"]
["a","c","d"]
["a","c","e"]
["a","c","f"]
["a","d","e"]
["a","d","f"]
["a","e","f"]
["b","c","d"]
["b","c","e"]
["b","c","f"]
["b","d","e"]
["b","d","f"]
["b","e","f"]
["c","d","e"]
["c","d","f"]
["c","e","f"]
["d","e","f"]
["a","b","c","d"]
["a","b","c","e"]
["a","b","c","f"]
["a","b","d","e"]
["a","b","d","f"]
["a","b","e","f"]
["a","c","d","e"]
["a","c","d","f"]
["a","c","e","f"]
["a","d","e","f"]
["b","c","d","e"]
["b","c","d","f"]
["b","c","e","f"]
["b","d","e","f"]
["c","d","e","f"]
["a","b","c","d","e"]
["a","b","c","d","f"]
["a","b","c","e","f"]
["a","b","d","e","f"]
["a","c","d","e","f"]
["b","c","d","e","f"]
["a","b","c","d","e","f"]
只要复制粘贴这两个函数“原样”,你就有了提取n元素集的不同k子集所需的基本知识,并生成该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/)