algorithm - 组合递归 - 算法从n返回k个元素的所有组合




数组的所有组合 (20)

我想写一个函数,它将一个字母数组作为参数和一些要选择的字母。

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

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

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


Clojure版本:

(defn comb [k l]
  (if (= 1 k) (map vector l)
      (apply concat
             (map-indexed
              #(map (fn [x] (conj x %2))
                    (comb (dec k) (drop (inc %1) l)))
              l))))

Haskell中的简单递归算法

import Data.List

combinations 0 lst = [[]]
combinations n lst = do
    (x:xs) <- tails lst
    rest   <- combinations (n-1) xs
    return $ x : rest

我们首先定义特殊情况,即选择零元素。 它产生一个单一的结果,这是一个空的列表(即包含一个空列表的列表)。

对于n> 0, x遍历列表中的每个元素, xsx之后的每个元素。

通过递归调用combinations restxs选取n - 1元素。 该函数的最终结果是一个列表,其中每个元素都是x : rest (即以x为头部并以尾部为rest的列表)为每个不同的x值和rest值。

> combinations 3 "abcde"
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]

当然,由于Haskell是懒惰的,这个列表可以根据需要逐渐生成,因此您可以部分评估指数级的大组合。

> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"
> take 10 c
["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn",
 "abcdefgo","abcdefgp","abcdefgq"]

计算机编程艺术第4卷:Fascicle 3有很多这些可能比我描述的更适合您的特殊情况。

灰色代码

一个你会遇到的问题当然是记忆,而且很快,你的设置中会有20个元素出现问题 - 20 C 3 = 1140.如果你想遍历集合,最好使用修改过的灰色代码算法,所以你没有把它们全部放在内存中。 这些从前一个产生下一个组合并避免重复。 有许多这些用于不同的用途。 我们想要最大化连续组合之间的差异吗? 最小化? 等等。

一些描述灰色代码的原始论文:

  1. 一些Hamilton路径和一个最小变化算法
  2. 相邻交换组合生成算法

以下是一些其他论文,涉及该主题:

  1. 有效实施Eades,Hickey,阅读相邻交换组合生成算法 (PDF,代码采用Pascal)
  2. 组合发生器
  3. 组合格雷码综述 (PostScript)
  4. 一种灰色编码算法

Chase的Twiddle(算法)

Phillip J Chase,“ Algorithm 382:M of N of N Objects组合 ”(1970)

算法在C ...

字典顺序中的组合索引(扣扣算法515)

您也可以通过其索引(按字典顺序)参考组合。 意识到索引应该是基于索引从右到左的一些变化,我们可以构建一些应该恢复组合的东西。

所以,我们有一组{1,2,3,4,5,6} ...并且我们需要三个元素。 假设{1,2,3}我们可以说元素之间的差异是一个,并且是最小的。 {1,2,4}有一个变化,并且按照字典顺序排列编号2.因此,最后一个位置的“变化”数量在辞典排序中占一个变化。 第二个变化{1,3,4}有一个变化,但由于它在第二位(与原始组中元素的数量成比例),所以变化更大。

我所描述的方法是一种解构,就像从设置到索引那样,我们需要做相反的处理 - 这更加棘手。 这就是Buckles解决问题的方法。 我写了一些C来计算它们 ,只做了很小的修改 - 我用集合的索引而不是数字范围来表示集合,所以我们总是从0 ... n开始工作。 注意:

  1. 由于组合无序,{1,3,2} = {1,2,3} - 我们命令它们是词典。
  2. 该方法有一个隐式0来启动第一个差异的集合。

字典顺序中的组合索引(McCaffrey)

还有另一种方法 :,它的概念更易于掌握和编程,但它没有Buckles的优化。 幸运的是,它也不会产生重复的组合:

集合 最大化 ,在哪里

例如: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1) 。 所以,第二十七个词汇组合是:{1,2,5,6},这些是你想要看的任何集合的索引。 下面的例子(OCaml),需要choose功能,留给读者:

