Алгоритм возврата всех комбинаций из k элементов из n
https://stackoverflow.com/questions/127704
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я хочу написать функцию, которая принимает массив букв в качестве аргумента и количество этих букв для выбора.
Допустим, вы предоставляете массив из 8 букв и хотите выбрать из него 3 буквы.Тогда у вас должно получиться:
8! / ((8 - 3)! * 3!) = 56
Массивы (или слова) взамен состоящие из 3 букв каждый.
Решение
Искусство компьютерного программирования, том 4:Выпуск 3 есть масса таких, которые могут лучше подойти к вашей конкретной ситуации, чем то, что я описываю.
Коды Грея
Проблема, с которой вы столкнетесь, — это, конечно, память, и довольно быстро у вас возникнут проблемы с 20 элементами в вашем наборе — 20С3 = 1140.И если вы хотите перебрать набор, лучше всего использовать модифицированный алгоритм кода Грея, чтобы не хранить их все в памяти.Они генерируют следующую комбинацию из предыдущей и избегают повторений.Их много для разных целей.Хотим ли мы максимизировать различия между последовательными комбинациями?минимизировать?и так далее.
Некоторые из оригинальных статей, описывающих коды Грея:
- Некоторые пути Гамильтона и алгоритм минимального изменения
- Алгоритм генерации комбинации смежного обмена
Вот еще несколько статей по этой теме:
- Эффективная реализация алгоритма генерации комбинации смежного обмена Идса, Хики и чтения (PDF, с кодом на Паскале)
- Комбинированные генераторы
- Обзор комбинаторных кодов Грея (Постскриптум)
- Алгоритм для кодов Грея
Твиддл Чейза (алгоритм)
Филипп Джей Чейз, `Алгоритм 382:Комбинации M из N объектов' (1970)
Индекс комбинаций в лексикографическом порядке (алгоритм Баклза 515)
Вы также можете ссылаться на комбинацию по ее индексу (в лексикографическом порядке).Понимая, что индекс должен представлять собой некоторое изменение справа налево на основе индекса, мы можем построить что-то, что должно восстанавливать комбинацию.
Итак, у нас есть набор {1,2,3,4,5,6}...и нам нужны три элемента.Допустим, {1,2,3} можно сказать, что разница между элементами одна, по порядку и минимальна.{1,2,4} имеет одно изменение и лексикографически имеет номер 2.Таким образом, количество «изменений» на последнем месте соответствует одному изменению в лексикографическом порядке.Второе место с одним изменением {1,3,4} имеет одно изменение, но учитывает большее изменение, поскольку оно находится на втором месте (пропорционально количеству элементов в исходном наборе).
Метод, который я описал, представляет собой деконструкцию, поскольку, похоже, от множества к индексу нам нужно сделать обратное — что гораздо сложнее.Вот как Пряжки решает проблему.я написал кое-что C, чтобы вычислить их, с небольшими изменениями — для представления набора я использовал индекс наборов, а не числовой диапазон, поэтому мы всегда работаем от 0...n.Примечание:
- Поскольку комбинации неупорядочены, {1,3,2} = {1,2,3} — мы упорядочиваем их, чтобы они были лексикографическими.
- Этот метод имеет неявный 0, чтобы начать набор для первой разницы.
Указатель комбинаций в лексикографическом порядке (Маккаффри)
Есть другой путь: его концепцию легче понять и запрограммировать, но в нем нет оптимизации Buckles.К счастью, он также не создает повторяющихся комбинаций:
Набор 
это максимизирует 
, где 
.
Например: 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(нСк).Потребление памяти ограничено 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
Другие советы
В С#:
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
Короткое 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]
Могу ли я представить свое рекурсивное решение этой проблемы на 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
Мне он нравится своей простотой.
Допустим, ваш массив букв выглядит так:«АБВДЕФГХ».У вас есть три индекса (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, вы также начнете изменять i.
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]);
}
}
}
Следующий рекурсивный алгоритм выбирает все комбинации k-элементов из упорядоченного набора:
- выберите первый элемент
iвашей комбинации - объединить
iс каждой из комбинацийk-1элементы, выбранные рекурсивно из набора элементов размером болееi.
Повторите вышеописанное для каждого i в наборе.
Важно, чтобы остальные элементы были размером больше, чем i, чтобы избежать повторения.Таким образом, [3,5] будет выбрано только один раз, как [3] в сочетании с [5], а не дважды (условие исключает [5] + [3]).Без этого условия вместо комбинаций вы получите вариации.
Я нашел эту тему полезной и решил добавить решение 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
В C++ следующая процедура создаст все комбинации длин distance(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
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;
}
}
Короткий пример на 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
Для пояснения рекурсивный метод описывается на следующем примере:
Пример:А Б В Г Е
Все комбинации из 3 будут:
- А со всеми комбинациями 2 из остальных (B C D E)
- B со всеми комбинациями из 2-х остальных (C D E)
- C со всеми комбинациями из 2-х остальных (D E)
Простой рекурсивный алгоритм на 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"]
И вот появился дедушка КОБОЛ, столь оклеветанный язык.
Предположим, массив состоит из 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.
Пример КОБОЛа:
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.
Вот элегантная общая реализация в 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 :: _}
}
}
Если вы можете использовать синтаксис 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 предмета.
Еще одна версия C# с отложенной генерацией индексов комбинаций.Эта версия поддерживает единый массив индексов для определения сопоставления между списком всех значений и значениями текущей комбинации, т.е.постоянно использует Хорошо) дополнительное пространство в течение всего времени работы.Код генерирует отдельные комбинации, включая первую, в Хорошо) время.
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
Здесь у вас есть ленивая оцененная версия этого алгоритма, закодированная на 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));
}
}
Надеюсь, это вам поможет!
У меня был алгоритм перестановки, который я использовал для проекта Эйлера, на 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
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]]
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;
}
Версия 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))))
Допустим, ваш массив букв выглядит так:«АБВДЕФГХ».У вас есть три индекса (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, вы также начнете изменять 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);
На основе https://stackoverflow.com/a/127898/2628125, но более абстрактно, для указателей любого размера.
Я создал для этого решение в SQL Server 2005 и разместил его на своем веб-сайте: http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm
Вот пример, демонстрирующий использование:
SELECT * FROM dbo.fn_GetMChooseNCombos('ABCD', 2, '')
Результаты:
Word
----
AB
AC
AD
BC
BD
CD
(6 row(s) affected)
Вот мое предложение на 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));
}
}
Все сказано и сделано, вот для этого код О'Камла.Алгоритм виден из кода..
let combi n lst =
let rec comb l c =
if( List.length c = n) then [c] else
match l with
[] -> []
| (h::t) -> (combi t (h::c))@(combi t c)
in
combi lst []
;;
Вот код, который я недавно написал на Java, который вычисляет и возвращает все комбинации элементов «num» из элементов «outOf».
// author: Sourabh Bhat (heySourabh@gmail.com)
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);
}
}
Краткое решение 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);
Вот метод, который дает вам все комбинации указанного размера из строки случайной длины.Аналогично решению quinmars, но работает для разных входных данных и k.
Код можно изменить для переноса, например, «dab» из ввода «abcd» w k=3.
public void run(String data, int howMany){
choose(data, howMany, new StringBuffer(), 0);
}
//n choose k
private void choose(String data, int k, StringBuffer result, int startIndex){
if (result.length()==k){
System.out.println(result.toString());
return;
}
for (int i=startIndex; i<data.length(); i++){
result.append(data.charAt(i));
choose(data,k,result, i+1);
result.setLength(result.length()-1);
}
}
Вывод для «abcde»:
abc abd abe acd ace ade bcd bce bde cde
Я написал класс для обработки общих функций для работы с биномиальным коэффициентом, который является типом проблемы, к которой относится ваша проблема.Он выполняет следующие задачи:
Выводит все K-индексы в удобном формате для любого N, выбирающего K в файл.K-индексы можно заменить более описательными строками или буквами.Этот метод делает решение такого типа задач довольно тривиальным.
Преобразует K-индексы в правильный индекс записи в таблице отсортированных биномиальных коэффициентов.Этот метод намного быстрее, чем старые опубликованные методы, основанные на итерациях.Это достигается за счет использования математического свойства, присущего треугольнику Паскаля.Моя газета говорит об этом.Я считаю, что я первый, кто открыл и опубликовал эту технику, но могу ошибаться.
Преобразует индекс в отсортированной таблице биномиальных коэффициентов в соответствующие K-индексы.
Использование Марк Доминус метод расчета биномиального коэффициента, который с гораздо меньшей вероятностью переполнится и работает с большими числами.
Класс написан на .NET C# и предоставляет способ управления объектами, связанными с проблемой (если таковые имеются), с помощью универсального списка.Конструктор этого класса принимает логическое значение InitTable, которое, если оно истинно, создает общий список для хранения управляемых объектов.Если это значение ложно, таблица не будет создана.Таблицу не обязательно создавать для выполнения 4 вышеуказанных методов.Для доступа к таблице предусмотрены методы доступа.
Существует связанный тестовый класс, который показывает, как использовать этот класс и его методы.Он был тщательно протестирован в двух случаях, и никаких известных ошибок не обнаружено.
Чтобы прочитать об этом классе и загрузить код, см. Таблизация биномиального коэффициента.
Преобразовать этот класс в C++ не составит труда.
Алгоритм:
- Считайте от 1 до 2^n.
- Преобразуйте каждую цифру в ее двоичное представление.
- Переведите каждый бит «включено» в элементы вашего набора в зависимости от позиции.
В С#:
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, чтобы найти все комбинации. (Мы игнорируем пустой набор.) Затем переведите цифры в их двоичное представление.Затем замените элементы вашего набора битами «включено».
Если вам нужны результаты только k элементов, печатайте только тогда, когда k бит включены.
(Если вам нужны все подмножества вместо подмножеств длины k, удалите часть cnt/kElement.)
(Для доказательства см. бесплатные курсы MIT «Математика для информатики», Леман и др., раздел 11.2.2. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/ )
Подключаюсь к подножке и публикую другое решение.Это общая реализация Java.Вход: (int k) количество элементов для выбора и (List<T> list) это список на выбор.Возвращает список комбинаций (List<List<T>>).
public static <T> List<List<T>> getCombinations(int k, List<T> list) {
List<List<T>> combinations = new ArrayList<List<T>>();
if (k == 0) {
combinations.add(new ArrayList<T>());
return combinations;
}
for (int i = 0; i < list.size(); i++) {
T element = list.get(i);
List<T> rest = getSublist(list, i+1);
for (List<T> previous : getCombinations(k-1, rest)) {
previous.add(element);
combinations.add(previous);
}
}
return combinations;
}
public static <T> List<T> getSublist(List<T> list, int i) {
List<T> sublist = new ArrayList<T>();
for (int j = i; j < list.size(); j++) {
sublist.add(list.get(j));
}
return sublist;
}
