我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。

假设您提供了一个包含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网站上发布了一个类似于这个问题的挑战,在那里你可以找到我的链接和其他一些解决方案。

其他回答

下面是一个简单易懂的递归c++解决方案:

#include<vector>
using namespace std;

template<typename T>
void ksubsets(const vector<T>& arr, unsigned left, unsigned idx,
    vector<T>& lst, vector<vector<T>>& res)
{
    if (left < 1) {
        res.push_back(lst);
        return;
    }
    for (unsigned i = idx; i < arr.size(); i++) {
        lst.push_back(arr[i]);
        ksubsets(arr, left - 1, i + 1, lst, res);
        lst.pop_back();
    }
}

int main()
{
    vector<int> arr = { 1, 2, 3, 4, 5 };
    unsigned left = 3;
    vector<int> lst;
    vector<vector<int>> res;
    ksubsets<int>(arr, left, 0, lst, res);
    // now res has all the combinations
}

下面是Clojure版本,它使用了我在OCaml实现答案中描述的相同算法:

(defn select
  ([items]
     (select items 0 (inc (count items))))
  ([items n1 n2]
     (reduce concat
             (map #(select % items)
                  (range n1 (inc n2)))))
  ([n items]
     (let [
           lmul (fn [a list-of-lists-of-bs]
                     (map #(cons a %) list-of-lists-of-bs))
           ]
       (if (= n (count items))
         (list items)
         (if (empty? items)
           items
           (concat
            (select n (rest items))
            (lmul (first items) (select (dec n) (rest items))))))))) 

它提供了三种调用方法:

(a)按问题要求,选出n项:

  user=> (count (select 3 "abcdefgh"))
  56

(b) n1至n2个选定项目:

user=> (select '(1 2 3 4) 2 3)
((3 4) (2 4) (2 3) (1 4) (1 3) (1 2) (2 3 4) (1 3 4) (1 2 4) (1 2 3))

(c)在0至所选项目的集合大小之间:

user=> (select '(1 2 3))
(() (3) (2) (1) (2 3) (1 3) (1 2) (1 2 3))

这是一个优雅的Scala通用实现,如99个Scala问题所述。

object P26 {
  def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = 
    ls match {
      case Nil => Nil
      case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)
    }

  def combinations[A](n: Int, ls: List[A]): List[List[A]] =
    if (n == 0) List(Nil)
    else flatMapSublists(ls) { sl =>
      combinations(n - 1, sl.tail) map {sl.head :: _}
    }
}

我已经编写了一个类来处理处理二项式系数的常见函数,这是您的问题属于的问题类型。它执行以下任务:

Outputs all the K-indexes in a nice format for any N choose K to a file. The K-indexes can be substituted with more descriptive strings or letters. This method makes solving this type of problem quite trivial. Converts the K-indexes to the proper index of an entry in the sorted binomial coefficient table. This technique is much faster than older published techniques that rely on iteration. It does this by using a mathematical property inherent in Pascal's Triangle. My paper talks about this. I believe I am the first to discover and publish this technique, but I could be wrong. Converts the index in a sorted binomial coefficient table to the corresponding K-indexes. Uses Mark Dominus method to calculate the binomial coefficient, which is much less likely to overflow and works with larger numbers. The class is written in .NET C# and provides a way to manage the objects related to the problem (if any) by using a generic list. The constructor of this class takes a bool value called InitTable that when true will create a generic list to hold the objects to be managed. If this value is false, then it will not create the table. The table does not need to be created in order to perform the 4 above methods. Accessor methods are provided to access the table. There is an associated test class which shows how to use the class and its methods. It has been extensively tested with 2 cases and there are no known bugs.

要了解这个类并下载代码,请参见将二项式系数表化。

将这个类转换为c++应该不难。

遵循Haskell代码同时计算组合数和组合,由于Haskell的惰性,您可以得到其中的一部分而无需计算另一部分。

import Data.Semigroup
import Data.Monoid

data Comb = MkComb {count :: Int, combinations :: [[Int]]} deriving (Show, Eq, Ord)

instance Semigroup Comb where
    (MkComb c1 cs1) <> (MkComb c2 cs2) = MkComb (c1 + c2) (cs1 ++ cs2)

instance Monoid Comb where
    mempty = MkComb 0 []

addElem :: Comb -> Int -> Comb
addElem (MkComb c cs) x = MkComb c (map (x :) cs)

comb :: Int -> Int -> Comb
comb n k | n < 0 || k < 0 = error "error in `comb n k`, n and k should be natural number"
comb n k | k == 0 || k == n = MkComb 1 [(take k [k-1,k-2..0])]
comb n k | n < k = mempty
comb n k = comb (n-1) k <> (comb (n-1) (k-1) `addElem` (n-1))

它是这样工作的:

*Main> comb 0 1
MkComb {count = 0, combinations = []}

*Main> comb 0 0
MkComb {count = 1, combinations = [[]]}

*Main> comb 1 1
MkComb {count = 1, combinations = [[0]]}

*Main> comb 4 2
MkComb {count = 6, combinations = [[1,0],[2,0],[2,1],[3,0],[3,1],[3,2]]}

*Main> count (comb 10 5)
252