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

假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:

8! / ((8 - 3)! * 3!) = 56

数组(或单词),每个数组由3个字母组成。


当前回答

c#简单算法。 (我发布它是因为我试图使用你们上传的那个,但由于某种原因我无法编译它——扩展一个类?所以我自己写了一个,以防别人遇到和我一样的问题)。 顺便说一下,除了基本的编程,我对c#没什么兴趣,但是这个工作得很好。

public static List<List<int>> GetSubsetsOfSizeK(List<int> lInputSet, int k)
        {
            List<List<int>> lSubsets = new List<List<int>>();
            GetSubsetsOfSizeK_rec(lInputSet, k, 0, new List<int>(), lSubsets);
            return lSubsets;
        }

public static void GetSubsetsOfSizeK_rec(List<int> lInputSet, int k, int i, List<int> lCurrSet, List<List<int>> lSubsets)
        {
            if (lCurrSet.Count == k)
            {
                lSubsets.Add(lCurrSet);
                return;
            }

            if (i >= lInputSet.Count)
                return;

            List<int> lWith = new List<int>(lCurrSet);
            List<int> lWithout = new List<int>(lCurrSet);
            lWith.Add(lInputSet[i++]);

            GetSubsetsOfSizeK_rec(lInputSet, k, i, lWith, lSubsets);
            GetSubsetsOfSizeK_rec(lInputSet, k, i, lWithout, lSubsets);
        }

GetSubsetsOfSizeK(set of type List<int>, integer k)

您可以修改它以遍历您正在处理的任何内容。

好运!

其他回答

像Andrea Ambu一样用Python写的,但不是硬编码来选择三个。

def combinations(list, k):
    """Choose combinations of list, choosing k elements(no repeats)"""
    if len(list) < k:
        return []
    else:
        seq = [i for i in range(k)]
        while seq:
            print [list[index] for index in seq]
            seq = get_next_combination(len(list), k, seq)

def get_next_combination(num_elements, k, seq):
        index_to_move = find_index_to_move(num_elements, seq)
        if index_to_move == None:
            return None
        else:
            seq[index_to_move] += 1

            #for every element past this sequence, move it down
            for i, elem in enumerate(seq[(index_to_move+1):]):
                seq[i + 1 + index_to_move] = seq[index_to_move] + i + 1

            return seq

def find_index_to_move(num_elements, seq):
        """Tells which index should be moved"""
        for rev_index, elem in enumerate(reversed(seq)):
            if elem < (num_elements - rev_index - 1):
                return len(seq) - rev_index - 1
        return None   

《计算机编程艺术,卷4A:组合算法,第1部分》第7.2.1.3节中算法L(字典组合)的C代码:

#include <stdio.h>
#include <stdlib.h>

void visit(int* c, int t) 
{
  // for (int j = 1; j <= t; j++)
  for (int j = t; j > 0; j--)
    printf("%d ", c[j]);
  printf("\n");
}

int* initialize(int n, int t) 
{
  // c[0] not used
  int *c = (int*) malloc((t + 3) * sizeof(int));

  for (int j = 1; j <= t; j++)
    c[j] = j - 1;
  c[t+1] = n;
  c[t+2] = 0;
  return c;
}

void comb(int n, int t) 
{
  int *c = initialize(n, t);
  int j;

  for (;;) {
    visit(c, t);
    j = 1;
    while (c[j]+1 == c[j+1]) {
      c[j] = j - 1;
      ++j;
    }
    if (j > t) 
      return;
    ++c[j];
  }
  free(c);
}

int main(int argc, char *argv[])
{
  comb(5, 3);
  return 0;
}

这是我想出的解决这个问题的算法。它是用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);
}

你可以在这里看到它如何工作的解释。

简单但缓慢的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;
}

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