最近在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

void combine(char a[], int N, int M, int m, int start, char result[]) {
    if (0 == m) {
        for (int i = M - 1; i >= 0; i--)
            std::cout << result[i];
        std::cout << std::endl;
        return;
    }
    for (int i = start; i < (N - m + 1); i++) {
        result[m - 1] = a[i];
        combine(a, N, M, m-1, i+1, result);
    }
}

void combine(char a[], int N, int M) {
    char *result = new char[M];
    combine(a, N, M, M, 0, result);
    delete[] result;
}

在第一个函数中，m表示还需要选择多少个，start表示必须从数组中的哪个位置开始选择。

下面的递归算法从有序集中选取所有k元素组合:

选择组合中的第一个元素I 将I与从大于I的元素集中递归选择的k-1个元素的组合组合。

对集合中的每一个i进行上述迭代。

为了避免重复，您必须选择比i大的其余元素。这样[3,5]将只被选中一次，即[3]与[5]结合，而不是两次(该条件消除了[5]+[3])。没有这个条件，你得到的是变化而不是组合。

也许我错过了重点(你需要的是算法，而不是现成的解决方案)，但看起来scala已经开箱即用了(现在):

def combis(str:String, k:Int):Array[String] = {
  str.combinations(k).toArray 
}

使用这样的方法:

  println(combis("abcd",2).toList)

会产生:

  List(ab, ac, ad, bc, bd, cd)

Clojure版本:

(defn comb [k l]
  (if (= 1 k) (map vector l)
      (apply concat
             (map-indexed
              #(map (fn [x] (conj x %2))
                    (comb (dec k) (drop (inc %1) l)))
              l))))

下面是我的Scala解决方案:

def combinations[A](s: List[A], k: Int): List[List[A]] = 
  if (k > s.length) Nil
  else if (k == 1) s.map(List(_))
  else combinations(s.tail, k - 1).map(s.head :: _) ::: combinations(s.tail, k)