我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
我知道这个问题已经有很多答案了,但我想在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元素集的幂集(如果你愿意的话)。
我并不是说这很优雅,只是说它在经过大量的测试(并在调试阶段将空气变为蓝色:)之后可以工作。
其他回答
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))))
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;
}
}
JavaScript,基于生成器,递归方法:
function *nCk(n,k){ for(var i=n-1;i>=k-1;--i) if(k===1) yield [i]; else for(var temp of nCk(i,k-1)){ temp.unshift(i); yield temp; } } function test(){ try{ var n=parseInt(ninp.value); var k=parseInt(kinp.value); log.innerText=""; var stop=Date.now()+1000; if(k>=1) for(var res of nCk(n,k)) if(Date.now()<stop) log.innerText+=JSON.stringify(res)+" "; else{ log.innerText+="1 second passed, stopping here."; break; } }catch(ex){} } n:<input id="ninp" oninput="test()"> >= k:<input id="kinp" oninput="test()"> >= 1 <div id="log"></div>
通过这种方式(减少i和unshift()),它以递减的顺序生成组合和组合内的元素,有点赏心悦目。 测试在1秒后停止,因此输入奇怪的数字是相对安全的。
递归,一个很简单的答案,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”处理为每个组合生成的产品数组。
赶时髦,发布另一个解决方案。这是一个通用的Java实现。输入:(int k)是要选择的元素数量,(List<T> List)是要选择的列表。返回一个组合列表(list < list <T>>)。
public static <T> List<List<T>> getCombinations(int k, List<T> list) {
List<List<T>> combinations = new ArrayList<List<T>>();
if (k == 0) {
combinations.add(new ArrayList<T>());
return combinations;
}
for (int i = 0; i < list.size(); i++) {
T element = list.get(i);
List<T> rest = getSublist(list, i+1);
for (List<T> previous : getCombinations(k-1, rest)) {
previous.add(element);
combinations.add(previous);
}
}
return combinations;
}
public static <T> List<T> getSublist(List<T> list, int i) {
List<T> sublist = new ArrayList<T>();
for (int j = i; j < list.size(); j++) {
sublist.add(list.get(j));
}
return sublist;
}