从n返回k个元素的所有组合的算法

Question

我想写一个函数,它将一个字母数组作为参数,并选择一些字母.

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

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

数组(或单词)返回,每个包含3个字母.

Answer 1

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

格雷码

你会遇到的一个问题当然是记忆而且非常快,你的组中有20个元素会出现问题 - ²⁰ C ₃ = 1140.如果你想迭代这个集合,最好使用修改后的灰色代码算法,所以你没有把所有这些都保存在内存中.这些产生了前一个的下一个组合,避免重复.其中有许多用于不同的用途.我们是否希望最大化连续组合之间的差异？最小化？等等.

一些描述格雷码的原始论文:

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

以下是一些涉及该主题的其他文章:

1. Eades,Hickey,读取相邻交换组合生成算法的有效实现(PDF,代码为Pascal)
2. 组合发电机
3. 组合灰度代码调查(PostScript)
4. 一种格雷码算法

Chase's Twiddle(算法)

Phillip J Chase," 算法382:N个物体中M的组合 "(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)

Answer 2

在C#中:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
  return k == 0 ? new[] { new T[0] } :
    elements.SelectMany((e, i) =>
      elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}

用法:

var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);

结果:

123
124
125
134
135
145
234
235
245
345

Answer 3

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

Answer 4

我可以提出我的递归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

我喜欢它的简单性.

Answer 5

让我们说你的一系列字母看起来像这样:"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]);
        }
    }
}

Answer 6

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

• 选择i组合的第一个元素
• 结合i与每个组合的k-1从所述一组大于元件的递归选择元素i.

i对集合中的每一个迭代上面的内容.

i为了避免重复,必须选择大于其余的元素.这种方式[3,5]只会被选择一次,因为[3]与[5]结合,而不是两次(条件消除[5] + [3]).没有这种情况,你会得到变化而不是组合.

Answer 7

我发现这个线程很有用,并且我认为我会添加一个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

Answer 8

在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

Answer 9

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

Answer 10

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

为了便于说明,使用以下示例描述递归方法:

示例:ABCDE
3的所有组合将是:

• A与其余的所有组合2(BCDE)
• B与其余的所有组合2(CDE)
• C与其余的所有组合(DE)

Answer 11

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遍历列表中的每个元素,并且xs是后面的每个元素x.

restn - 1从xs使用递归调用中选择元素combinations.该函数的最终结果是一个列表,其中每个元素都是x : rest(对于每个不同的和的值,列表具有x头部和rest尾部).xrest

> 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"]

Answer 12

这是一款备受诟病的语言 - 爷爷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.

Answer 13

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

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个项目.

Answer 14

这是Scala中优雅的通用实现,如99 Scala问题所述.

object P26 {
  def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = 
    ls match {
      case Nil => Nil
      case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)
    }

  def combinations[A](n: Int, ls: List[A]): List[List[A]] =
    if (n == 0) List(Nil)
    else flatMapSublists(ls) { sl =>
      combinations(n - 1, sl.tail) map {sl.head :: _}
    }
}

Answer 15

另一个带有懒惰生成组合索引的C#版本.此版本维护单个索引数组,以定义所有值列表与当前组合值之间的映射,即在整个运行时期间不断使用O(k)额外空间.代码在O(k)时间内生成单独的组合,包括第一个组合.

public static IEnumerable<T[]> Combinations<T>(this T[] values, int k)
{
    if (k < 0 || values.Length < k)
        yield break; // invalid parameters, no combinations possible

    // generate the initial combination indices
    var combIndices = new int[k];
    for (var i = 0; i < k; i++)
    {
        combIndices[i] = i;
    }

    while (true)
    {
        // return next combination
        var combination = new T[k];
        for (var i = 0; i < k; i++)
        {
            combination[i] = values[combIndices[i]];
        }
        yield return combination;

        // find first index to update
        var indexToUpdate = k - 1;
        while (indexToUpdate >= 0 && combIndices[indexToUpdate] >= values.Length - k + indexToUpdate)
        {
            indexToUpdate--;
        }

        if (indexToUpdate < 0)
            yield break; // done

        // update combination indices
        for (var combIndex = combIndices[indexToUpdate] + 1; indexToUpdate < k; indexToUpdate++, combIndex++)
        {
            combIndices[indexToUpdate] = combIndex;
        }
    }
}

测试代码:

foreach (var combination in new[] {'a', 'b', 'c', 'd', 'e'}.Combinations(3))
{
    System.Console.WriteLine(String.Join(" ", combination));
}

输出:

a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e

Answer 16

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

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 

Answer 17

这里有一个用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));
        }
    }

希望这对你有所帮助!

Answer 18

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

Answer 19

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

Answer 20

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

Answer 21

简短的Python代码，产生索引位置

def yield_combos(n,k):
    # n is set size, k is combo size

    i = 0
    a = [0]*k

    while i > -1:
        for j in range(i+1, k):
            a[j] = a[j-1]+1
        i=j
        yield a
        while a[i] == i + n - k:
            i -= 1
        a[i] += 1

Answer 22

算法：

• 从 1 数到 2^n。
• 将每个数字转换为其二进制表示形式。
• 根据位置将每个“on”位转换为集合中的元素。

在 C# 中：

void Main()
{
    var set = new [] {"A", "B", "C", "D" }; //, "E", "F", "G", "H", "I", "J" };
    
    var kElement = 2;
    
    for(var i = 1; i < Math.Pow(2, set.Length); i++) {
        var result = Convert.ToString(i, 2).PadLeft(set.Length, '0');
        var cnt = Regex.Matches(Regex.Escape(result),  "1").Count; 
        if (cnt == kElement) {
            for(int j = 0; j < set.Length; j++)
                if ( Char.GetNumericValue(result[j]) == 1)
                    Console.Write(set[j]);
            Console.WriteLine();
        }
    }
}

为什么它有效？

n 元素集的子集和 n 位序列之间存在双射。

这意味着我们可以通过计算序列来找出有多少个子集。

例如，下面的四元素集可以用{0,1} X {0, 1} X {0, 1} X {0, 1}（或2^4）不同的序列来表示。

所以 -我们所要做的就是从 1 数到 2^n 来找到所有组合。（我们忽略空集。）接下来，将数字转换为其二进制表示形式。然后用集合中的元素替换“on”位。

如果您只需要 k 个元素结果，则仅在 k 位“打开”时打印。

（如果您想要所有子集而不是 k 长度子集，请删除 cnt/kElement 部分。）

如需证明，请参阅MIT 免费课件 Mathematics for Computer Science，Lehman 等人的第 11.2.2 节。

Answer 23

假设您的字母数组如下所示：“ ABCDEFGH”。您有三个索引（i，j，k），它们指示当前单词将使用哪些字母，您从以下位置开始：

ABCDEFGH
^ ^ ^
约克

首先，您改变k，因此下一步看起来像这样：

ABCDEFGH
^ ^ ^
约克

如果到达末尾，则继续并依次改变j和k。

ABCDEFGH
^ ^ ^
约克

ABCDEFGH
^ ^ ^
约克

j达到G后，您也开始改变i。

ABCDEFGH
  ^ ^ ^
  约克

ABCDEFGH
  ^ ^ ^
  约克
...

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

基于/sf/answers/8952891/，但更抽象，适用于任何大小的指针。