我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
下面是我最近用Java写的一段代码,它计算并返回从“outOf”元素中“num”元素的所有组合。
// author: Sourabh Bhat (heySourabh@gmail.com)
public class Testing
{
public static void main(String[] args)
{
// Test case num = 5, outOf = 8.
int num = 5;
int outOf = 8;
int[][] combinations = getCombinations(num, outOf);
for (int i = 0; i < combinations.length; i++)
{
for (int j = 0; j < combinations[i].length; j++)
{
System.out.print(combinations[i][j] + " ");
}
System.out.println();
}
}
private static int[][] getCombinations(int num, int outOf)
{
int possibilities = get_nCr(outOf, num);
int[][] combinations = new int[possibilities][num];
int arrayPointer = 0;
int[] counter = new int[num];
for (int i = 0; i < num; i++)
{
counter[i] = i;
}
breakLoop: while (true)
{
// Initializing part
for (int i = 1; i < num; i++)
{
if (counter[i] >= outOf - (num - 1 - i))
counter[i] = counter[i - 1] + 1;
}
// Testing part
for (int i = 0; i < num; i++)
{
if (counter[i] < outOf)
{
continue;
} else
{
break breakLoop;
}
}
// Innermost part
combinations[arrayPointer] = counter.clone();
arrayPointer++;
// Incrementing part
counter[num - 1]++;
for (int i = num - 1; i >= 1; i--)
{
if (counter[i] >= outOf - (num - 1 - i))
counter[i - 1]++;
}
}
return combinations;
}
private static int get_nCr(int n, int r)
{
if(r > n)
{
throw new ArithmeticException("r is greater then n");
}
long numerator = 1;
long denominator = 1;
for (int i = n; i >= r + 1; i--)
{
numerator *= i;
}
for (int i = 2; i <= n - r; i++)
{
denominator *= i;
}
return (int) (numerator / denominator);
}
}
其他回答
我知道这个问题已经有很多答案了,但我想在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元素集的幂集(如果你愿意的话)。
我并不是说这很优雅,只是说它在经过大量的测试(并在调试阶段将空气变为蓝色:)之后可以工作。
下面是一个使用宏的Lisp方法。这适用于Common Lisp,也适用于其他Lisp方言。
下面的代码创建了'n'个嵌套循环,并为列表lst中的'n'个元素的每个组合执行任意代码块(存储在body变量中)。变量var指向一个包含用于循环的变量的列表。
(defmacro do-combinations ((var lst num) &body body)
(loop with syms = (loop repeat num collect (gensym))
for i on syms
for k = `(loop for ,(car i) on (cdr ,(cadr i))
do (let ((,var (list ,@(reverse syms)))) (progn ,@body)))
then `(loop for ,(car i) on ,(if (cadr i) `(cdr ,(cadr i)) lst) do ,k)
finally (return k)))
让我们看看…
(macroexpand-1 '(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p))))
(LOOP FOR #:G3217 ON '(1 2 3 4 5 6 7) DO
(LOOP FOR #:G3216 ON (CDR #:G3217) DO
(LOOP FOR #:G3215 ON (CDR #:G3216) DO
(LOOP FOR #:G3214 ON (CDR #:G3215) DO
(LET ((P (LIST #:G3217 #:G3216 #:G3215 #:G3214)))
(PROGN (PPRINT (MAPCAR #'CAR P))))))))
(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p)))
(1 2 3 4)
(1 2 3 5)
(1 2 3 6)
...
由于默认情况下不存储组合,因此存储空间保持在最小值。选择主体代码而不是存储所有结果的可能性也提供了更大的灵活性。
这是一个简单的JS解决方案:
function getAllCombinations(n, k, f1) { indexes = Array(k); for (let i =0; i< k; i++) { indexes[i] = i; } var total = 1; f1(indexes); while (indexes[0] !== n-k) { total++; getNext(n, indexes); f1(indexes); } return {total}; } function getNext(n, vec) { const k = vec.length; vec[k-1]++; for (var i=0; i<k; i++) { var currentIndex = k-i-1; if (vec[currentIndex] === n - i) { var nextIndex = k-i-2; vec[nextIndex]++; vec[currentIndex] = vec[nextIndex] + 1; } } for (var i=1; i<k; i++) { if (vec[i] === n - (k-i - 1)) { vec[i] = vec[i-1] + 1; } } return vec; } let start = new Date(); let result = getAllCombinations(10, 3, indexes => console.log(indexes)); let runTime = new Date() - start; console.log({ result, runTime });
《计算机编程艺术,卷4A:组合算法,第1部分》第7.2.1.3节中算法L(字典组合)的C代码:
#include <stdio.h>
#include <stdlib.h>
void visit(int* c, int t)
{
// for (int j = 1; j <= t; j++)
for (int j = t; j > 0; j--)
printf("%d ", c[j]);
printf("\n");
}
int* initialize(int n, int t)
{
// c[0] not used
int *c = (int*) malloc((t + 3) * sizeof(int));
for (int j = 1; j <= t; j++)
c[j] = j - 1;
c[t+1] = n;
c[t+2] = 0;
return c;
}
void comb(int n, int t)
{
int *c = initialize(n, t);
int j;
for (;;) {
visit(c, t);
j = 1;
while (c[j]+1 == c[j+1]) {
c[j] = j - 1;
++j;
}
if (j > t)
return;
++c[j];
}
free(c);
}
int main(int argc, char *argv[])
{
comb(5, 3);
return 0;
}
下面是我的JavaScript解决方案,通过使用reduce/map,它消除了几乎所有变量,功能更强大
function combinations(arr, size) { var len = arr.length; if (size > len) return []; if (!size) return [[]]; if (size == len) return [arr]; return arr.reduce(function (acc, val, i) { var res = combinations(arr.slice(i + 1), size - 1) .map(function (comb) { return [val].concat(comb); }); return acc.concat(res); }, []); } var combs = combinations([1,2,3,4,5,6,7,8],3); combs.map(function (comb) { document.body.innerHTML += comb.toString() + '<br />'; }); document.body.innerHTML += '<br /> Total combinations = ' + combs.length;