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

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

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

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


当前回答

我想提出我的解决方案。在next中没有递归调用,也没有嵌套循环。 代码的核心是next()方法。

public class Combinations {
    final int pos[];
    final List<Object> set;

    public Combinations(List<?> l, int k) {
        pos = new int[k];
        set=new ArrayList<Object>(l);
        reset();
    }
    public void reset() {
        for (int i=0; i < pos.length; ++i) pos[i]=i;
    }
    public boolean next() {
        int i = pos.length-1;
        for (int maxpos = set.size()-1; pos[i] >= maxpos; --maxpos) {
            if (i==0) return false;
            --i;
        }
        ++pos[i];
        while (++i < pos.length)
            pos[i]=pos[i-1]+1;
        return true;
    }

    public void getSelection(List<?> l) {
        @SuppressWarnings("unchecked")
        List<Object> ll = (List<Object>)l;
        if (ll.size()!=pos.length) {
            ll.clear();
            for (int i=0; i < pos.length; ++i)
                ll.add(set.get(pos[i]));
        }
        else {
            for (int i=0; i < pos.length; ++i)
                ll.set(i, set.get(pos[i]));
        }
    }
}

用法示例:

static void main(String[] args) {
    List<Character> l = new ArrayList<Character>();
    for (int i=0; i < 32; ++i) l.add((char)('a'+i));
    Combinations comb = new Combinations(l,5);
    int n=0;
    do {
        ++n;
        comb.getSelection(l);
        //Log.debug("%d: %s", n, l.toString());
    } while (comb.next());
    Log.debug("num = %d", n);
}

其他回答

短快C实现

#include <stdio.h>

void main(int argc, char *argv[]) {
  const int n = 6; /* The size of the set; for {1, 2, 3, 4} it's 4 */
  const int p = 4; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
  int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */

  int i = 0;
  for (int j = 0; j <= n; j++) comb[j] = 0;
  while (i >= 0) {
    if (comb[i] < n + i - p + 1) {
       comb[i]++;
       if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); }
       else            { comb[++i] = comb[i - 1]; }
    } else i--; }
}

要查看它有多快,请使用这段代码并测试它

#include <time.h>
#include <stdio.h>

void main(int argc, char *argv[]) {
  const int n = 32; /* The size of the set; for {1, 2, 3, 4} it's 4 */
  const int p = 16; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
  int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */

  int c = 0; int i = 0;
  for (int j = 0; j <= n; j++) comb[j] = 0;
  while (i >= 0) {
    if (comb[i] < n + i - p + 1) {
       comb[i]++;
       /* if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); } */
       if (i == p - 1) c++;
       else            { comb[++i] = comb[i - 1]; }
    } else i--; }
  printf("%d!%d == %d combination(s) in %15.3f second(s)\n ", p, n, c, clock()/1000.0);
}

使用cmd.exe (windows)测试:

Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.

c:\Program Files\lcc\projects>combination
16!32 == 601080390 combination(s) in          5.781 second(s)

c:\Program Files\lcc\projects>

祝你有愉快的一天。

这是一个为nCk生成组合的递归程序。假设集合中的元素从1到n

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

int nCk(int n,int loopno,int ini,int *a,int k)
{
    static int count=0;
    int i;
    loopno--;
    if(loopno<0)
    {
        a[k-1]=ini;
        for(i=0;i<k;i++)
        {
            printf("%d,",a[i]);
        }
        printf("\n");
        count++;
        return 0;
    }
    for(i=ini;i<=n-loopno-1;i++)
    {
        a[k-1-loopno]=i+1;
        nCk(n,loopno,i+1,a,k);
    }
    if(ini==0)
    return count;
    else
    return 0;
}

void main()
{
    int n,k,*a,count;
    printf("Enter the value of n and k\n");
    scanf("%d %d",&n,&k);
    a=(int*)malloc(k*sizeof(int));
    count=nCk(n,k,0,a,k);
    printf("No of combinations=%d\n",count);
}

这个答案怎么样……这将打印所有长度为3的组合…它可以推广到任何长度… 工作代码…

#include<iostream>
#include<string>
using namespace std;

void combination(string a,string dest){
int l = dest.length();
if(a.empty() && l  == 3 ){
 cout<<dest<<endl;}
else{
  if(!a.empty() && dest.length() < 3 ){
     combination(a.substr(1,a.length()),dest+a[0]);}
  if(!a.empty() && dest.length() <= 3 ){
      combination(a.substr(1,a.length()),dest);}
 }

 }

 int main(){
 string demo("abcd");
 combination(demo,"");
 return 0;
 }

作为迭代器对象实现的MetaTrader MQL4非常快速的组合。

代码很容易理解。

我对很多算法进行了基准测试,这个算法真的非常快——大约比大多数next_combination()函数快3倍。

class CombinationsIterator { private: int input_array[]; // 1 2 3 4 5 int index_array[]; // i j k int m_elements; // N int m_indices; // K public: CombinationsIterator(int &src_data[], int k) { m_indices = k; m_elements = ArraySize(src_data); ArrayCopy(input_array, src_data); ArrayResize(index_array, m_indices); // create initial combination (0..k-1) for (int i = 0; i < m_indices; i++) { index_array[i] = i; } } // https://stackoverflow.com/questions/5076695 // bool next_combination(int &item[], int k, int N) bool advance() { int N = m_elements; for (int i = m_indices - 1; i >= 0; --i) { if (index_array[i] < --N) { ++index_array[i]; for (int j = i + 1; j < m_indices; ++j) { index_array[j] = index_array[j - 1] + 1; } return true; } } return false; } void getItems(int &items[]) { // fill items[] from input array for (int i = 0; i < m_indices; i++) { items[i] = input_array[index_array[i]]; } } };

测试上述迭代器类的驱动程序:

//+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ // driver program to test above class #define N 5 #define K 3 void OnStart() { int myset[N] = {1, 2, 3, 4, 5}; int items[K]; CombinationsIterator comboIt(myset, K); do { comboIt.getItems(items); printf("%s", ArrayToString(items)); } while (comboIt.advance()); }

输出: 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5

下面的递归算法从有序集中选取所有k元素组合:

选择组合中的第一个元素I 将I与从大于I的元素集中递归选择的k-1个元素的组合组合。

对集合中的每一个i进行上述迭代。

为了避免重复,您必须选择比i大的其余元素。这样[3,5]将只被选中一次,即[3]与[5]结合,而不是两次(该条件消除了[5]+[3])。没有这个条件,你得到的是变化而不是组合。