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

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

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

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


当前回答

Python中的简短示例:

def comb(sofar, rest, n):
    if n == 0:
        print sofar
    else:
        for i in range(len(rest)):
            comb(sofar + rest[i], rest[i+1:], n-1)

>>> comb("", "abcde", 3)
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde

为了解释,递归方法用下面的例子描述:

示例:A B C D E 3的所有组合是:

A与其余2的所有组合(B C D E) B与其余2的所有组合(C D E) C与其余2的所有组合(D E)

其他回答

我可以给出这个问题的递归Python解决方案吗?

def choose_iter(elements, length):
    for i in xrange(len(elements)):
        if length == 1:
            yield (elements[i],)
        else:
            for next in choose_iter(elements[i+1:], length-1):
                yield (elements[i],) + next
def choose(l, k):
    return list(choose_iter(l, k))

使用示例:

>>> len(list(choose_iter("abcdefgh",3)))
56

我喜欢它的简洁。

这个答案怎么样……这将打印所有长度为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;
 }

这是一个为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);
}

像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   

Here's some simple code that prints all the C(n,m) combinations. It works by initializing and moving a set of array indices that point to next valid combination. The indices are initialized to point to the lowest m indices (lexicographically the smallest combination). Then on, starting with the m-th index, we try to move the indices forward. if an index has reached its limit, we try the previous index (all the way down to index 1). If we can move an index forward, then we reset all greater indices.

m=(rand()%n)+1; // m will vary from 1 to n

for (i=0;i<n;i++) a[i]=i+1;

// we want to print all possible C(n,m) combinations of selecting m objects out of n
printf("Printing C(%d,%d) possible combinations ...\n", n,m);

// This is an adhoc algo that keeps m pointers to the next valid combination
for (i=0;i<m;i++) p[i]=i; // the p[.] contain indices to the a vector whose elements constitute next combination

done=false;
while (!done)
{
    // print combination
    for (i=0;i<m;i++) printf("%2d ", a[p[i]]);
    printf("\n");

    // update combination
    // method: start with p[m-1]. try to increment it. if it is already at the end, then try moving p[m-2] ahead.
    // if this is possible, then reset p[m-1] to 1 more than (the new) p[m-2].
    // if p[m-2] can not also be moved, then try p[m-3]. move that ahead. then reset p[m-2] and p[m-1].
    // repeat all the way down to p[0]. if p[0] can not also be moved, then we have generated all combinations.
    j=m-1;
    i=1;
    move_found=false;
    while ((j>=0) && !move_found)
    {
        if (p[j]<(n-i)) 
        {
            move_found=true;
            p[j]++; // point p[j] to next index
            for (k=j+1;k<m;k++)
            {
                p[k]=p[j]+(k-j);
            }
        }
        else
        {
            j--;
            i++;
        }
    }
    if (!move_found) done=true;
}