(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
    (* maximize function -- maximize a that is aCb              *)
    (* return largest c where c < i and choose(c,i) <= z        *)
    let rec maximize a b x =
        if (choose a b ) <= x then a else maximize (a-1) b x
    in
    let rec iterate n x i = match i with
        | 0 -> []
        | i ->
            let max = maximize n i x in
            max :: iterate n (x - (choose max i)) (i-1)
    in
    if x < 0 then failwith "errors" else
    let idxs =  iterate (List.length set) x k in
    List.map (List.nth set) (List.sort (-) idxs)

https://gist.github.com/3118596

有一个JavaScript实现。 它具有获得k组合和任何对象数组的所有组合的功能。 例子:

k_combinations([1,2,3], 2)
-> [[1,2], [1,3], [2,3]]

combinations([1,2,3])
-> [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

Here's my JavaScript solution that is a little more functional through use of reduce/map, which eliminates almost all variables

function combinations(arr, size) {
  var len = arr.length;

  if (size > len) return [];
  if (!size) return [[]];
  if (size == len) return [arr];

  return arr.reduce(function (acc, val, i) {
    var res = combinations(arr.slice(i + 1), size - 1)
      .map(function (comb) { return [val].concat(comb); });
    
    return acc.concat(res);
  }, []);
}

var combs = combinations([1,2,3,4,5,6,7,8],3);
combs.map(function (comb) {
  document.body.innerHTML += comb.toString() + '<br />';
});

document.body.innerHTML += '<br /> Total combinations = ' + combs.length;


I have written a class to handle common functions for working with the binomial coefficient, which is the type of problem that your problem falls under. It performs the following tasks:

  1. Outputs all the K-indexes in a nice format for any N choose K to a file. The K-indexes can be substituted with more descriptive strings or letters. This method makes solving this type of problem quite trivial.

  2. Converts the K-indexes to the proper index of an entry in the sorted binomial coefficient table. This technique is much faster than older published techniques that rely on iteration. It does this by using a mathematical property inherent in Pascal's Triangle. My paper talks about this. I believe I am the first to discover and publish this technique, but I could be wrong.

  3. Converts the index in a sorted binomial coefficient table to the corresponding K-indexes.

  4. Uses Mark Dominus method to calculate the binomial coefficient, which is much less likely to overflow and works with larger numbers.

  5. The class is written in .NET C# and provides a way to manage the objects related to the problem (if any) by using a generic list. The constructor of this class takes a bool value called InitTable that when true will create a generic list to hold the objects to be managed. If this value is false, then it will not create the table. The table does not need to be created in order to perform the 4 above methods. Accessor methods are provided to access the table.

  6. There is an associated test class which shows how to use the class and its methods. It has been extensively tested with 2 cases and there are no known bugs.

To read about this class and download the code, see Tablizing The Binomial Coeffieicent .

It should not be hard to convert this class to C++.


Lets say your array of letters looks like this: "ABCDEFGH". You have three indices (i, j, k) indicating which letters you are going to use for the current word, You start with:

A B C D E F G H
^ ^ ^
i j k

First you vary k, so the next step looks like that:

A B C D E F G H
^ ^   ^
i j   k

If you reached the end you go on and vary j and then k again.

A B C D E F G H
^   ^ ^
i   j k

A B C D E F G H
^   ^   ^
i   j   k

Once you j reached G you start also to vary i.

A B C D E F G H
  ^ ^ ^
  i j k

A B C D E F G H
  ^ ^   ^
  i j   k
...
function initializePointers($cnt) {
    $pointers = [];

    for($i=0; $i<$cnt; $i++) {
        $pointers[] = $i;
    }

    return $pointers;     
}

function incrementPointers(&$pointers, &$arrLength) {
    for($i=0; $i<count($pointers); $i++) {
        $currentPointerIndex = count($pointers) - $i - 1;
        $currentPointer = $pointers[$currentPointerIndex];

        if($currentPointer < $arrLength - $i - 1) {
           ++$pointers[$currentPointerIndex];

           for($j=1; ($currentPointerIndex+$j)<count($pointers); $j++) {
                $pointers[$currentPointerIndex+$j] = $pointers[$currentPointerIndex]+$j;
           }

           return true;
        }
    }

    return false;
}

function getDataByPointers(&$arr, &$pointers) {
    $data = [];

    for($i=0; $i<count($pointers); $i++) {
        $data[] = $arr[$pointers[$i]];
    }

    return $data;
}

function getCombinations($arr, $cnt)
{
    $len = count($arr);
    $result = [];
    $pointers = initializePointers($cnt);

    do {
        $result[] = getDataByPointers($arr, $pointers);
    } while(incrementPointers($pointers, count($arr)));

    return $result;
}

$result = getCombinations([0, 1, 2, 3, 4, 5], 3);
print_r($result);

Based on https://.com/a/127898/2628125 , but more abstract, for any size of pointers.


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

  • 选择你的组合的第一个元素i
  • i与从大于i的元素集合中递归选择的k-1元素的每个组合进行组合。

i中的每个i重复上述过程。

选择其余元素比i ,这是至关重要的,以避免重复。 这种方式[3,5]将被选中一次,如[3]与[5]相结合,而不是两次(条件消除[5] + [3])。 没有这种情况,你会得到变化而不是组合。


可以说你的字母数组看起来像这样:“ABCDEFGH”。 你有三个指数(i,j,k),表示你将用于当前单词的哪些字母,你从以下开始:

A B C D E F G H
^ ^ ^
i j k

首先你改变k,所以下一步看起来像这样:

A B C D E F G H
^ ^   ^
i j   k

如果你到达最后,你继续改变j然后再改变k。

A B C D E F G H
^   ^ ^
i   j k

A B C D E F G H
^   ^   ^
i   j   k

一旦你到达G你也开始改变我。

A B C D E F G H
  ^ ^ ^
  i j k

A B C D E F G H
  ^ ^   ^
  i j   k
...

用代码写,看起来像这样

void print_combinations(const char *string)
{
    int i, j, k;
    int len = strlen(string);

    for (i = 0; i < len - 2; i++)
    {
        for (j = i + 1; j < len - 1; j++)
        {
            for (k = j + 1; k < len; k++)
                printf("%c%c%c\n", string[i], string[j], string[k]);
        }
    }
}

在C ++中,以下例程将产生范围[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

如果您可以使用SQL语法 - 比方说,如果您使用LINQ来访问结构或数组的字段,或者直接访问只有一个字符字段“Letter”的具有名为“Alphabet”的表的数据库,则可以调整以下内容码:

SELECT A.Letter, B.Letter, C.Letter
FROM Alphabet AS A, Alphabet AS B, Alphabet AS C
WHERE A.Letter<>B.Letter AND A.Letter<>C.Letter AND B.Letter<>C.Letter
AND A.Letter<B.Letter AND B.Letter<C.Letter

这将返回3个字母的所有组合,尽管你在表格“Alphabet”中有多少个字母(可以是3,8,10,27等)。

如果你想要的是所有的排列,而不是组合(即你想要“ACB”和“ABC”算作不同,而不是只出现一次),只需删除最后一行(AND)即可完成。

编辑后:重新阅读问题后,我意识到需要的是一般算法,而不仅仅是针对选择3个项目的特定算法。 亚当休斯的答案是完整的,不幸的是我不能投票(还)。 这个答案很简单,但只适用于你想要3件物品的情况。



我可以提出我的递归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:len(elements)], length-1):
                yield (elements[i],) + next
def choose(l, k):
    return list(choose_iter(l, k))

用法示例:

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

我喜欢它的简单性。


我有一个用于python的项目euler的排列算法:

def missing(miss,src):
    "Returns the list of items in src not present in miss"
    return [i for i in src if i not in miss]


def permutation_gen(n,l):
    "Generates all the permutations of n items of the l list"
    for i in l:
        if n<=1: yield [i]
        r = [i]
        for j in permutation_gen(n-1,missing([i],l)):  yield r+j

如果

n<len(l) 

你应该有所需要的所有组合,而不必重复,你需要它吗?

它是一个生成器,所以你可以像这样使用它:

for comb in permutation_gen(3,list("ABCDEFGH")):
    print comb 

短的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]

