Haskell中的简单递归算法

import Data.List

combinations 0 lst = [[]]
combinations n lst = do
    (x:xs) <- tails lst
    rest   <- combinations (n-1) xs
    return $ x : rest

我们首先定义特殊情况，即选择零元素。它产生一个单一的结果，这是一个空列表(即一个包含空列表的列表)。

对于n> 0, x遍历列表中的每一个元素xs是x之后的每一个元素。

Rest通过对组合的递归调用从xs中选取n - 1个元素。该函数的最终结果是一个列表，其中每个元素都是x: rest(即对于x和rest的每个不同值，x为头部，rest为尾部的列表)。

> combinations 3 "abcde"
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]

当然，由于Haskell是懒惰的，列表是根据需要逐渐生成的，因此您可以部分计算指数级的大组合。

> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"
> take 10 c
["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn",
 "abcdefgo","abcdefgp","abcdefgq"]

这是一个优雅的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 :: _}
    }
}

还有另一个递归解决方案(你应该能够使用字母而不是数字)使用堆栈，虽然比大多数更短:

stack = [] 
def choose(n,x):
   r(0,0,n+1,x)

def r(p, c, n,x):
   if x-c == 0:
      print stack
      return

   for i in range(p, n-(x-1)+c):
      stack.append(i)
      r(i+1,c+1,n,x)
      stack.pop()

4选3或者我想要从0到4的所有3种数字组合

choose(4,3) 

[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 2, 3]
[0, 2, 4]
[0, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]

这是一个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);
}

你可以在这里找到这是如何工作的解释。

我的实现在c/c++

#include <unistd.h>
#include <stdio.h>
#include <iconv.h>
#include <string.h>
#include <errno.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
    int opt = -1, min_len = 0, max_len = 0;
    char ofile[256], fchar[2], tchar[2];
    ofile[0] = 0;
    fchar[0] = 0;
    tchar[0] = 0;
    while((opt = getopt(argc, argv, "o:f:t:l:L:")) != -1)
    {
            switch(opt)
            {
                    case 'o':
                    strncpy(ofile, optarg, 255);
                    break;
                    case 'f':
                    strncpy(fchar, optarg, 1);
                    break;
                    case 't':
                    strncpy(tchar, optarg, 1);
                    break;
                    case 'l':
                    min_len = atoi(optarg);
                    break;
                    case 'L':
                    max_len = atoi(optarg);
                    break;
                    default:
                    printf("usage: %s -oftlL\n\t-o output file\n\t-f from char\n\t-t to char\n\t-l min seq len\n\t-L max seq len", argv[0]);
            }
    }
if(max_len < 1)
{
    printf("error, length must be more than 0\n");
    return 1;
}
if(min_len > max_len)
{
    printf("error, max length must be greater or equal min_length\n");
    return 1;
}
if((int)fchar[0] > (int)tchar[0])
{
    printf("error, invalid range specified\n");
    return 1;
}
FILE *out = fopen(ofile, "w");
if(!out)
{
    printf("failed to open input file with error: %s\n", strerror(errno));
    return 1;
}
int cur_len = min_len;
while(cur_len <= max_len)
{
    char buf[cur_len];
    for(int i = 0; i < cur_len; i++)
        buf[i] = fchar[0];
    fwrite(buf, cur_len, 1, out);
    fwrite("\n", 1, 1, out);
    while(buf[0] != (tchar[0]+1))
    {
        while(buf[cur_len-1] < tchar[0])
        {
            (int)buf[cur_len-1]++;
            fwrite(buf, cur_len, 1, out);
            fwrite("\n", 1, 1, out);
        }
        if(cur_len < 2)
            break;
        if(buf[0] == tchar[0])
        {
            bool stop = true;
            for(int i = 1; i < cur_len; i++)
            {
                if(buf[i] != tchar[0])
                {
                    stop = false;
                    break;
                }
            }
            if(stop)
                break;
        }
        int u = cur_len-2;
        for(; u>=0 && buf[u] >= tchar[0]; u--)
            ;
        (int)buf[u]++;
        for(int i = u+1; i < cur_len; i++)
            buf[i] = fchar[0];
        fwrite(buf, cur_len, 1, out);
        fwrite("\n", 1, 1, out);
    }
    cur_len++;
}
fclose(out);
return 0;
}

这里我的实现在c++，它写所有的组合到指定的文件，但行为可以改变，我在生成各种字典，它接受最小和最大长度和字符范围，目前只有ANSI支持，它足以满足我的需求

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