我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含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);
其他回答
假设你的字母数组是这样的:"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,但更抽象,适用于任何大小的指针。
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网站上发布了一个类似于这个问题的挑战,在那里你可以找到我的链接和其他一些解决方案。
c#简单算法。 (我发布它是因为我试图使用你们上传的那个,但由于某种原因我无法编译它——扩展一个类?所以我自己写了一个,以防别人遇到和我一样的问题)。 顺便说一下,除了基本的编程,我对c#没什么兴趣,但是这个工作得很好。
public static List<List<int>> GetSubsetsOfSizeK(List<int> lInputSet, int k)
{
List<List<int>> lSubsets = new List<List<int>>();
GetSubsetsOfSizeK_rec(lInputSet, k, 0, new List<int>(), lSubsets);
return lSubsets;
}
public static void GetSubsetsOfSizeK_rec(List<int> lInputSet, int k, int i, List<int> lCurrSet, List<List<int>> lSubsets)
{
if (lCurrSet.Count == k)
{
lSubsets.Add(lCurrSet);
return;
}
if (i >= lInputSet.Count)
return;
List<int> lWith = new List<int>(lCurrSet);
List<int> lWithout = new List<int>(lCurrSet);
lWith.Add(lInputSet[i++]);
GetSubsetsOfSizeK_rec(lInputSet, k, i, lWith, lSubsets);
GetSubsetsOfSizeK_rec(lInputSet, k, i, lWithout, lSubsets);
}
GetSubsetsOfSizeK(set of type List<int>, integer k)
您可以修改它以遍历您正在处理的任何内容。
好运!
这是一个c++解决方案,我提出使用递归和位移位。它也可以在C语言中工作。
void r_nCr(unsigned int startNum, unsigned int bitVal, unsigned int testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
unsigned int n = (startNum - bitVal) << 1;
n += bitVal ? 1 : 0;
for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
cout << (n >> (i - 1) & 1);
cout << endl;
if (!(n & testNum) && n != startNum)
r_nCr(n, bitVal, testNum);
if (bitVal && bitVal < testNum)
r_nCr(startNum, bitVal >> 1, testNum);
}
你可以在这里找到这是如何工作的解释。
作为迭代器对象实现的MetaTrader MQL4非常快速的组合。
代码很容易理解。
我对很多算法进行了基准测试,这个算法真的非常快——大约比大多数next_combination()函数快3倍。
class CombinationsIterator { private: int input_array[]; // 1 2 3 4 5 int index_array[]; // i j k int m_elements; // N int m_indices; // K public: CombinationsIterator(int &src_data[], int k) { m_indices = k; m_elements = ArraySize(src_data); ArrayCopy(input_array, src_data); ArrayResize(index_array, m_indices); // create initial combination (0..k-1) for (int i = 0; i < m_indices; i++) { index_array[i] = i; } } // https://stackoverflow.com/questions/5076695 // bool next_combination(int &item[], int k, int N) bool advance() { int N = m_elements; for (int i = m_indices - 1; i >= 0; --i) { if (index_array[i] < --N) { ++index_array[i]; for (int j = i + 1; j < m_indices; ++j) { index_array[j] = index_array[j - 1] + 1; } return true; } } return false; } void getItems(int &items[]) { // fill items[] from input array for (int i = 0; i < m_indices; i++) { items[i] = input_array[index_array[i]]; } } };
测试上述迭代器类的驱动程序:
//+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ // driver program to test above class #define N 5 #define K 3 void OnStart() { int myset[N] = {1, 2, 3, 4, 5}; int items[K]; CombinationsIterator comboIt(myset, K); do { comboIt.getItems(items); printf("%s", ArrayToString(items)); } while (comboIt.advance()); }
输出: 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5