简洁的Javascript解决方案:

Array.prototype.combine=function combine(k){    
    var toCombine=this;
    var last;
    function combi(n,comb){             
        var combs=[];
        for ( var x=0,y=comb.length;x<y;x++){
            for ( var l=0,m=toCombine.length;l<m;l++){      
                combs.push(comb[x]+toCombine[l]);           
            }
        }
        if (n<k-1){
            n++;
            combi(n,combs);
        } else{last=combs;}
    }
    combi(1,toCombine);
    return last;
}
// Example:
// var toCombine=['a','b','c'];
// var results=toCombine.combine(4);

这是我在C ++中的主张

我试图对迭代器类型施加尽可能小的限制,因此该解决方案假定只是前向迭代器,并且它可以是const_iterator。 这应该适用于任何标准容器。 在参数没有意义的情况下,它会抛出std :: invalid_argumnent

#include <vector>
#include <stdexcept>

template <typename Fci> // Fci - forward const iterator
std::vector<std::vector<Fci> >
enumerate_combinations(Fci begin, Fci end, unsigned int combination_size)
{
    if(begin == end && combination_size > 0u)
        throw std::invalid_argument("empty set and positive combination size!");
    std::vector<std::vector<Fci> > result; // empty set of combinations
    if(combination_size == 0u) return result; // there is exactly one combination of
                                              // size 0 - emty set
    std::vector<Fci> current_combination;
    current_combination.reserve(combination_size + 1u); // I reserve one aditional slot
                                                        // in my vector to store
                                                        // the end sentinel there.
                                                        // The code is cleaner thanks to that
    for(unsigned int i = 0u; i < combination_size && begin != end; ++i, ++begin)
    {
        current_combination.push_back(begin); // Construction of the first combination
    }
    // Since I assume the itarators support only incrementing, I have to iterate over
    // the set to get its size, which is expensive. Here I had to itrate anyway to  
    // produce the first cobination, so I use the loop to also check the size.
    if(current_combination.size() < combination_size)
        throw std::invalid_argument("combination size > set size!");
    result.push_back(current_combination); // Store the first combination in the results set
    current_combination.push_back(end); // Here I add mentioned earlier sentinel to
                                        // simplyfy rest of the code. If I did it 
                                        // earlier, previous statement would get ugly.
    while(true)
    {
        unsigned int i = combination_size;
        Fci tmp;                            // Thanks to the sentinel I can find first
        do                                  // iterator to change, simply by scaning
        {                                   // from right to left and looking for the
            tmp = current_combination[--i]; // first "bubble". The fact, that it's 
            ++tmp;                          // a forward iterator makes it ugly but I
        }                                   // can't help it.
        while(i > 0u && tmp == current_combination[i + 1u]);

        // Here is probably my most obfuscated expression.
        // Loop above looks for a "bubble". If there is no "bubble", that means, that
        // current_combination is the last combination, Expression in the if statement
        // below evaluates to true and the function exits returning result.
        // If the "bubble" is found however, the ststement below has a sideeffect of 
        // incrementing the first iterator to the left of the "bubble".
        if(++current_combination[i] == current_combination[i + 1u])
            return result;
        // Rest of the code sets posiotons of the rest of the iterstors
        // (if there are any), that are to the right of the incremented one,
        // to form next combination

        while(++i < combination_size)
        {
            current_combination[i] = current_combination[i - 1u];
            ++current_combination[i];
        }
        // Below is the ugly side of using the sentinel. Well it had to haave some 
        // disadvantage. Try without it.
        result.push_back(std::vector<Fci>(current_combination.begin(),
                                          current_combination.end() - 1));
    }
}

这是我最近在Java中编写的代码,它计算并返回“outOf”元素中“num”元素的所有组合。

// author: Sourabh Bhat ([email protected])

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);
    }
}

static IEnumerable<string> Combinations(List<string> characters, int length)
{
    for (int i = 0; i < characters.Count; i++)
    {
        // only want 1 character, just return this one
        if (length == 1)
            yield return characters[i];

        // want more than one character, return this one plus all combinations one shorter
        // only use characters after the current one for the rest of the combinations
        else
            foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
                yield return characters[i] + next;
    }
}

Array.prototype.combs = function(num) {

    var str = this,
        length = str.length,
        of = Math.pow(2, length) - 1,
        out, combinations = [];

    while(of) {

        out = [];

        for(var i = 0, y; i < length; i++) {

            y = (1 << i);

            if(y & of && (y !== of))
                out.push(str[i]);

        }

        if (out.length >= num) {
           combinations.push(out);
        }

        of--;
    }

    return combinations;
}




combinations