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

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

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

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


当前回答

基于java解决方案的短php算法返回k元素从n(二项式系数)的所有组合:

$array = array(1,2,3,4,5);

$array_result = NULL;

$array_general = NULL;

function combinations($array, $len, $start_position, $result_array, $result_len, &$general_array)
{
    if($len == 0)
    {
        $general_array[] = $result_array;
        return;
    }

    for ($i = $start_position; $i <= count($array) - $len; $i++)
    {
        $result_array[$result_len - $len] = $array[$i];
        combinations($array, $len-1, $i+1, $result_array, $result_len, $general_array);
    }
} 

combinations($array, 3, 0, $array_result, 3, $array_general);

echo "<pre>";
print_r($array_general);
echo "</pre>";

相同的解决方案,但在javascript:

var newArray = [1, 2, 3, 4, 5];
var arrayResult = [];
var arrayGeneral = [];

function combinations(newArray, len, startPosition, resultArray, resultLen, arrayGeneral) {
    if(len === 0) {
        var tempArray = [];
        resultArray.forEach(value => tempArray.push(value));
        arrayGeneral.push(tempArray);
        return;
    }
    for (var i = startPosition; i <= newArray.length - len; i++) {
        resultArray[resultLen - len] = newArray[i];
        combinations(newArray, len-1, i+1, resultArray, resultLen, arrayGeneral);
    }
} 

combinations(newArray, 3, 0, arrayResult, 3, arrayGeneral);

console.log(arrayGeneral);

其他回答

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

也许我错过了重点(你需要的是算法,而不是现成的解决方案),但看起来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)

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)

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

好运!

我们可以用比特的概念来做这个。假设我们有一个字符串“abc”,我们想要所有长度为2的元素的组合(即“ab”,“ac”,“bc”)。

我们可以在1到2^n(排他性)的数字中找到集合位。这里是1到7,只要我们设置了bits = 2,我们就可以从string中输出相应的值。

例如:

1 - 001 二零零一 3011 ->印刷ab (str[0], str[1]) 四到一百。 5 - 101 ->打印ac (str[0], str[2]) 6 - 110 ->印刷ab (str[1], str[2]) 7 - 111。

代码示例:

public class StringCombinationK {   
    static void combk(String s , int k){
        int n = s.length();
        int num = 1<<n;
        int j=0;
        int count=0;

        for(int i=0;i<num;i++){
            if (countSet(i)==k){
                setBits(i,j,s);
                count++;
                System.out.println();
            }
        }

        System.out.println(count);
    }

    static void setBits(int i,int j,String s){ // print the corresponding string value,j represent the index of set bit
        if(i==0){
            return;
        }

        if(i%2==1){
            System.out.print(s.charAt(j));                  
        }

        setBits(i/2,j+1,s);
    }

    static int countSet(int i){ //count number of set bits
        if( i==0){
            return 0;
        }

        return (i%2==0? 0:1) + countSet(i/2);
    }

    public static void main(String[] arhs){
        String s = "abcdefgh";
        int k=3;
        combk(s,k);
    }
}

简短快速的c#实现

public static IEnumerable<IEnumerable<T>> Combinations<T>(IEnumerable<T> elements, int k)
{
    return Combinations(elements.Count(), k).Select(p => p.Select(q => elements.ElementAt(q)));                
}      

public static List<int[]> Combinations(int setLenght, int subSetLenght) //5, 3
{
    var result = new List<int[]>();

    var lastIndex = subSetLenght - 1;
    var dif = setLenght - subSetLenght;
    var prevSubSet = new int[subSetLenght];
    var lastSubSet = new int[subSetLenght];
    for (int i = 0; i < subSetLenght; i++)
    {
        prevSubSet[i] = i;
        lastSubSet[i] = i + dif;
    }

    while(true)
    {
        //add subSet ad result set
        var n = new int[subSetLenght];
        for (int i = 0; i < subSetLenght; i++)
            n[i] = prevSubSet[i];

        result.Add(n);

        if (prevSubSet[0] >= lastSubSet[0])
            break;

        //start at index 1 because index 0 is checked and breaking in the current loop
        int j = 1;
        for (; j < subSetLenght; j++)
        {
            if (prevSubSet[j] >= lastSubSet[j])
            {
                prevSubSet[j - 1]++;

                for (int p = j; p < subSetLenght; p++)
                    prevSubSet[p] = prevSubSet[p - 1] + 1;

                break;
            }
        }

        if (j > lastIndex)
            prevSubSet[lastIndex]++;
    }

    return result;
}