我想写一个函数，它以一个字母数组作为参数，并从中选择一些字母。
假设您提供了一个包含8个字母的数组，并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词)，每个数组由3个字母组成。
当前回答
如果你可以使用SQL语法——比如，如果你使用LINQ访问一个结构或数组的字段，或者直接访问一个数据库，其中有一个名为“Alphabet”的表，只有一个字符字段“Letter”，你可以适应以下代码:
SELECT A.Letter, B.Letter, C.Letter
FROM Alphabet AS A, Alphabet AS B, Alphabet AS C
WHERE A.Letter<>B.Letter AND A.Letter<>C.Letter AND B.Letter<>C.Letter
AND A.Letter<B.Letter AND B.Letter<C.Letter
这将返回所有3个字母的组合，不管你在表格“字母表”中有多少个字母(它可以是3,8,10,27等)。
如果你想要的是所有的排列，而不是组合(也就是说，你想要“ACB”和“ABC”被视为不同的，而不是只出现一次)，只需删除最后一行(and一行)，就完成了。
Post-Edit:重新阅读问题后，我意识到需要的是通用算法，而不仅仅是选择3个项目的特定算法。Adam Hughes的答案是完整的，不幸的是我还不能投票。这个答案很简单，但只适用于你想要三样东西的时候。
其他回答
假设你的字母数组是这样的:"ABCDEFGH"。你有三个下标(i, j, k)来表示你要用哪个字母来表示当前单词。
A B C D E F G H ^ ^ ^ i j k
首先你改变k，所以下一步看起来像这样:
A B C D E F G H ^ ^ ^ i j k
如果你到达终点，你继续改变j和k。
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k
一旦j达到G, i也开始变化。
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k ...
function initializePointers($cnt) {
$pointers = [];
for($i=0; $i<$cnt; $i++) {
$pointers[] = $i;
}
return $pointers;
}
function incrementPointers(&$pointers, &$arrLength) {
for($i=0; $i<count($pointers); $i++) {
$currentPointerIndex = count($pointers) - $i - 1;
$currentPointer = $pointers[$currentPointerIndex];
if($currentPointer < $arrLength - $i - 1) {
++$pointers[$currentPointerIndex];
for($j=1; ($currentPointerIndex+$j)<count($pointers); $j++) {
$pointers[$currentPointerIndex+$j] = $pointers[$currentPointerIndex]+$j;
}
return true;
}
}
return false;
}
function getDataByPointers(&$arr, &$pointers) {
$data = [];
for($i=0; $i<count($pointers); $i++) {
$data[] = $arr[$pointers[$i]];
}
return $data;
}
function getCombinations($arr, $cnt)
{
$len = count($arr);
$result = [];
$pointers = initializePointers($cnt);
do {
$result[] = getDataByPointers($arr, $pointers);
} while(incrementPointers($pointers, count($arr)));
return $result;
}
$result = getCombinations([0, 1, 2, 3, 4, 5], 3);
print_r($result);
基于https://stackoverflow.com/a/127898/2628125，但更抽象，适用于任何大小的指针。
简短的python代码，产生索引位置
def yield_combos(n,k):
# n is set size, k is combo size
i = 0
a = [0]*k
while i > -1:
for j in range(i+1, k):
a[j] = a[j-1]+1
i=j
yield a
while a[i] == i + n - k:
i -= 1
a[i] += 1
基于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);
最近在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
不需要进行集合操作。这个问题几乎和循环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
最后，将索引映射到您可能拥有的任何数据集。
