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

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

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

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


当前回答

我发现这个线程很有用,我想我会添加一个Javascript解决方案,你可以弹出到Firebug。取决于你的JS引擎,如果起始字符串很大,可能会花一点时间。

function string_recurse(active, rest) {
    if (rest.length == 0) {
        console.log(active);
    } else {
        string_recurse(active + rest.charAt(0), rest.substring(1, rest.length));
        string_recurse(active, rest.substring(1, rest.length));
    }
}
string_recurse("", "abc");

输出如下:

abc
ab
ac
a
bc
b
c

其他回答

现在又出现了祖辈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.

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

下面是一个使用宏的Lisp方法。这适用于Common Lisp,也适用于其他Lisp方言。

下面的代码创建了'n'个嵌套循环,并为列表lst中的'n'个元素的每个组合执行任意代码块(存储在body变量中)。变量var指向一个包含用于循环的变量的列表。

(defmacro do-combinations ((var lst num) &body body)
  (loop with syms = (loop repeat num collect (gensym))
        for i on syms
        for k = `(loop for ,(car i) on (cdr ,(cadr i))
                         do (let ((,var (list ,@(reverse syms)))) (progn ,@body)))
                then `(loop for ,(car i) on ,(if (cadr i) `(cdr ,(cadr i)) lst) do ,k)
        finally (return k)))

让我们看看…

(macroexpand-1 '(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p))))

(LOOP FOR #:G3217 ON '(1 2 3 4 5 6 7) DO
 (LOOP FOR #:G3216 ON (CDR #:G3217) DO
  (LOOP FOR #:G3215 ON (CDR #:G3216) DO
   (LOOP FOR #:G3214 ON (CDR #:G3215) DO
    (LET ((P (LIST #:G3217 #:G3216 #:G3215 #:G3214)))
     (PROGN (PPRINT (MAPCAR #'CAR P))))))))

(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p)))

(1 2 3 4)
(1 2 3 5)
(1 2 3 6)
...

由于默认情况下不存储组合,因此存储空间保持在最小值。选择主体代码而不是存储所有结果的可能性也提供了更大的灵活性。

在Python中,利用递归的优势和所有事情都是通过引用完成的事实。对于非常大的集合,这将占用大量内存,但其优点是初始集合可以是一个复杂的对象。它只会找到唯一的组合。

import copy

def find_combinations( length, set, combinations = None, candidate = None ):
    # recursive function to calculate all unique combinations of unique values
    # from [set], given combinations of [length].  The result is populated
    # into the 'combinations' list.
    #
    if combinations == None:
        combinations = []
    if candidate == None:
        candidate = []

    for item in set:
        if item in candidate:
            # this item already appears in the current combination somewhere.
            # skip it
            continue

        attempt = copy.deepcopy(candidate)
        attempt.append(item)
        # sorting the subset is what gives us completely unique combinations,
        # so that [1, 2, 3] and [1, 3, 2] will be treated as equals
        attempt.sort()

        if len(attempt) < length:
            # the current attempt at finding a new combination is still too
            # short, so add another item to the end of the set
            # yay recursion!
            find_combinations( length, set, combinations, attempt )
        else:
            # the current combination attempt is the right length.  If it
            # already appears in the list of found combinations then we'll
            # skip it.
            if attempt in combinations:
                continue
            else:
                # otherwise, we append it to the list of found combinations
                # and move on.
                combinations.append(attempt)
                continue
    return len(combinations)

你可以这样使用它。传递'result'是可选的,所以你可以用它来获取可能组合的数量…尽管这样做效率很低(最好通过计算来完成)。

size = 3
set = [1, 2, 3, 4, 5]
result = []

num = find_combinations( size, set, result ) 
print "size %d results in %d sets" % (size, num)
print "result: %s" % (result,)

您应该从测试数据中得到以下输出:

size 3 results in 10 sets
result: [[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]]

如果你的集合是这样的,它也会工作得很好:

set = [
    [ 'vanilla', 'cupcake' ],
    [ 'chocolate', 'pudding' ],
    [ 'vanilla', 'pudding' ],
    [ 'chocolate', 'cookie' ],
    [ 'mint', 'cookie' ]
]

下面是我最近用Java写的一段代码,它计算并返回从“outOf”元素中“num”元素的所有组合。

// author: Sourabh Bhat (heySourabh@gmail.com)

public class Testing
{
    public static void main(String[] args)
    {

// Test case num = 5, outOf = 8.

        int num = 5;
        int outOf = 8;
        int[][] combinations = getCombinations(num, outOf);
        for (int i = 0; i < combinations.length; i++)
        {
            for (int j = 0; j < combinations[i].length; j++)
            {
                System.out.print(combinations[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static int[][] getCombinations(int num, int outOf)
    {
        int possibilities = get_nCr(outOf, num);
        int[][] combinations = new int[possibilities][num];
        int arrayPointer = 0;

        int[] counter = new int[num];

        for (int i = 0; i < num; i++)
        {
            counter[i] = i;
        }
        breakLoop: while (true)
        {
            // Initializing part
            for (int i = 1; i < num; i++)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i] = counter[i - 1] + 1;
            }

            // Testing part
            for (int i = 0; i < num; i++)
            {
                if (counter[i] < outOf)
                {
                    continue;
                } else
                {
                    break breakLoop;
                }
            }

            // Innermost part
            combinations[arrayPointer] = counter.clone();
            arrayPointer++;

            // Incrementing part
            counter[num - 1]++;
            for (int i = num - 1; i >= 1; i--)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i - 1]++;
            }
        }

        return combinations;
    }

    private static int get_nCr(int n, int r)
    {
        if(r > n)
        {
            throw new ArithmeticException("r is greater then n");
        }
        long numerator = 1;
        long denominator = 1;
        for (int i = n; i >= r + 1; i--)
        {
            numerator *= i;
        }
        for (int i = 2; i <= n - r; i++)
        {
            denominator *= i;
        }

        return (int) (numerator / denominator);
    }
}