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

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

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

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


当前回答

我们可以用比特的概念来做这个。假设我们有一个字符串“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);
    }
}

其他回答

static IEnumerable<string> Combinations(List<string> characters, int length)
{
    for (int i = 0; i < characters.Count; i++)
    {
        // only want 1 character, just return this one
        if (length == 1)
            yield return characters[i];

        // want more than one character, return this one plus all combinations one shorter
        // only use characters after the current one for the rest of the combinations
        else
            foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
                yield return characters[i] + next;
    }
}

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

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

现在又出现了祖辈COBOL,一种饱受诟病的语言。

让我们假设一个包含34个元素的数组,每个元素8个字节(完全是任意选择)。其思想是枚举所有可能的4元素组合,并将它们加载到一个数组中。

我们使用4个指标,每个指标代表4个组中的每个位置

数组是这样处理的:

    idx1 = 1
    idx2 = 2
    idx3 = 3
    idx4 = 4

我们把idx4从4变到最后。对于每个idx4,我们得到一个唯一的组合 四人一组。当idx4到达数组的末尾时,我们将idx3增加1,并将idx4设置为idx3+1。然后再次运行idx4到最后。我们以这种方式继续,分别增加idx3、idx2和idx1,直到idx1的位置距离数组末端小于4。算法就完成了。

1          --- pos.1
2          --- pos 2
3          --- pos 3
4          --- pos 4
5
6
7
etc.

第一次迭代:

1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
etc.

一个COBOL的例子:

01  DATA_ARAY.
    05  FILLER     PIC X(8)    VALUE  "VALUE_01".
    05  FILLER     PIC X(8)    VALUE  "VALUE_02".
  etc.
01  ARAY_DATA    OCCURS 34.
    05  ARAY_ITEM       PIC X(8).

01  OUTPUT_ARAY   OCCURS  50000   PIC X(32).

01   MAX_NUM   PIC 99 COMP VALUE 34.

01  INDEXXES  COMP.
    05  IDX1            PIC 99.
    05  IDX2            PIC 99.
    05  IDX3            PIC 99.
    05  IDX4            PIC 99.
    05  OUT_IDX   PIC 9(9).

01  WHERE_TO_STOP_SEARCH          PIC 99  COMP.

* Stop the search when IDX1 is on the third last array element:

COMPUTE WHERE_TO_STOP_SEARCH = MAX_VALUE - 3     

MOVE 1 TO IDX1

PERFORM UNTIL IDX1 > WHERE_TO_STOP_SEARCH
   COMPUTE IDX2 = IDX1 + 1
   PERFORM UNTIL IDX2 > MAX_NUM
      COMPUTE IDX3 = IDX2 + 1
      PERFORM UNTIL IDX3 > MAX_NUM
         COMPUTE IDX4 = IDX3 + 1
         PERFORM UNTIL IDX4 > MAX_NUM
            ADD 1 TO OUT_IDX
            STRING  ARAY_ITEM(IDX1)
                    ARAY_ITEM(IDX2)
                    ARAY_ITEM(IDX3)
                    ARAY_ITEM(IDX4)
                    INTO OUTPUT_ARAY(OUT_IDX)
            ADD 1 TO IDX4
         END-PERFORM
         ADD 1 TO IDX3
      END-PERFORM
      ADD 1 TO IDX2
   END_PERFORM
   ADD 1 TO IDX1
END-PERFORM.

在VB。Net,该算法从一组数字(PoolArray)中收集n个数字的所有组合。例如,从“8,10,20,33,41,44,47”中选择5个选项的所有组合。

Sub CreateAllCombinationsOfPicksFromPool(ByVal PicksArray() As UInteger, ByVal PicksIndex As UInteger, ByVal PoolArray() As UInteger, ByVal PoolIndex As UInteger)
    If PicksIndex < PicksArray.Length Then
        For i As Integer = PoolIndex To PoolArray.Length - PicksArray.Length + PicksIndex
            PicksArray(PicksIndex) = PoolArray(i)
            CreateAllCombinationsOfPicksFromPool(PicksArray, PicksIndex + 1, PoolArray, i + 1)
        Next
    Else
        ' completed combination. build your collections using PicksArray.
    End If
End Sub

        Dim PoolArray() As UInteger = Array.ConvertAll("8,10,20,33,41,44,47".Split(","), Function(u) UInteger.Parse(u))
        Dim nPicks as UInteger = 5
        Dim Picks(nPicks - 1) As UInteger
        CreateAllCombinationsOfPicksFromPool(Picks, 0, PoolArray, 0)

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"]