我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
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网站上发布了一个类似于这个问题的挑战,在那里你可以找到我的链接和其他一些解决方案。
其他回答
下面是一个使用宏的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)
...
由于默认情况下不存储组合,因此存储空间保持在最小值。选择主体代码而不是存储所有结果的可能性也提供了更大的灵活性。
我们可以用比特的概念来做这个。假设我们有一个字符串“abc”,我们想要所有长度为2的元素的组合(即“ab”,“ac”,“bc”)。
我们可以在1到2^n(排他性)的数字中找到集合位。这里是1到7,只要我们设置了bits = 2,我们就可以从string中输出相应的值。
例如:
1 - 001 二零零一 3011 ->印刷ab (str[0], str[1]) 四到一百。 5 - 101 ->打印ac (str[0], str[2]) 6 - 110 ->印刷ab (str[1], str[2]) 7 - 111。
代码示例:
public class StringCombinationK {
static void combk(String s , int k){
int n = s.length();
int num = 1<<n;
int j=0;
int count=0;
for(int i=0;i<num;i++){
if (countSet(i)==k){
setBits(i,j,s);
count++;
System.out.println();
}
}
System.out.println(count);
}
static void setBits(int i,int j,String s){ // print the corresponding string value,j represent the index of set bit
if(i==0){
return;
}
if(i%2==1){
System.out.print(s.charAt(j));
}
setBits(i/2,j+1,s);
}
static int countSet(int i){ //count number of set bits
if( i==0){
return 0;
}
return (i%2==0? 0:1) + countSet(i/2);
}
public static void main(String[] arhs){
String s = "abcdefgh";
int k=3;
combk(s,k);
}
}
这是我想出的解决这个问题的算法。它是用c++编写的,但是可以适应几乎任何支持位操作的语言。
void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const 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);
}
你可以在这里看到它如何工作的解释。
一个简洁的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);
简单但缓慢的c++回溯算法。
#include <iostream>
void backtrack(int* numbers, int n, int k, int i, int s)
{
if (i == k)
{
for (int j = 0; j < k; ++j)
{
std::cout << numbers[j];
}
std::cout << std::endl;
return;
}
if (s > n)
{
return;
}
numbers[i] = s;
backtrack(numbers, n, k, i + 1, s + 1);
backtrack(numbers, n, k, i, s + 1);
}
int main(int argc, char* argv[])
{
int n = 5;
int k = 3;
int* numbers = new int[k];
backtrack(numbers, n, k, 0, 1);
delete[] numbers;
return 0;
}