Алгоритм возврата всех комбинаций k элементов из n

Question

Я хочу написать функцию, которая принимает массив букв в качестве аргумента и количество этих букв для выбора.

Допустим, вы предоставляете массив из 8 букв и хотите выбрать 3 буквы из этого. Тогда вы должны получить:

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

Массивы (или слова) в ответ, состоящие из 3 букв.

Answer 1

Простой рекурсивный алгоритм в 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.

rest выбирает n - 1 элементов из xs, используя рекурсивный вызов combinations. Конечным результатом функции является список, в котором каждый элемент равен 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"]

Answer 2

А вот и дедушка КОБОЛЬ, очень злобный язык.

Давайте предположим, что массив из 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 3

Если вы можете использовать синтаксис SQL - скажем, если вы используете LINQ для доступа к полям структуры или массива или напрямую обращаетесь к базе данных, в которой есть таблица «Алфавит» с одним символьным полем «Буква», вы можно адаптировать следующий код:

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 букв, независимо от того, сколько букв у вас в таблице «Алфавит» (это может быть 3, 8, 10, 27 и т. Д.).

Если вам нужны все перестановки, а не комбинации (т.е. вы хотите, чтобы «ACB» и «ABC» считались разными, а не появлялись только один раз), просто удалите последнюю строку (одну «И») и все готово.

Постредактирование: после перечитывания вопроса я понимаю, что необходим общий алгоритм, а не только конкретный для случая выбора 3 элементов. Ответ Адама Хьюза является полным, к сожалению, я не могу его проголосовать (пока). Этот ответ прост, но работает только тогда, когда вам нужно ровно 3 элемента.

Answer 4

Вот элегантная универсальная реализация в 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 5

Здесь у вас есть ленивая версия этого алгоритма, написанная на 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 6

Еще одна версия 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 7

У меня был алгоритм перестановки, который я использовал для проекта 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 8

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 9

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 10

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