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

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

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

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


当前回答

下面是一个方法,它从一个随机长度的字符串中给出指定大小的所有组合。类似于昆玛斯的解,但适用于不同的输入和k。

代码可以更改为换行,即'dab'从输入'abcd' w k=3。

public void run(String data, int howMany){
    choose(data, howMany, new StringBuffer(), 0);
}


//n choose k
private void choose(String data, int k, StringBuffer result, int startIndex){
    if (result.length()==k){
        System.out.println(result.toString());
        return;
    }

    for (int i=startIndex; i<data.length(); i++){
        result.append(data.charAt(i));
        choose(data,k,result, i+1);
        result.setLength(result.length()-1);
    }
}

"abcde"的输出:

ABC abd ace ade BCD bce bde cde

其他回答

这是我对javascript的贡献(没有递归)

set = ["q0", "q1", "q2", "q3"]
collector = []


function comb(num) {
  results = []
  one_comb = []
  for (i = set.length - 1; i >= 0; --i) {
    tmp = Math.pow(2, i)
    quotient = parseInt(num / tmp)
    results.push(quotient)
    num = num % tmp
  }
  k = 0
  for (i = 0; i < results.length; ++i)
    if (results[i]) {
      ++k
      one_comb.push(set[i])
    }
  if (collector[k] == undefined)
    collector[k] = []
  collector[k].push(one_comb)
}


sum = 0
for (i = 0; i < set.length; ++i)
  sum += Math.pow(2, i)
 for (ii = sum; ii > 0; --ii)
  comb(ii)
 cnt = 0
for (i = 1; i < collector.length; ++i) {
  n = 0
  for (j = 0; j < collector[i].length; ++j)
    document.write(++cnt, " - " + (++n) + " - ", collector[i][j], "<br>")
  document.write("<hr>")
}   
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表示必须从数组中的哪个位置开始选择。

在c++中,以下例程将生成range [first,last)之间的长度距离(first,k)的所有组合:

#include <algorithm>

template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Mark Nelson http://marknelson.us */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator i1 = first;
   Iterator i2 = last;
   ++i1;
   if (last == i1)
      return false;
   i1 = last;
   --i1;
   i1 = k;
   --i2;
   while (first != i1)
   {
      if (*--i1 < *i2)
      {
         Iterator j = k;
         while (!(*i1 < *j)) ++j;
         std::iter_swap(i1,j);
         ++i1;
         ++j;
         i2 = k;
         std::rotate(i1,j,last);
         while (last != j)
         {
            ++j;
            ++i2;
         }
         std::rotate(k,i2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

它可以这样使用:

#include <string>
#include <iostream>

int main()
{
    std::string s = "12345";
    std::size_t comb_size = 3;
    do
    {
        std::cout << std::string(s.begin(), s.begin() + comb_size) << std::endl;
    } while (next_combination(s.begin(), s.begin() + comb_size, s.end()));

    return 0;
}

这将打印以下内容:

123
124
125
134
135
145
234
235
245
345

另一个具有组合索引惰性生成的c#版本。这个版本维护了一个索引数组来定义所有值列表和当前组合值之间的映射,即在整个运行时不断使用O(k)额外的空间。该代码在O(k)时间内生成单个组合,包括第一个组合。

public static IEnumerable<T[]> Combinations<T>(this T[] values, int k)
{
    if (k < 0 || values.Length < k)
        yield break; // invalid parameters, no combinations possible

    // generate the initial combination indices
    var combIndices = new int[k];
    for (var i = 0; i < k; i++)
    {
        combIndices[i] = i;
    }

    while (true)
    {
        // return next combination
        var combination = new T[k];
        for (var i = 0; i < k; i++)
        {
            combination[i] = values[combIndices[i]];
        }
        yield return combination;

        // find first index to update
        var indexToUpdate = k - 1;
        while (indexToUpdate >= 0 && combIndices[indexToUpdate] >= values.Length - k + indexToUpdate)
        {
            indexToUpdate--;
        }

        if (indexToUpdate < 0)
            yield break; // done

        // update combination indices
        for (var combIndex = combIndices[indexToUpdate] + 1; indexToUpdate < k; indexToUpdate++, combIndex++)
        {
            combIndices[indexToUpdate] = combIndex;
        }
    }
}

测试代码:

foreach (var combination in new[] {'a', 'b', 'c', 'd', 'e'}.Combinations(3))
{
    System.Console.WriteLine(String.Join(" ", combination));
}

输出:

a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e

简短的java解决方案:

import java.util.Arrays;

public class Combination {
    public static void main(String[] args){
        String[] arr = {"A","B","C","D","E","F"};
        combinations2(arr, 3, 0, new String[3]);
    }

    static void combinations2(String[] arr, int len, int startPosition, String[] result){
        if (len == 0){
            System.out.println(Arrays.toString(result));
            return;
        }       
        for (int i = startPosition; i <= arr.length-len; i++){
            result[result.length - len] = arr[i];
            combinations2(arr, len-1, i+1, result);
        }
    }       
}

结果将是

[A, B, C]
[A, B, D]
[A, B, E]
[A, B, F]
[A, C, D]
[A, C, E]
[A, C, F]
[A, D, E]
[A, D, F]
[A, E, F]
[B, C, D]
[B, C, E]
[B, C, F]
[B, D, E]
[B, D, F]
[B, E, F]
[C, D, E]
[C, D, F]
[C, E, F]
[D, E, F]