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

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

542 голосов
/ 24 сентября 2008

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

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

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

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

Ответы [ 70 ]

395 голосов
/ 24 сентября 2008

Искусство компьютерного программирования, том 4: В главе 3 есть тонна таких вещей, которые могли бы соответствовать вашей конкретной ситуации лучше, чем я описываю.

Серые коды

Проблема, с которой вы столкнетесь, это, конечно, память и довольно быстро, у вас будут проблемы с 20 элементами в вашем наборе - 20 C 3 = 1140. И если вы хотите перебрать множество, лучше использовать модифицированный алгоритм серого кода, чтобы не хранить все из них в памяти. Они генерируют следующую комбинацию из предыдущего и избегают повторений. Есть много из них для различных целей. Мы хотим максимизировать различия между последовательными комбинациями? минимизировать? и так далее.

Некоторые из оригинальных работ, описывающих серые коды:

  1. Некоторые пути Гамильтона и алгоритм минимального изменения
  2. Алгоритм генерации комбинации смежных обменов

Вот еще несколько статей на эту тему:

  1. Эффективная реализация алгоритма генерации комбинаций Eades, Hickey, Read для смежного обмена (PDF, с кодом на Паскале)
  2. Комбинированные генераторы
  3. Обзор комбинаторных кодов серого (PostScript)
  4. Алгоритм для кодов серого

Чейз Твиддл (алгоритм)

Филипп Дж. Чейз, ` Алгоритм 382: комбинации М из N объектов '(1970)

Алгоритм на C ...

Индекс комбинаций в лексикографическом порядке (алгоритм Buckles 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. К счастью, он также не создает дублирующихся комбинаций:

Набор x_k...x_1 in N, который максимизирует i = C(x_1,k) + C(x_2,k-1) + ... + C(x_k,1), где C(n,r) = {n choose r}.

Для примера: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1). Итак, 27-я лексикографическая комбинация четырех вещей: {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)

Маленький и простой итератор комбинаций

Следующие два алгоритма предоставлены для дидактических целей. Они реализуют итератор и (более общие) общие комбинации папок. Они максимально быстрые, имеющие сложность O ( n C k ). Потребление памяти ограничено k.

Мы начнем с итератора, который будет вызывать пользовательскую функцию для каждой комбинации 

let iter_combs n k f =
  let rec iter v s j =
    if j = k then f v
    else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
  iter [] 0 0

Более общая версия будет вызывать предоставленную пользователем функцию вместе с переменной состояния, начиная с начального состояния. Поскольку нам нужно передать состояние между различными состояниями, мы не будем использовать цикл for, а вместо этого используем рекурсию, 

let fold_combs n k f x =
  let rec loop i s c x =
    if i < n then
      loop (i+1) s c @@
      let c = i::c and s = s + 1 and i = i + 1 in
      if s < k then loop i s c x else f c x
    else x in
  loop 0 0 [] x
186 голосов
/ 14 декабря 2009

В 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
74 голосов
/ 27 апреля 2013

Краткое решение 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]
73 голосов
/ 15 мая 2010

Могу ли я представить свое рекурсивное решение 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

Мне нравится его простота.

61 голосов
/ 24 сентября 2008

Допустим, ваш массив букв выглядит так: «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]);
        }
    }
}
52 голосов
/ 24 сентября 2008

Следующий рекурсивный алгоритм выбирает все комбинации k-элементов из упорядоченного набора:

  • выберите первый элемент i вашей комбинации
  • объединяет i с каждой из комбинаций k-1 элементов, выбранных рекурсивно из набора элементов, больших чем i.

Повторяйте выше для каждого i в наборе.

Очень важно, чтобы вы выбрали остальные элементы больше i, чтобы избежать повторения. Таким образом, [3,5] будет выбран только один раз, как [3] в сочетании с [5], а не дважды (условие исключает [5] + [3]). Без этого условия вы получаете вариации вместо комбинаций.

24 голосов
/ 17 ноября 2011

Я нашел эту ветку полезной и подумал, что добавлю решение 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
23 голосов
/ 24 октября 2009

В C ++ следующая подпрограмма будет производить все комбинации расстояния длины (first, k) между диапазонами [first, last): 

#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
20 голосов
/ 24 сентября 2008 
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;
    }
}
19 голосов
/ 01 августа 2013

Краткий пример на 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

Для пояснения рекурсивный метод описан в следующем примере:

Пример: A B C D E
Все комбинации из 3 будут:

  • A со всеми комбинациями 2 из остальных (B C D E)
  • B со всеми комбинациями 2 из остальных (C D E)
  • C со всеми комбинациями 2 из остальных (D E)
Страница:
...