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

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

如果您可以使用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

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

如果您想要的是所有排列,而不是组合(即您希望"ACB"和"ABC"计算为不同,而不是仅出现一次)只需删除最后一行(AND一)并完成.

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

        

14> Zack Marrape..：

这是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 :: _}
    }
}

        

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



public static IEnumerable Combinations(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

        

16> Andrea Ambu..：

我有一个用于项目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

你需要所有你需要的组合而不重复,你需要它吗？

它是一个生成器,所以你可以用这样的东西:

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

        

17> Juan Antonio..：

这里有一个用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(IEnumerable 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 i in Combinations(t, k))
        {
            Console.WriteLine(string.Join(",", i));
        }
    }


希望这对你有所帮助!

        

18> Akseli Palén..：
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]]

        

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

        

20> llj098..：
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))))

        

21> 小智..：

假设您的字母数组如下所示：“ 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/ask/17360801/，但更抽象，适用于任何大小的指针。