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

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

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

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


当前回答

下面是一个使用宏的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)
...

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

其他回答

还有另一个递归解决方案(你应该能够使用字母而不是数字)使用堆栈,虽然比大多数更短:

stack = [] 
def choose(n,x):
   r(0,0,n+1,x)

def r(p, c, n,x):
   if x-c == 0:
      print stack
      return

   for i in range(p, n-(x-1)+c):
      stack.append(i)
      r(i+1,c+1,n,x)
      stack.pop()

4选3或者我想要从0到4的所有3种数字组合

choose(4,3) 

[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 2, 3]
[0, 2, 4]
[0, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]

另一种python递归解决方案。

def combination_indicies(n, k, j = 0, stack = []):   
    if len(stack) == k:            
        yield list(stack)
        return
        
    for i in range(j, n):
        stack.append(i)
        for x in combination_indicies(n, k, i + 1, stack):            
            yield x
        stack.pop()  
        
list(combination_indicies(5, 3))

输出:

[[0, 1, 2],
 [0, 1, 3],
 [0, 1, 4],
 [0, 2, 3],
 [0, 2, 4],
 [0, 3, 4],
 [1, 2, 3],
 [1, 2, 4],
 [1, 3, 4],
 [2, 3, 4]]

这里你有一个用c#编写的该算法的惰性评估版本:

    static bool nextCombination(int[] num, int n, int k)
    {
        bool finished, changed;

        changed = finished = false;

        if (k > 0)
        {
            for (int i = k - 1; !finished && !changed; i--)
            {
                if (num[i] < (n - 1) - (k - 1) + i)
                {
                    num[i]++;
                    if (i < k - 1)
                    {
                        for (int j = i + 1; j < k; j++)
                        {
                            num[j] = num[j - 1] + 1;
                        }
                    }
                    changed = true;
                }
                finished = (i == 0);
            }
        }

        return changed;
    }

    static IEnumerable Combinations<T>(IEnumerable<T> elements, int k)
    {
        T[] elem = elements.ToArray();
        int size = elem.Length;

        if (k <= size)
        {
            int[] numbers = new int[k];
            for (int i = 0; i < k; i++)
            {
                numbers[i] = i;
            }

            do
            {
                yield return numbers.Select(n => elem[n]);
            }
            while (nextCombination(numbers, size, k));
        }
    }

及测试部分:

    static void Main(string[] args)
    {
        int k = 3;
        var t = new[] { "dog", "cat", "mouse", "zebra"};

        foreach (IEnumerable<string> i in Combinations(t, k))
        {
            Console.WriteLine(string.Join(",", i));
        }
    }

希望这对你有帮助!


另一种版本,迫使所有前k个组合首先出现,然后是所有前k+1个组合,然后是所有前k+2个组合,等等。这意味着如果你对数组进行排序,最重要的在最上面,它会把它们逐渐扩展到下一个——只有在必须这样做的时候。

private static bool NextCombinationFirstsAlwaysFirst(int[] num, int n, int k)
{
    if (k > 1 && NextCombinationFirstsAlwaysFirst(num, num[k - 1], k - 1))
        return true;

    if (num[k - 1] + 1 == n)
        return false;

    ++num[k - 1];
    for (int i = 0; i < k - 1; ++i)
        num[i] = i;

    return true;
}

例如,如果你在k=3, n=5上运行第一个方法("nextCombination"),你会得到:

0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

但如果你跑

int[] nums = new int[k];
for (int i = 0; i < k; ++i)
    nums[i] = i;
do
{
    Console.WriteLine(string.Join(" ", nums));
}
while (NextCombinationFirstsAlwaysFirst(nums, n, k));

你会得到这个(为了清晰起见,我添加了空行):

0 1 2

0 1 3
0 2 3
1 2 3

0 1 4
0 2 4
1 2 4
0 3 4
1 3 4
2 3 4

它只在必须添加时才添加“4”,而且在添加“4”之后,它只在必须添加时再添加“3”(在执行01、02、12之后)。

递归,一个很简单的答案,combo,在Free Pascal中。

    procedure combinata (n, k :integer; producer :oneintproc);

        procedure combo (ndx, nbr, len, lnd :integer);
        begin
            for nbr := nbr to len do begin
                productarray[ndx] := nbr;
                if len < lnd then
                    combo(ndx+1,nbr+1,len+1,lnd)
                else
                    producer(k);
            end;
        end;

    begin
        combo (0, 0, n-k, n-1);
    end;

“producer”处理为每个组合生成的产品数组。

我想提出我的解决方案。在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);
}