我想写一个函数，它以一个字母数组作为参数，并从中选择一些字母。
假设您提供了一个包含8个字母的数组，并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词)，每个数组由3个字母组成。
当前回答
不需要进行集合操作。这个问题几乎和循环K个嵌套循环一样，但你必须小心索引和边界(忽略Java和OOP的东西):
public class CombinationsGen {
private final int n;
private final int k;
private int[] buf;
public CombinationsGen(int n, int k) {
this.n = n;
this.k = k;
}
public void combine(Consumer<int[]> consumer) {
buf = new int[k];
rec(0, 0, consumer);
}
private void rec(int index, int next, Consumer<int[]> consumer) {
int max = n - index;
if (index == k - 1) {
for (int i = 0; i < max && next < n; i++) {
buf[index] = next;
next++;
consumer.accept(buf);
}
} else {
for (int i = 0; i < max && next + index < n; i++) {
buf[index] = next;
next++;
rec(index + 1, next, consumer);
}
}
}
}
像这样使用:
CombinationsGen gen = new CombinationsGen(5, 2);
AtomicInteger total = new AtomicInteger();
gen.combine(arr -> {
System.out.println(Arrays.toString(arr));
total.incrementAndGet();
});
System.out.println(total);
获得预期的结果:
[0, 1]
[0, 2]
[0, 3]
[0, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
10
最后，将索引映射到您可能拥有的任何数据集。
其他回答
Python中的简短示例:
def comb(sofar, rest, n):
if n == 0:
print sofar
else:
for i in range(len(rest)):
comb(sofar + rest[i], rest[i+1:], n-1)
>>> comb("", "abcde", 3)
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
为了解释，递归方法用下面的例子描述:
示例:A B C D E 3的所有组合是:
A与其余2的所有组合(B C D E) B与其余2的所有组合(C D E) C与其余2的所有组合(D E)
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秒后停止，因此输入奇怪的数字是相对安全的。
最近在IronScripter网站上有一个PowerShell挑战，需要一个n- choice -k的解决方案。我在那里发布了一个解决方案，但这里有一个更通用的版本。
AllK开关用于控制输出是长度为ChooseK的组合，还是长度为1到ChooseK的组合。 Prefix参数实际上是输出字符串的累加器，但其效果是为初始调用传递的值实际上会为每一行输出添加前缀。
function Get-NChooseK
{
[CmdletBinding()]
Param
(
[String[]]
$ArrayN
, [Int]
$ChooseK
, [Switch]
$AllK
, [String]
$Prefix = ''
)
PROCESS
{
# Validate the inputs
$ArrayN = $ArrayN | Sort-Object -Unique
If ($ChooseK -gt $ArrayN.Length)
{
Write-Error "Can't choose $ChooseK items when only $($ArrayN.Length) are available." -ErrorAction Stop
}
# Control the output
$firstK = If ($AllK) { 1 } Else { $ChooseK }
# Get combinations
$firstK..$ChooseK | ForEach-Object {
$thisK = $_
$ArrayN[0..($ArrayN.Length-($thisK--))] | ForEach-Object {
If ($thisK -eq 0)
{
Write-Output ($Prefix+$_)
}
Else
{
Get-NChooseK -Array ($ArrayN[($ArrayN.IndexOf($_)+1)..($ArrayN.Length-1)]) -Choose $thisK -AllK:$false -Prefix ($Prefix+$_)
}
}
}
}
}
例如:
PS C:\>$ArrayN = 'E','B','C','A','D'
PS C:\>$ChooseK = 3
PS C:\>Get-NChooseK -ArrayN $ArrayN -ChooseK $ChooseK
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
PowerShell解决方案:
function Get-NChooseK
{
<#
.SYNOPSIS
Returns all the possible combinations by choosing K items at a time from N possible items.
.DESCRIPTION
Returns all the possible combinations by choosing K items at a time from N possible items.
The combinations returned do not consider the order of items as important i.e. 123 is considered to be the same combination as 231, etc.
.PARAMETER ArrayN
The array of items to choose from.
.PARAMETER ChooseK
The number of items to choose.
.PARAMETER AllK
Includes combinations for all lesser values of K above zero i.e. 1 to K.
.PARAMETER Prefix
String that will prefix each line of the output.
.EXAMPLE
PS C:\> Get-NChooseK -ArrayN '1','2','3' -ChooseK 3
123
.EXAMPLE
PS C:\> Get-NChooseK -ArrayN '1','2','3' -ChooseK 3 -AllK
1
2
3
12
13
23
123
.EXAMPLE
PS C:\> Get-NChooseK -ArrayN '1','2','3' -ChooseK 2 -Prefix 'Combo: '
Combo: 12
Combo: 13
Combo: 23
.NOTES
Author : nmbell
#>
# Use cmdlet binding
[CmdletBinding()]
# Declare parameters
Param
(
[String[]]
$ArrayN
, [Int]
$ChooseK
, [Switch]
$AllK
, [String]
$Prefix = ''
)
BEGIN
{
}
PROCESS
{
# Validate the inputs
$ArrayN = $ArrayN | Sort-Object -Unique
If ($ChooseK -gt $ArrayN.Length)
{
Write-Error "Can't choose $ChooseK items when only $($ArrayN.Length) are available." -ErrorAction Stop
}
# Control the output
$firstK = If ($AllK) { 1 } Else { $ChooseK }
# Get combinations
$firstK..$ChooseK | ForEach-Object {
$thisK = $_
$ArrayN[0..($ArrayN.Length-($thisK--))] | ForEach-Object {
If ($thisK -eq 0)
{
Write-Output ($Prefix+$_)
}
Else
{
Get-NChooseK -Array ($ArrayN[($ArrayN.IndexOf($_)+1)..($ArrayN.Length-1)]) -Choose $thisK -AllK:$false -Prefix ($Prefix+$_)
}
}
}
}
END
{
}
}
例如:
PS C:\>Get-NChooseK -ArrayN 'A','B','C','D','E' -ChooseK 3
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
最近在IronScripter网站上发布了一个类似于这个问题的挑战，在那里你可以找到我的链接和其他一些解决方案。
我知道这个问题已经有很多答案了，但我想在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元素集的幂集(如果你愿意的话)。
我并不是说这很优雅，只是说它在经过大量的测试(并在调试阶段将空气变为蓝色:)之后可以工作。
