Lisp宏为所有值r(每次取)生成代码

(defmacro txaat (some-list taken-at-a-time)
  (let* ((vars (reverse (truncate-list '(a b c d e f g h i j) taken-at-a-time))))
    `(
      ,@(loop for i below taken-at-a-time 
           for j in vars 
           with nested = nil 
           finally (return nested) 
           do
             (setf 
              nested 
              `(loop for ,j from
                    ,(if (< i (1- (length vars)))
                         `(1+ ,(nth (1+ i) vars))
                         0)
                  below (- (length ,some-list) ,i)
                    ,@(if (equal i 0) 
                          `(collect 
                               (list
                                ,@(loop for k from (1- taken-at-a-time) downto 0
                                     append `((nth ,(nth k vars) ,some-list)))))
                          `(append ,nested))))))))

So,

CL-USER> (macroexpand-1 '(txaat '(a b c d) 1))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 1)
    COLLECT (LIST (NTH A '(A B C D))))
T
CL-USER> (macroexpand-1 '(txaat '(a b c d) 2))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 2)
      APPEND (LOOP FOR B FROM (1+ A) TO (- (LENGTH '(A B C D)) 1)
                   COLLECT (LIST (NTH A '(A B C D)) (NTH B '(A B C D)))))
T
CL-USER> (macroexpand-1 '(txaat '(a b c d) 3))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 3)
      APPEND (LOOP FOR B FROM (1+ A) TO (- (LENGTH '(A B C D)) 2)
                   APPEND (LOOP FOR C FROM (1+ B) TO (- (LENGTH '(A B C D)) 1)
                                COLLECT (LIST (NTH A '(A B C D))
                                              (NTH B '(A B C D))
                                              (NTH C '(A B C D))))))
T

CL-USER> 

And,

CL-USER> (txaat '(a b c d) 1)
((A) (B) (C) (D))
CL-USER> (txaat '(a b c d) 2)
((A B) (A C) (A D) (B C) (B D) (C D))
CL-USER> (txaat '(a b c d) 3)
((A B C) (A B D) (A C D) (B C D))
CL-USER> (txaat '(a b c d) 4)
((A B C D))
CL-USER> (txaat '(a b c d) 5)
NIL
CL-USER> (txaat '(a b c d) 0)
NIL
CL-USER> 

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

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])。没有这个条件，你得到的是变化而不是组合。

在c#中:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
  return k == 0 ? new[] { new T[0] } :
    elements.SelectMany((e, i) =>
      elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}

用法:

var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);

结果:

123
124
125
134
135
145
234
235
245
345

下面是一个coffeescript实现

combinations: (list, n) ->
        permuations = Math.pow(2, list.length) - 1
        out = []
        combinations = []

        while permuations
            out = []

            for i in [0..list.length]
                y = ( 1 << i )
                if( y & permuations and (y isnt permuations))
                    out.push(list[i])

            if out.length <= n and out.length > 0
                combinations.push(out)

            permuations--

        return combinations