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

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

Коды Грея

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

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

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

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

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

Twiddle Чейза (алгоритм)

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

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

Указатель комбинаций в лексикографическом порядке (алгоритм пряжки 515)

Вы также можете ссылаться на комбинацию по ее индексу (в лексикографическом порядке). Понимая, что индекс должен подвергаться некоторому изменению справа налево на основе индекса, мы можем построить что-то, что должно восстанавливать комбинацию.

Итак, у нас есть набор {1,2,3,4,5,6} ... и нам нужно три элемента. Скажем {1,2,3}, мы можем сказать, что разница между элементами едина, порядок и минимален. {1,2,4} имеет одно изменение и лексикографически номер 2. Таким образом, количество «изменений» на последнем месте соответствует одному изменению в лексикографическом порядке. Второе место с одним изменением {1,3,4} имеет одно изменение, но учитывает большее количество изменений, поскольку оно находится на втором месте (пропорционально количеству элементов в исходном наборе).

Метод, который я описал, представляет собой деконструкцию, как кажется, от набора к индексу, нам нужно сделать обратное - что намного сложнее. Вот как Пряжки решает проблему. Я написал несколько C вычислить их с небольшими изменениями - я использовал индекс наборов, а не диапазон чисел для представления набора, поэтому мы всегда работаем от 0 ... n. Примечание:

1. Поскольку комбинации неупорядочены, {1,3,2} = {1,2,3} - мы делаем их лексикографическими.
2. Этот метод имеет неявный 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 (ⁿ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

Допустим, ваш массив букв выглядит так: «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

Как только вы j достигнете 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]);
        }
    }
}

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

Если вы можете использовать синтаксис 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» считались разными, а не появлялись только один раз), просто удалите последнюю строку (AND) и готово.

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

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

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

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

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

Вот мое предложение на 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));
    }
}

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

На Python похож на Андреа Амбу, но не жестко запрограммирован для выбора трех.

def combinations(list, k):
    """Choose combinations of list, choosing k elements(no repeats)"""
    if len(list) < k:
        return []
    else:
        seq = [i for i in range(k)]
        while seq:
            print [list[index] for index in seq]
            seq = get_next_combination(len(list), k, seq)

def get_next_combination(num_elements, k, seq):
        index_to_move = find_index_to_move(num_elements, seq)
        if index_to_move == None:
            return None
        else:
            seq[index_to_move] += 1

            #for every element past this sequence, move it down
            for i, elem in enumerate(seq[(index_to_move+1):]):
                seq[i + 1 + index_to_move] = seq[index_to_move] + i + 1

            return seq

def find_index_to_move(num_elements, seq):
        """Tells which index should be moved"""
        for rev_index, elem in enumerate(reversed(seq)):
            if elem < (num_elements - rev_index - 1):
                return len(seq) - rev_index - 1
        return None   

Я создал для этого решение в 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++ следующая процедура будет производить все комбинации длин расстояний (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

В 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

Вот код, который я недавно написал на Java, который вычисляет и возвращает все комбинации элементов «num» из элементов «outOf».

// author: Sourabh Bhat ([email protected])

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

Вот простой код, который печатает все комбинации C (n, m). Он работает путем инициализации и перемещения набора индексов массива, указывающих на следующую допустимую комбинацию. Индексы инициализируются так, чтобы указывать на наименьшие m индексов (лексикографически наименьшую комбинацию). Затем, начиная с m-го индекса, мы пытаемся продвинуть индексы вперед. если индекс достиг своего предела, мы пробуем предыдущий индекс (вплоть до индекса 1). Если мы можем переместить индекс вперед, мы сбрасываем все большие индексы.

m=(rand()%n)+1; // m will vary from 1 to n

for (i=0;i<n;i++) a[i]=i+1;

// we want to print all possible C(n,m) combinations of selecting m objects out of n
printf("Printing C(%d,%d) possible combinations ...\n", n,m);

// This is an adhoc algo that keeps m pointers to the next valid combination
for (i=0;i<m;i++) p[i]=i; // the p[.] contain indices to the a vector whose elements constitute next combination

done=false;
while (!done)
{
    // print combination
    for (i=0;i<m;i++) printf("%2d ", a[p[i]]);
    printf("\n");

    // update combination
    // method: start with p[m-1]. try to increment it. if it is already at the end, then try moving p[m-2] ahead.
    // if this is possible, then reset p[m-1] to 1 more than (the new) p[m-2].
    // if p[m-2] can not also be moved, then try p[m-3]. move that ahead. then reset p[m-2] and p[m-1].
    // repeat all the way down to p[0]. if p[0] can not also be moved, then we have generated all combinations.
    j=m-1;
    i=1;
    move_found=false;
    while ((j>=0) && !move_found)
    {
        if (p[j]<(n-i)) 
        {
            move_found=true;
            p[j]++; // point p[j] to next index
            for (k=j+1;k<m;k++)
            {
                p[k]=p[j]+(k-j);
            }
        }
        else
        {
            j--;
            i++;
        }
    }
    if (!move_found) done=true;
}

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

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

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

Здесь у вас есть версия этого алгоритма с отложенной оценкой, написанная на 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));
        }
    }

Надеюсь, это поможет вам!

Макрос Lisp генерирует код для всех значений r (взятых за раз)

(defmacro txaat (some-list taken-at-a-time)
  (let* ((vars (reverse (truncate-list '(a b c d e f g h i j) taken-at-a-time))))
    `(
      ,@(loop for i below taken-at-a-time 
           for j in vars 
           with nested = nil 
           finally (return nested) 
           do
             (setf 
              nested 
              `(loop for ,j from
                    ,(if (< i (1- (length vars)))
                         `(1+ ,(nth (1+ i) vars))
                         0)
                  below (- (length ,some-list) ,i)
                    ,@(if (equal i 0) 
                          `(collect 
                               (list
                                ,@(loop for k from (1- taken-at-a-time) downto 0
                                     append `((nth ,(nth k vars) ,some-list)))))
                          `(append ,nested))))))))

Так,

CL-USER> (macroexpand-1 '(txaat '(a b c d) 1))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 1)
    COLLECT (LIST (NTH A '(A B C D))))
T
CL-USER> (macroexpand-1 '(txaat '(a b c d) 2))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 2)
      APPEND (LOOP FOR B FROM (1+ A) TO (- (LENGTH '(A B C D)) 1)
                   COLLECT (LIST (NTH A '(A B C D)) (NTH B '(A B C D)))))
T
CL-USER> (macroexpand-1 '(txaat '(a b c d) 3))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 3)
      APPEND (LOOP FOR B FROM (1+ A) TO (- (LENGTH '(A B C D)) 2)
                   APPEND (LOOP FOR C FROM (1+ B) TO (- (LENGTH '(A B C D)) 1)
                                COLLECT (LIST (NTH A '(A B C D))
                                              (NTH B '(A B C D))
                                              (NTH C '(A B C D))))))
T

CL-USER> 

И,

CL-USER> (txaat '(a b c d) 1)
((A) (B) (C) (D))
CL-USER> (txaat '(a b c d) 2)
((A B) (A C) (A D) (B C) (B D) (C D))
CL-USER> (txaat '(a b c d) 3)
((A B C) (A B D) (A C D) (B C D))
CL-USER> (txaat '(a b c d) 4)
((A B C D))
CL-USER> (txaat '(a b c d) 5)
NIL
CL-USER> (txaat '(a b c d) 0)
NIL
CL-USER> 

Я нашел эту ветку полезной и подумал, что добавлю решение Javascript, которое вы можете вставить в Firebug. В зависимости от вашего JS-движка это может занять немного времени, если начальная строка большая.

function string_recurse(active, rest) {
    if (rest.length == 0) {
        console.info(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

Вот метод, который дает вам все комбинации указанного размера из строки случайной длины. Подобно решению 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

В Python используется рекурсия и тот факт, что все делается по ссылке. Это займет много памяти для очень больших наборов, но имеет то преимущество, что исходный набор может быть сложным объектом. Найдет только уникальные комбинации.

import copy

def find_combinations( length, set, combinations = None, candidate = None ):
    # recursive function to calculate all unique combinations of unique values
    # from [set], given combinations of [length].  The result is populated
    # into the 'combinations' list.
    #
    if combinations == None:
        combinations = []
    if candidate == None:
        candidate = []

    for item in set:
        if item in candidate:
            # this item already appears in the current combination somewhere.
            # skip it
            continue

        attempt = copy.deepcopy(candidate)
        attempt.append(item)
        # sorting the subset is what gives us completely unique combinations,
        # so that [1, 2, 3] and [1, 3, 2] will be treated as equals
        attempt.sort()

        if len(attempt) < length:
            # the current attempt at finding a new combination is still too
            # short, so add another item to the end of the set
            # yay recursion!
            find_combinations( length, set, combinations, attempt )
        else:
            # the current combination attempt is the right length.  If it
            # already appears in the list of found combinations then we'll
            # skip it.
            if attempt in combinations:
                continue
            else:
                # otherwise, we append it to the list of found combinations
                # and move on.
                combinations.append(attempt)
                continue
    return len(combinations)

Вы используете это так. Передавать «результат» необязательно, поэтому вы можете просто использовать его для получения количества возможных комбинаций ... хотя это было бы действительно неэффективно (лучше делать расчетом).

size = 3
set = [1, 2, 3, 4, 5]
result = []

num = find_combinations( size, set, result ) 
print "size %d results in %d sets" % (size, num)
print "result: %s" % (result,)

Вы должны получить следующий результат из этих тестовых данных:

size 3 results in 10 sets
result: [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

И он будет работать так же хорошо, если ваш набор будет выглядеть так:

set = [
    [ 'vanilla', 'cupcake' ],
    [ 'chocolate', 'pudding' ],
    [ 'vanilla', 'pudding' ],
    [ 'chocolate', 'cookie' ],
    [ 'mint', 'cookie' ]
]

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

Это рекурсивная программа, которая генерирует комбинации для nCk.Elements в коллекции, предположительно от 1 до n.

#include<stdio.h>
#include<stdlib.h>

int nCk(int n,int loopno,int ini,int *a,int k)
{
    static int count=0;
    int i;
    loopno--;
    if (loopno<0)
    {
        a[k-1]=ini;
        for(i=0;i<k;i++)
        {
            printf("%d,",a[i]);
        }
        printf("\n");
        count++;
        return 0;
    }
    for(i=ini;i<=n-loopno-1;i++)
    {
        a[k-1-loopno]=i+1;
        nCk(n,loopno,i+1,a,k);
    }
    if (ini==0)
    return count;
    else
    return 0;
}

void main()
{
    int n,k,*a,count;
    printf("Enter the value of n and k\n");
    scanf("%d %d",&n,&k);
    a=(int*)malloc(k*sizeof(int));
    count=nCk(n,k,0,a,k);
    printf("No of combinations=%d\n",count);
}

В VB.Net этот алгоритм собирает все комбинации n чисел из набора чисел (PoolArray). например все комбинации из 5 пиков из «8,10,20,33,41,44,47».

Sub CreateAllCombinationsOfPicksFromPool(ByVal PicksArray() As UInteger, ByVal PicksIndex As UInteger, ByVal PoolArray() As UInteger, ByVal PoolIndex As UInteger)
    If PicksIndex < PicksArray.Length Then
        For i As Integer = PoolIndex To PoolArray.Length - PicksArray.Length + PicksIndex
            PicksArray(PicksIndex) = PoolArray(i)
            CreateAllCombinationsOfPicksFromPool(PicksArray, PicksIndex + 1, PoolArray, i + 1)
        Next
    Else
        ' completed combination. build your collections using PicksArray.
    End If
End Sub

        Dim PoolArray() As UInteger = Array.ConvertAll("8,10,20,33,41,44,47".Split(","), Function(u) UInteger.Parse(u))
        Dim nPicks as UInteger = 5
        Dim Picks(nPicks - 1) As UInteger
        CreateAllCombinationsOfPicksFromPool(Picks, 0, PoolArray, 0)

Поскольку язык программирования не упоминается, я предполагаю, что списки тоже в порядке. Итак, вот версия OCaml, подходящая для коротких списков (без хвостовой рекурсии). Учитывая список л элементов типа Любые и целое число п, он вернет список всех возможных списков, содержащих элементы п из л, если мы предположим, что порядок элементов в списках результатов игнорируется, то есть список ['a'; 'b'] совпадает с ['b'; 'a'] и сообщается один раз. Таким образом, размер результирующего списка будет ((List.length l) Выберите n).

Интуиция рекурсии следующая: вы берете начало списка и затем делаете два рекурсивных вызова:

• рекурсивный вызов 1 (RC1): в конец списка, но выбрать n-1 элемент
• рекурсивный вызов 2 (RC2): в конец списка, но выбрать n элементов

чтобы объединить рекурсивные результаты, умножьте список (укажите нечетное имя) на заголовок списка с результатами RC1, а затем добавьте (@) результаты RC2. Список-умножение - это следующая операция lmul:

a lmul [ l1 ; l2 ; l3] = [a::l1 ; a::l2 ; a::l3]

lmul реализован в приведенном ниже коде как

List.map (fun x -> h::x)

Рекурсия прекращается, когда размер списка равен количеству элементов, которые вы хотите выбрать, и в этом случае вы просто возвращаете сам список.

Итак, вот четырехстрочный алгоритм в OCaml, реализующий вышеуказанный алгоритм:

    let rec choose l n = match l, (List.length l) with                                 
    | _, lsize  when n==lsize  -> [l]                                
    | h::t, _ -> (List.map (fun x-> h::x) (choose t (n-1))) @ (choose t n)   
    | [], _ -> []    

Это мой вклад в javascript (без рекурсии)

set = ["q0", "q1", "q2", "q3"]
collector = []


function comb(num) {
  results = []
  one_comb = []
  for (i = set.length - 1; i >= 0; --i) {
    tmp = Math.pow(2, i)
    quotient = parseInt(num / tmp)
    results.push(quotient)
    num = num % tmp
  }
  k = 0
  for (i = 0; i < results.length; ++i)
    if (results[i]) {
      ++k
      one_comb.push(set[i])
    }
  if (collector[k] == undefined)
    collector[k] = []
  collector[k].push(one_comb)
}


sum = 0
for (i = 0; i < set.length; ++i)
  sum += Math.pow(2, i)
 for (ii = sum; ii > 0; --ii)
  comb(ii)
 cnt = 0
for (i = 1; i < collector.length; ++i) {
  n = 0
  for (j = 0; j < collector[i].length; ++j)
    document.write(++cnt, " - " + (++n) + " - ", collector[i][j], "<br>")
  document.write("<hr>")
}   

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

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

void combine(char a[], int N, int M, int m, int start, char result[]) {
    if (0 == m) {
        for (int i = M - 1; i >= 0; i--)
            std::cout << result[i];
        std::cout << std::endl;
        return;
    }
    for (int i = start; i < (N - m + 1); i++) {
        result[m - 1] = a[i];
        combine(a, N, M, m-1, i+1, result);
    }
}

void combine(char a[], int N, int M) {
    char *result = new char[M];
    combine(a, N, M, M, 0, result);
    delete[] result;
}

В первой функции m обозначает, сколько еще вам нужно выбрать, а start обозначает, с какой позиции в массиве вы должны начать выбор.

Моя реализация на c / C++

#include <unistd.h>
#include <stdio.h>
#include <iconv.h>
#include <string.h>
#include <errno.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
    int opt = -1, min_len = 0, max_len = 0;
    char ofile[256], fchar[2], tchar[2];
    ofile[0] = 0;
    fchar[0] = 0;
    tchar[0] = 0;
    while((opt = getopt(argc, argv, "o:f:t:l:L:")) != -1)
    {
            switch(opt)
            {
                    case 'o':
                    strncpy(ofile, optarg, 255);
                    break;
                    case 'f':
                    strncpy(fchar, optarg, 1);
                    break;
                    case 't':
                    strncpy(tchar, optarg, 1);
                    break;
                    case 'l':
                    min_len = atoi(optarg);
                    break;
                    case 'L':
                    max_len = atoi(optarg);
                    break;
                    default:
                    printf("usage: %s -oftlL\n\t-o output file\n\t-f from char\n\t-t to char\n\t-l min seq len\n\t-L max seq len", argv[0]);
            }
    }
if (max_len < 1)
{
    printf("error, length must be more than 0\n");
    return 1;
}
if (min_len > max_len)
{
    printf("error, max length must be greater or equal min_length\n");
    return 1;
}
if ((int)fchar[0] > (int)tchar[0])
{
    printf("error, invalid range specified\n");
    return 1;
}
FILE *out = fopen(ofile, "w");
if (!out)
{
    printf("failed to open input file with error: %s\n", strerror(errno));
    return 1;
}
int cur_len = min_len;
while(cur_len <= max_len)
{
    char buf[cur_len];
    for(int i = 0; i < cur_len; i++)
        buf[i] = fchar[0];
    fwrite(buf, cur_len, 1, out);
    fwrite("\n", 1, 1, out);
    while(buf[0] != (tchar[0]+1))
    {
        while(buf[cur_len-1] < tchar[0])
        {
            (int)buf[cur_len-1]++;
            fwrite(buf, cur_len, 1, out);
            fwrite("\n", 1, 1, out);
        }
        if (cur_len < 2)
            break;
        if (buf[0] == tchar[0])
        {
            bool stop = true;
            for(int i = 1; i < cur_len; i++)
            {
                if (buf[i] != tchar[0])
                {
                    stop = false;
                    break;
                }
            }
            if (stop)
                break;
        }
        int u = cur_len-2;
        for(; u>=0 && buf[u] >= tchar[0]; u--)
            ;
        (int)buf[u]++;
        for(int i = u+1; i < cur_len; i++)
            buf[i] = fchar[0];
        fwrite(buf, cur_len, 1, out);
        fwrite("\n", 1, 1, out);
    }
    cur_len++;
}
fclose(out);
return 0;
}

здесь моя реализация на С ++, он записывает все комбинации в указанные файлы, но поведение может быть изменено, я создал различные словари, он принимает минимальную и максимальную длину и диапазон символов, в настоящее время поддерживается только ansi, этого достаточно для моих нужд

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

1. Выводит все K-индексы в удобном формате для любого N выберите K в файл. K-индексы можно заменить более описательными строками или буквами. Этот метод делает решение такого типа задач довольно тривиальным.

2. Преобразует K-индексы в правильный индекс записи в отсортированной таблице биномиальных коэффициентов. Этот метод намного быстрее, чем старые опубликованные методы, основанные на итерациях. Это достигается с помощью математического свойства, присущего треугольнику Паскаля. Об этом говорится в моей статье. Я считаю, что я первый, кто открыл и опубликовал эту технику, но могу ошибаться.

3. Преобразует индекс в отсортированной таблице биномиальных коэффициентов в соответствующие K-индексы.

4. Использует метод Марк Доминус для вычисления биномиального коэффициента, который с меньшей вероятностью переполнится и работает с большими числами.

5. Класс написан на .NET C# и обеспечивает способ управления объектами, связанными с проблемой (если таковые имеются), с помощью общего списка. Конструктор этого класса принимает логическое значение с именем InitTable, которое, когда оно истинно, будет создавать общий список для хранения объектов, которыми нужно управлять. Если это значение ложно, таблица не будет создана. Таблицу не нужно создавать для выполнения 4 вышеуказанных методов. Для доступа к таблице предоставляются методы доступа.

6. Существует связанный тестовый класс, который показывает, как использовать класс и его методы. Он был тщательно протестирован с двумя случаями, и никаких известных ошибок нет.

Чтобы прочитать об этом классе и загрузить код, см. Табулирование биномиального коэффициента.

Преобразовать этот класс в C++ не составит труда.

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

Предположим, массив из 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.

Как насчет этого ответа ... он печатает все комбинации длины 3 ... и может быть обобщен для любой длины ... Рабочий код ...

#include<iostream>
#include<string>
using namespace std;

void combination(string a,string dest){
int l = dest.length();
if (a.empty() && l  == 3 ){
 cout<<dest<<endl;}
else{
  if (!a.empty() && dest.length() < 3 ){
     combination(a.substr(1,a.length()),dest+a[0]);}
  if (!a.empty() && dest.length() <= 3 ){
      combination(a.substr(1,a.length()),dest);}
 }

 }

 int main(){
 string demo("abcd");
 combination(demo,"");
 return 0;
 }

А вот версия Clojure, в которой используется тот же алгоритм, который я описал в своем ответе на реализацию OCaml:

(defn select
  ([items]
     (select items 0 (inc (count items))))
  ([items n1 n2]
     (reduce concat
             (map #(select % items)
                  (range n1 (inc n2)))))
  ([n items]
     (let [
           lmul (fn [a list-of-lists-of-bs]
                     (map #(cons a %) list-of-lists-of-bs))
           ]
       (if (= n (count items))
         (list items)
         (if (empty? items)
           items
           (concat
            (select n (rest items))
            (lmul (first items) (select (dec n) (rest items))))))))) 

Он предоставляет три способа называть это:

а) для выбранных элементов п, как требует вопрос:

  user=> (count (select 3 "abcdefgh"))
  56

(б) для выбранных элементов между n1 и n2:

user=> (select '(1 2 3 4) 2 3)
((3 4) (2 4) (2 3) (1 4) (1 3) (1 2) (2 3 4) (1 3 4) (1 2 4) (1 2 3))

(c) между 0 и размером выбранных элементов коллекции:

user=> (select '(1 2 3))
(() (3) (2) (1) (2 3) (1 3) (1 2) (1 2 3))

Короткая быстрая реализация на C

#include <stdio.h>

void main(int argc, char *argv[]) {
  const int n = 6; /* The size of the set; for {1, 2, 3, 4} it's 4 */
  const int p = 4; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
  int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */

  int i = 0;
  for (int j = 0; j <= n; j++) comb[j] = 0;
  while (i >= 0) {
    if (comb[i] < n + i - p + 1) {
       comb[i]++;
       if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); }
       else            { comb[++i] = comb[i - 1]; }
    } else i--; }
}

Чтобы увидеть, насколько это быстро, используйте этот код и протестируйте его.

#include <time.h>
#include <stdio.h>

void main(int argc, char *argv[]) {
  const int n = 32; /* The size of the set; for {1, 2, 3, 4} it's 4 */
  const int p = 16; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
  int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */

  int c = 0; int i = 0;
  for (int j = 0; j <= n; j++) comb[j] = 0;
  while (i >= 0) {
    if (comb[i] < n + i - p + 1) {
       comb[i]++;
       /* if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); } */
       if (i == p - 1) c++;
       else            { comb[++i] = comb[i - 1]; }
    } else i--; }
  printf("%d!%d == %d combination(s) in %15.3f second(s)\n ", p, n, c, clock()/1000.0);
}

тест с cmd.exe (windows):

Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.

c:\Program Files\lcc\projects>combination
16!32 == 601080390 combination(s) in          5.781 second(s)

c:\Program Files\lcc\projects>

Хорошего дня.

Краткое 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]

еще одно рекурсивное решение (вы должны иметь возможность перенести это, чтобы использовать буквы вместо чисел) с использованием стека, хотя немного короче, чем у большинства:

stack = [] 
def choose(n,x):
   r(0,0,n+1,x)

def r(p, c, n,x):
   if x-c == 0:
      print stack
      return

   for i in range(p, n-(x-1)+c):
      stack.append(i)
      r(i+1,c+1,n,x)
      stack.pop()

4 выберите 3 или я хочу все 3 комбинации чисел от 0 до 4

choose(4,3) 

[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 2, 3]
[0, 2, 4]
[0, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]

Вот реализация coffeescript

combinations: (list, n) ->
        permuations = Math.pow(2, list.length) - 1
        out = []
        combinations = []

        while permuations
            out = []

            for i in [0..list.length]
                y = ( 1 << i )
                if ( y & permuations and (y isnt permuations))
                    out.push(list[i])

            if out.length <= n and out.length > 0
                combinations.push(out)

            permuations--

        return combinations 

Вот мое решение Scala:

def combinations[A](s: List[A], k: Int): List[List[A]] = 
  if (k > s.length) Nil
  else if (k == 1) s.map(List(_))
  else combinations(s.tail, k - 1).map(s.head :: _) ::: combinations(s.tail, k)

#include <stdio.h>

unsigned int next_combination(unsigned int *ar, size_t n, unsigned int k)
{
    unsigned int finished = 0;
    unsigned int changed = 0;
    unsigned int i;

    if (k > 0) {
        for (i = k - 1; !finished && !changed; i--) {
            if (ar[i] < (n - 1) - (k - 1) + i) {
                /* Increment this element */
                ar[i]++;
                if (i < k - 1) {
                    /* Turn the elements after it into a linear sequence */
                    unsigned int j;
                    for (j = i + 1; j < k; j++) {
                        ar[j] = ar[j - 1] + 1;
                    }
                }
                changed = 1;
            }
            finished = i == 0;
        }
        if (!changed) {
            /* Reset to first combination */
            for (i = 0; i < k; i++) {
                ar[i] = i;
            }
        }
    }
    return changed;
}

typedef void(*printfn)(const void *, FILE *);

void print_set(const unsigned int *ar, size_t len, const void **elements,
    const char *brackets, printfn print, FILE *fptr)
{
    unsigned int i;
    fputc(brackets[0], fptr);
    for (i = 0; i < len; i++) {
        print(elements[ar[i]], fptr);
        if (i < len - 1) {
            fputs(", ", fptr);
        }
    }
    fputc(brackets[1], fptr);
}

int main(void)
{
    unsigned int numbers[] = { 0, 1, 2 };
    char *elements[] = { "a", "b", "c", "d", "e" };
    const unsigned int k = sizeof(numbers) / sizeof(unsigned int);
    const unsigned int n = sizeof(elements) / sizeof(const char*);

    do {
        print_set(numbers, k, (void*)elements, "[]", (printfn)fputs, stdout);
        putchar('\n');
    } while (next_combination(numbers, n, k));
    getchar();
    return 0;
}

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

Версия 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))))

Все сказано и сделано, вот и код O'caml для этого. Алгоритм очевиден из кода.

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

Возможно, я упустил момент (что вам нужен алгоритм, а не готовое решение), но похоже, что scala делает это из коробки (сейчас):

def combis(str:String, k:Int):Array[String] = {
  str.combinations(k).toArray 
}

Используя такой метод:

  println(combis("abcd",2).toList)

Изготовим:

  List(ab, ac, ad, bc, bd, cd)

Короткая быстрая реализация на C#

public static IEnumerable<IEnumerable<T>> Combinations<T>(IEnumerable<T> elements, int k)
{
    return Combinations(elements.Count(), k).Select(p => p.Select(q => elements.ElementAt(q)));                
}      

public static List<int[]> Combinations(int setLenght, int subSetLenght) //5, 3
{
    var result = new List<int[]>();

    var lastIndex = subSetLenght - 1;
    var dif = setLenght - subSetLenght;
    var prevSubSet = new int[subSetLenght];
    var lastSubSet = new int[subSetLenght];
    for (int i = 0; i < subSetLenght; i++)
    {
        prevSubSet[i] = i;
        lastSubSet[i] = i + dif;
    }

    while(true)
    {
        //add subSet ad result set
        var n = new int[subSetLenght];
        for (int i = 0; i < subSetLenght; i++)
            n[i] = prevSubSet[i];

        result.Add(n);

        if (prevSubSet[0] >= lastSubSet[0])
            break;

        //start at index 1 because index 0 is checked and breaking in the current loop
        int j = 1;
        for (; j < subSetLenght; j++)
        {
            if (prevSubSet[j] >= lastSubSet[j])
            {
                prevSubSet[j - 1]++;

                for (int p = j; p < subSetLenght; p++)
                    prevSubSet[p] = prevSubSet[p - 1] + 1;

                break;
            }
        }

        if (j > lastIndex)
            prevSubSet[lastIndex]++;
    }

    return result;
}

Краткое решение 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);

Вот решение C++, которое я придумал, используя рекурсию и битовый сдвиг. Это может работать и в C.

void r_nCr(unsigned int startNum, unsigned int bitVal, unsigned int testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
    unsigned int n = (startNum - bitVal) << 1;
    n += bitVal ? 1 : 0;

    for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
        cout << (n >> (i - 1) & 1);
    cout << endl;

    if (!(n & testNum) && n != startNum)
        r_nCr(n, bitVal, testNum);

    if (bitVal && bitVal < testNum)
        r_nCr(startNum, bitVal >> 1, testNum);
}

Вы можете найти объяснение, как это работает здесь.

C# простой алгоритм. (Я публикую его, так как пытался использовать тот, который вы, ребята, загрузили, но по какой-то причине я не смог его скомпилировать - расширение класса? Поэтому я написал свой собственный, на случай, если кто-то еще столкнется с той же проблемой Я сделал). Между прочим, я не слишком увлекаюсь C#, чем базовым программированием, но этот работает нормально.

public static List<List<int>> GetSubsetsOfSizeK(List<int> lInputSet, int k)
        {
            List<List<int>> lSubsets = new List<List<int>>();
            GetSubsetsOfSizeK_rec(lInputSet, k, 0, new List<int>(), lSubsets);
            return lSubsets;
        }

public static void GetSubsetsOfSizeK_rec(List<int> lInputSet, int k, int i, List<int> lCurrSet, List<List<int>> lSubsets)
        {
            if (lCurrSet.Count == k)
            {
                lSubsets.Add(lCurrSet);
                return;
            }

            if (i >= lInputSet.Count)
                return;

            List<int> lWith = new List<int>(lCurrSet);
            List<int> lWithout = new List<int>(lCurrSet);
            lWith.Add(lInputSet[i++]);

            GetSubsetsOfSizeK_rec(lInputSet, k, i, lWith, lSubsets);
            GetSubsetsOfSizeK_rec(lInputSet, k, i, lWithout, lSubsets);
        }

ИСПОЛЬЗОВАНИЕ: GetSubsetsOfSizeK(set of type List<int>, integer k)

Вы можете изменить его, чтобы перебирать все, с чем вы работаете.

Удачи!

Короткий алгоритм php для возврата всех комбинаций k элементов из n (биномиальный коэффициент) на основе решения java:

$array = array(1,2,3,4,5);

$array_result = NULL;

$array_general = NULL;

function combinations($array, $len, $start_position, $result_array, $result_len, &$general_array)
{
    if ($len == 0)
    {
        $general_array[] = $result_array;
        return;
    }

    for ($i = $start_position; $i <= count($array) - $len; $i++)
    {
        $result_array[$result_len - $len] = $array[$i];
        combinations($array, $len-1, $i+1, $result_array, $result_len, $general_array);
    }
} 

combinations($array, 3, 0, $array_result, 3, $array_general);

echo "<pre>";
print_r($array_general);
echo "</pre>";

То же решение, но в javascript:

var newArray = [1, 2, 3, 4, 5];
var arrayResult = [];
var arrayGeneral = [];

function combinations(newArray, len, startPosition, resultArray, resultLen, arrayGeneral) {
    if (len === 0) {
        var tempArray = [];
        resultArray.forEach(value => tempArray.push(value));
        arrayGeneral.push(tempArray);
        return;
    }
    for (var i = startPosition; i <= newArray.length - len; i++) {
        resultArray[resultLen - len] = newArray[i];
        combinations(newArray, len-1, i+1, resultArray, resultLen, arrayGeneral);
    }
} 

combinations(newArray, 3, 0, arrayResult, 3, arrayGeneral);

console.info(arrayGeneral);

Вот алгоритм, который я придумал для решения этой проблемы. Он написан на C++, но может быть адаптирован практически к любому языку, поддерживающему побитовые операции.

void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const unsigned int &testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
    unsigned int n = (startNum - bitVal) << 1;
    n += bitVal ? 1 : 0;

    for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
        cout << (n >> (i - 1) & 1);
    cout << endl;

    if (!(n & testNum) && n != startNum)
        r_nCr(n, bitVal, testNum);

    if (bitVal && bitVal < testNum)
        r_nCr(startNum, bitVal >> 1, testNum);
}

Вы можете увидеть объяснение, как это работает здесь.

короткий код 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

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

Вот мое решение JavaScript, которое немного более функционально за счет использования reduce / map, которое устраняет почти все переменные.

function combinations(arr, size) {
  var len = arr.length;

  if (size > len) return [];
  if (!size) return [[]];
  if (size == len) return [arr];

  return arr.reduce(function (acc, val, i) {
    var res = combinations(arr.slice(i + 1), size - 1)
      .map(function (comb) { return [val].concat(comb); });
    
    return acc.concat(res);
  }, []);
}

var combs = combinations([1,2,3,4,5,6,7,8],3);
combs.map(function (comb) {
  document.body.innerHTML += comb.toString() + '<br />';
});

document.body.innerHTML += '<br /> Total combinations = ' + combs.length;

Код C для алгоритма L (лексикографические комбинации) в разделе 7.2.1.3 документа Искусство программирования, Том 4A: Комбинаторные алгоритмы, Часть 1:

#include <stdio.h>
#include <stdlib.h>

void visit(int* c, int t) 
{
  // for (int j = 1; j <= t; j++)
  for (int j = t; j > 0; j--)
    printf("%d ", c[j]);
  printf("\n");
}

int* initialize(int n, int t) 
{
  // c[0] not used
  int *c = (int*) malloc((t + 3) * sizeof(int));

  for (int j = 1; j <= t; j++)
    c[j] = j - 1;
  c[t+1] = n;
  c[t+2] = 0;
  return c;
}

void comb(int n, int t) 
{
  int *c = initialize(n, t);
  int j;

  for (;;) {
    visit(c, t);
    j = 1;
    while (c[j]+1 == c[j+1]) {
      c[j] = j - 1;
      ++j;
    }
    if (j > t) 
      return;
    ++c[j];
  }
  free(c);
}

int main(int argc, char *argv[])
{
  comb(5, 3);
  return 0;
}

Прыгаем на подножку и публикуем другое решение. Это общая реализация 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;
}

Рекурсивно, очень простой ответ, combo, в Free Pascal.

    procedure combinata (n, k :integer; producer :oneintproc);

        procedure combo (ndx, nbr, len, lnd :integer);
        begin
            for nbr := nbr to len do begin
                productarray[ndx] := nbr;
                if len < lnd then
                    combo(ndx+1,nbr+1,len+1,lnd)
                else
                    producer(k);
            end;
        end;

    begin
        combo (0, 0, n-k, n-1);
    end;

«производитель» распоряжается набором продуктов, созданным для каждой комбинации.

Я искал аналогичное решение для PHP и наткнулся на следующие

class Combinations implements Iterator
{
    protected $c = null;
    protected $s = null;
    protected $n = 0;
    protected $k = 0;
    protected $pos = 0;

    function __construct($s, $k) {
        if (is_array($s)) {
            $this->s = array_values($s);
            $this->n = count($this->s);
        } else {
            $this->s = (string) $s;
            $this->n = strlen($this->s);
        }
        $this->k = $k;
        $this->rewind();
    }
    function key() {
        return $this->pos;
    }
    function current() {
        $r = array();
        for($i = 0; $i < $this->k; $i++)
            $r[] = $this->s[$this->c[$i]];
        return is_array($this->s) ? $r : implode('', $r);
    }
    function next() {
        if ($this->_next())
            $this->pos++;
        else
            $this->pos = -1;
    }
    function rewind() {
        $this->c = range(0, $this->k);
        $this->pos = 0;
    }
    function valid() {
        return $this->pos >= 0;
    }

    protected function _next() {
        $i = $this->k - 1;
        while ($i >= 0 && $this->c[$i] == $this->n - $this->k + $i)
            $i--;
        if ($i < 0)
            return false;
        $this->c[$i]++;
        while($i++ < $this->k - 1)
            $this->c[$i] = $this->c[$i - 1] + 1;
        return true;
    }
}


foreach(new Combinations("1234567", 5) as $substring)
    echo $substring, ' ';

источник

Не уверен, насколько эффективен этот класс, но я использовал его только для сеялки.

Нет необходимости в манипуляциях с коллекциями. Проблема почти такая же, как и при переключении по K вложенным циклам, но вы должны быть осторожны с индексами и границами (игнорируя Java и материал ООП):

 public class CombinationsGen {
    private final int n;
    private final int k;
    private int[] buf;

    public CombinationsGen(int n, int k) {
        this.n = n;
        this.k = k;
    }

    public void combine(Consumer<int[]> consumer) {
        buf = new int[k];
        rec(0, 0, consumer);
    }

    private void rec(int index, int next, Consumer<int[]> consumer) {
        int max = n - index;

        if (index == k - 1) {
            for (int i = 0; i < max && next < n; i++) {
                buf[index] = next;
                next++;
                consumer.accept(buf);
            }
        } else {
            for (int i = 0; i < max && next + index < n; i++) {
                buf[index] = next;
                next++;
                rec(index + 1, next, consumer);
            }
        }
    }
}

Используйте так:

 CombinationsGen gen = new CombinationsGen(5, 2);

 AtomicInteger total = new AtomicInteger();
 gen.combine(arr -> {
     System.out.println(Arrays.toString(arr));
     total.incrementAndGet();
 });
 System.out.println(total);

Получите ожидаемые результаты:

[0, 1]
[0, 2]
[0, 3]
[0, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
10

Наконец, сопоставьте индексы с любым набором данных, который у вас может быть.

Хочу представить свое решение. В next нет рекурсивных вызовов и вложенных циклов. Ядром кода является метод next().

public class Combinations {
    final int pos[];
    final List<Object> set;

    public Combinations(List<?> l, int k) {
        pos = new int[k];
        set=new ArrayList<Object>(l);
        reset();
    }
    public void reset() {
        for (int i=0; i < pos.length; ++i) pos[i]=i;
    }
    public boolean next() {
        int i = pos.length-1;
        for (int maxpos = set.size()-1; pos[i] >= maxpos; --maxpos) {
            if (i==0) return false;
            --i;
        }
        ++pos[i];
        while (++i < pos.length)
            pos[i]=pos[i-1]+1;
        return true;
    }

    public void getSelection(List<?> l) {
        @SuppressWarnings("unchecked")
        List<Object> ll = (List<Object>)l;
        if (ll.size()!=pos.length) {
            ll.clear();
            for (int i=0; i < pos.length; ++i)
                ll.add(set.get(pos[i]));
        }
        else {
            for (int i=0; i < pos.length; ++i)
                ll.set(i, set.get(pos[i]));
        }
    }
}

И пример использования:

static void main(String[] args) {
    List<Character> l = new ArrayList<Character>();
    for (int i=0; i < 32; ++i) l.add((char)('a'+i));
    Combinations comb = new Combinations(l,5);
    int n=0;
    do {
        ++n;
        comb.getSelection(l);
        //Log.debug("%d: %s", n, l.toString());
    } while (comb.next());
    Log.debug("num = %d", n);
}

Простой, но медленный алгоритм поиска с возвратом в C++.

#include <iostream>

void backtrack(int* numbers, int n, int k, int i, int s)
{
    if (i == k)
    {
        for (int j = 0; j < k; ++j)
        {
            std::cout << numbers[j];
        }
        std::cout << std::endl;

        return;
    }

    if (s > n)
    {
        return;
    }

    numbers[i] = s;
    backtrack(numbers, n, k, i + 1, s + 1);
    backtrack(numbers, n, k, i, s + 1);
}

int main(int argc, char* argv[])
{
    int n = 5;
    int k = 3;

    int* numbers = new int[k];

    backtrack(numbers, n, k, 0, 1);

    delete[] numbers;

    return 0;
}

Еще одно решение с C#:

 static List<List<T>> GetCombinations<T>(List<T> originalItems, int combinationLength)
    {
        if (combinationLength < 1)
        {
            return null;
        }

        return CreateCombinations<T>(new List<T>(), 0, combinationLength, originalItems);
    }

 static List<List<T>> CreateCombinations<T>(List<T> initialCombination, int startIndex, int length, List<T> originalItems)
    {
        List<List<T>> combinations = new List<List<T>>();
        for (int i = startIndex; i < originalItems.Count - length + 1; i++)
        {
            List<T> newCombination = new List<T>(initialCombination);
            newCombination.Add(originalItems[i]);
            if (length > 1)
            {
                List<List<T>> newCombinations = CreateCombinations(newCombination, i + 1, length - 1, originalItems);
                combinations.AddRange(newCombinations);
            }
            else
            {
                combinations.Add(newCombination);
            }
        }

        return combinations;
    }

Пример использования:

   List<char> initialArray = new List<char>() { 'a','b','c','d'};
   int combinationLength = 3;
   List<List<char>> combinations = GetCombinations(initialArray, combinationLength);

Алгоритм:

• Посчитайте от 1 до 2 ^ n.
• Преобразуйте каждую цифру в ее двоичное представление.
• Преобразуйте каждый бит включения в элементы вашего набора в зависимости от позиции.

В 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, чтобы найти все комбинации. (мы игнорируем пустой набор.) Затем переводим цифры в их двоичное представление. Затем замените элементы вашего набора на «включенные» биты.

Если вам нужны результаты только для k элементов, печатайте только тогда, когда k битов включены.

(Если вам нужны все подмножества вместо подмножеств длины k, удалите часть cnt / kElement.)

(Для доказательства см. Бесплатные курсы MIT «Математика для компьютерных наук», Lehman et al, раздел 11.2.2. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mat Mathematics-for-computer-science-fall-2010/readings/)

Допустим, ваш массив букв выглядит так: «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

Как только вы j достигнете 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, но более абстрактно, для указателей любого размера.

Для этого мы можем использовать концепцию битов. Пусть у нас есть строка «abc», и мы хотим иметь все комбинации элементов длиной 2 (то есть «ab», «ac», «bc».)

Мы можем найти установленные биты в числах от 1 до 2 ^ n (исключая). Здесь от 1 до 7, и где бы мы ни установили биты = 2, мы можем вывести соответствующее значение из строки.

Например:

• 1 - 001
• 2 - 010
• 3 - 011 -> print ab (str[0] , str[1])
• 4–100
• 5 - 101 -> print ac (str[0] , str[2])
• 6 - 110 -> print ab (str[1] , str[2])
• 7 - 111.

Пример кода:

public class StringCombinationK {   
    static void combk(String s , int k){
        int n = s.length();
        int num = 1<<n;
        int j=0;
        int count=0;

        for(int i=0;i<num;i++){
            if (countSet(i)==k){
                setBits(i,j,s);
                count++;
                System.out.println();
            }
        }

        System.out.println(count);
    }

    static void setBits(int i,int j,String s){ // print the corresponding string value,j represent the index of set bit
        if (i==0){
            return;
        }

        if (i%2==1){
            System.out.print(s.charAt(j));                  
        }

        setBits(i/2,j+1,s);
    }

    static int countSet(int i){ //count number of set bits
        if ( i==0){
            return 0;
        }

        return (i%2==0? 0:1) + countSet(i/2);
    }

    public static void main(String[] arhs){
        String s = "abcdefgh";
        int k=3;
        combk(s,k);
    }
}

Я сделал общий класс для комбинаций на C++. Используется вот так.

char ar[] = "0ABCDEFGH";
nCr ncr(8, 3);
while(ncr.next()) {
    for(int i=0; i<ncr.size(); i++) cout << ar[ncr[i]];
    cout << ' ';
}

Моя библиотека ncr [i] возвращается с 1, а не с 0. Вот почему в массиве 0. Если вы хотите учитывать порядок, просто измените класс nCr на nPr. Использование идентично.

Результат

ABC ABD ABE ABF ABG ABH ACD ТУЗ ACF АЧГ ACH ADE АПД ADG ADH AEF AEG AEH AFG AFH AGH BCD До н.э. BCF BCG BCH BDE BDF БДГ BDH BEF ПРОСИТЬ BEH BFG BFH BGH CDE CDF CDG CDH CEF CEG CEH CFG CFH CGH DEF ГРАДУС DEH DFG DFH DGH EFG EFH EGH FGH

Вот и заголовочный файл.

#pragma once
#include <exception>

class NRexception : public std::exception
{
public:
    virtual const char* what() const throw() {
        return "Combination : N, R should be positive integer!!";
    }
};

class Combination
{
public:
    Combination(int n, int r);
    virtual ~Combination() { delete [] ar;}
    int& operator[](unsigned i) {return ar[i];}
    bool next();
    int size() {return r;}
    static int factorial(int n);

protected:
    int* ar;
    int n, r;
};

class nCr : public Combination
{
public: 
    nCr(int n, int r);
    bool next();
    int count() const;
};

class nTr : public Combination
{
public:
    nTr(int n, int r);
    bool next();
    int count() const;
};

class nHr : public nTr
{
public:
    nHr(int n, int r) : nTr(n,r) {}
    bool next();
    int count() const;
};

class nPr : public Combination
{
public:
    nPr(int n, int r);
    virtual ~nPr() {delete [] on;}
    bool next();
    void rewind();
    int count() const;

private:
    bool* on;
    void inc_ar(int i);
};

И реализация.

#include "combi.h"
#include <set>
#include<cmath>

Combination::Combination(int n, int r)
{
    //if (n < 1 || r < 1) throw NRexception();
    ar = new int[r];
    this->n = n;
    this->r = r;
}

int Combination::factorial(int n) 
{
    return n == 1 ? n : n * factorial(n-1);
}

int nPr::count() const
{
    return factorial(n)/factorial(n-r);
}

int nCr::count() const
{
    return factorial(n)/factorial(n-r)/factorial(r);
}

int nTr::count() const
{
    return pow(n, r);
}

int nHr::count() const
{
    return factorial(n+r-1)/factorial(n-1)/factorial(r);
}

nCr::nCr(int n, int r) : Combination(n, r)
{
    if (r == 0) return;
    for(int i=0; i<r-1; i++) ar[i] = i + 1;
    ar[r-1] = r-1;
}

nTr::nTr(int n, int r) : Combination(n, r)
{
    for(int i=0; i<r-1; i++) ar[i] = 1;
    ar[r-1] = 0;
}

bool nCr::next()
{
    if (r == 0) return false;
    ar[r-1]++;
    int i = r-1;
    while(ar[i] == n-r+2+i) {
        if (--i == -1) return false;
        ar[i]++;
    }
    while(i < r-1) ar[i+1] = ar[i++] + 1;
    return true;
}

bool nTr::next()
{
    ar[r-1]++;
    int i = r-1;
    while(ar[i] == n+1) {
        ar[i] = 1;
        if (--i == -1) return false;
        ar[i]++;
    }
    return true;
}

bool nHr::next()
{
    ar[r-1]++;
    int i = r-1;
    while(ar[i] == n+1) {
        if (--i == -1) return false;
        ar[i]++;
    }
    while(i < r-1) ar[i+1] = ar[i++];
    return true;
}

nPr::nPr(int n, int r) : Combination(n, r)
{
    on = new bool[n+2];
    for(int i=0; i<n+2; i++) on[i] = false;
    for(int i=0; i<r; i++) {
        ar[i] = i + 1;
        on[i] = true;
    }
    ar[r-1] = 0;
}

void nPr::rewind()
{
    for(int i=0; i<r; i++) {
        ar[i] = i + 1;
        on[i] = true;
    }
    ar[r-1] = 0;
}

bool nPr::next()
{   
    inc_ar(r-1);

    int i = r-1;
    while(ar[i] == n+1) {
        if (--i == -1) return false;
        inc_ar(i);
    }
    while(i < r-1) {
        ar[++i] = 0;
        inc_ar(i);
    }
    return true;
}

void nPr::inc_ar(int i)
{
    on[ar[i]] = false;
    while(on[++ar[i]]);
    if (ar[i] != n+1) on[ar[i]] = true;
}

Очень быстрые комбинации для MetaTrader MQL4, реализованные в виде объекта-итератора.

Код настолько прост для понимания.

Я протестировал множество алгоритмов, этот действительно очень быстрый - примерно в 3 раза быстрее, чем большинство функций next_combination ().

class CombinationsIterator
{
private:
	int input_array[];  // 1 2 3 4 5
	int index_array[];  // i j k
	int m_elements;     // N
	int m_indices;      // K

public:
	CombinationsIterator(int &src_data[], int k)
	{
		m_indices = k;
		m_elements = ArraySize(src_data);
		ArrayCopy(input_array, src_data);
		ArrayResize(index_array, m_indices);

		// create initial combination (0..k-1)
		for (int i = 0; i < m_indices; i++)
		{
			index_array[i] = i;
		}
	}

	// https://stackoverflow.com/questions/5076695
	// bool next_combination(int &item[], int k, int N)
	bool advance()
	{
		int N = m_elements;
		for (int i = m_indices - 1; i >= 0; --i)
		{
			if (index_array[i] < --N)
			{
				++index_array[i];
				for (int j = i + 1; j < m_indices; ++j)
				{
					index_array[j] = index_array[j - 1] + 1;
				}
				return true;
			}
		}
		return false;
	}

	void getItems(int &items[])
	{
		// fill items[] from input array
		for (int i = 0; i < m_indices; i++)
		{
			items[i] = input_array[index_array[i]];
		}
	}
};

Программа драйвера для проверки указанного выше класса итератора:

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
// driver program to test above class

#define N 5
#define K 3

void OnStart()
{
	int myset[N] = {1, 2, 3, 4, 5};
	int items[K];

	CombinationsIterator comboIt(myset, K);

	do
	{
		comboIt.getItems(items);

		printf("%s", ArrayToString(items));

	} while (comboIt.advance());

}

Output:
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5

Вот простое решение JS:

function getAllCombinations(n, k, f1) {
	indexes = Array(k);
  for (let i =0; i< k; i++) {
  	indexes[i] = i;
  }
  var total = 1;
  f1(indexes);
  while (indexes[0] !== n-k) {
  	total++;
		getNext(n, indexes);
    f1(indexes);
  }
  return {total};
}

function getNext(n, vec) {
	const k = vec.length;
  vec[k-1]++;
	for (var i=0; i<k; i++) {
  	var currentIndex = k-i-1;
    if (vec[currentIndex] === n - i) {
	  	var nextIndex = k-i-2;
      vec[nextIndex]++;
      vec[currentIndex] = vec[nextIndex] + 1;
    }
  }

	for (var i=1; i<k; i++) {
    if (vec[i] === n - (k-i - 1)) {
      vec[i] = vec[i-1] + 1;
    }
  }
	return vec;
} 



let start = new Date();
let result = getAllCombinations(10, 3, indexes => console.info(indexes)); 
let runTime = new Date() - start; 

console.info({
result, runTime
});

Вот подход Lisp с использованием макроса. Это работает в Common Lisp и должно работать в других диалектах Lisp.

Приведенный ниже код создает n вложенных циклов и выполняет произвольный фрагмент кода (хранящийся в переменной body) для каждой комбинации n элементов из списка lst. Переменная var указывает на список, содержащий переменные, используемые для циклов.

(defmacro do-combinations ((var lst num) &body body)
  (loop with syms = (loop repeat num collect (gensym))
        for i on syms
        for k = `(loop for ,(car i) on (cdr ,(cadr i))
                         do (let ((,var (list ,@(reverse syms)))) (progn ,@body)))
                then `(loop for ,(car i) on ,(if (cadr i) `(cdr ,(cadr i)) lst) do ,k)
        finally (return k)))

Посмотрим...

(macroexpand-1 '(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p))))

(LOOP FOR #:G3217 ON '(1 2 3 4 5 6 7) DO
 (LOOP FOR #:G3216 ON (CDR #:G3217) DO
  (LOOP FOR #:G3215 ON (CDR #:G3216) DO
   (LOOP FOR #:G3214 ON (CDR #:G3215) DO
    (LET ((P (LIST #:G3217 #:G3216 #:G3215 #:G3214)))
     (PROGN (PPRINT (MAPCAR #'CAR P))))))))

(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p)))

(1 2 3 4)
(1 2 3 5)
(1 2 3 6)
...

Поскольку комбинации не сохраняются по умолчанию, объем хранилища сведен к минимуму. Возможность выбора кода body вместо сохранения всех результатов также обеспечивает большую гибкость.

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

import Data.Semigroup
import Data.Monoid

data Comb = MkComb {count :: Int, combinations :: [[Int]]} deriving (Show, Eq, Ord)

instance Semigroup Comb where
    (MkComb c1 cs1) <> (MkComb c2 cs2) = MkComb (c1 + c2) (cs1 ++ cs2)

instance Monoid Comb where
    mempty = MkComb 0 []

addElem :: Comb -> Int -> Comb
addElem (MkComb c cs) x = MkComb c (map (x :) cs)

comb :: Int -> Int -> Comb
comb n k | n < 0 || k < 0 = error "error in `comb n k`, n and k should be natural number"
comb n k | k == 0 || k == n = MkComb 1 [(take k [k-1,k-2..0])]
comb n k | n < k = mempty
comb n k = comb (n-1) k <> (comb (n-1) (k-1) `addElem` (n-1))

Это работает так:

*Main> comb 0 1
MkComb {count = 0, combinations = []}

*Main> comb 0 0
MkComb {count = 1, combinations = [[]]}

*Main> comb 1 1
MkComb {count = 1, combinations = [[0]]}

*Main> comb 4 2
MkComb {count = 6, combinations = [[1,0],[2,0],[2,1],[3,0],[3,1],[3,2]]}

*Main> count (comb 10 5)
252

JavaScript, основанный на генераторе, рекурсивный подход:

function *nCk(n,k){
  for(var i=n-1;i>=k-1;--i)
    if (k===1)
      yield [i];
    else
      for(var temp of nCk(i,k-1)){
        temp.unshift(i);
        yield temp;
      }
}

function test(){
  try{
    var n=parseInt(ninp.value);
    var k=parseInt(kinp.value);
    log.innerText = "";
    var stop=Date.now()+1000;
    if (k>=1)
      for(var res of nCk(n,k))
        if (Date.now()<stop)
          log.innerText+=JSON.stringify(res)+" ";
        else{
          log.innerText+ = "1 second passed, stopping here.";
          break;
        }
  }catch(ex){}
}

n:<input id = "ninp" oninput = "test()">
&gt;= k:<input id = "kinp" oninput = "test()"> &gt;= 1
<div id = "log"></div>

Таким образом (уменьшая i и unshift()) он производит комбинации и элементы внутри комбинаций в порядке убывания, что несколько радует глаз. Тест останавливается через 1 секунду, поэтому ввод странных чисел относительно безопасен.

Я знаю, что на это уже есть МНОГО ответов, но я подумал, что добавлю свой собственный индивидуальный вклад в JavaScript, который состоит из двух функций - одна для генерации всех возможных различных k-подмножеств исходного n- набор элементов, и один для использования этой первой функции для создания набора мощности исходного набора из n элементов.

Вот код для двух функций:

//Generate combination subsets from a base set of elements (passed as an array). This function should generate an
//array containing nCr elements, where nCr = n!/[r! (n-r)!].

//Arguments:

//[1] baseSet :     The base set to create the subsets from (e.g., ["a", "b", "c", "d", "e", "f"])
//[2] cnt :         The number of elements each subset is to contain (e.g., 3)

function MakeCombinationSubsets(baseSet, cnt)
{
    var bLen = baseSet.length;
    var indices = [];
    var subSet = [];
    var done = false;
    var result = [];        //Contains all the combination subsets generated
    var done = false;
    var i = 0;
    var idx = 0;
    var tmpIdx = 0;
    var incr = 0;
    var test = 0;
    var newIndex = 0;
    var inBounds = false;
    var tmpIndices = [];
    var checkBounds = false;

    //First, generate an array whose elements are indices into the base set ...

    for (i=0; i<cnt; i++)

        indices.push(i);

    //Now create a clone of this array, to be used in the loop itself ...

        tmpIndices = [];

        tmpIndices = tmpIndices.concat(indices);

    //Now initialise the loop ...

    idx = cnt - 1;      //point to the last element of the indices array
    incr = 0;
    done = false;
    while (!done)
    {
    //Create the current subset ...

        subSet = [];    //Make sure we begin with a completely empty subset before continuing ...

        for (i=0; i<cnt; i++)

            subSet.push(baseSet[tmpIndices[i]]);    //Create the current subset, using items selected from the
                                                    //base set, using the indices array (which will change as we
                                                    //continue scanning) ...

    //Add the subset thus created to the result set ...

        result.push(subSet);

    //Now update the indices used to select the elements of the subset. At the start, idx will point to the
    //rightmost index in the indices array, but the moment that index moves out of bounds with respect to the
    //base set, attention will be shifted to the next left index.

        test = tmpIndices[idx] + 1;

        if (test >= bLen)
        {
        //Here, we're about to move out of bounds with respect to the base set. We therefore need to scan back,
        //and update indices to the left of the current one. Find the leftmost index in the indices array that
        //isn't going to  move out of bounds with respect to the base set ...

            tmpIdx = idx - 1;
            incr = 1;

            inBounds = false;       //Assume at start that the index we're checking in the loop below is out of bounds
            checkBounds = true;

            while (checkBounds)
            {
                if (tmpIdx < 0)
                {
                    checkBounds = false;    //Exit immediately at this point
                }
                else
                {
                    newIndex = tmpIndices[tmpIdx] + 1;
                    test = newIndex + incr;

                    if (test >= bLen)
                    {
                    //Here, incrementing the current selected index will take that index out of bounds, so
                    //we move on to the next index to the left ...

                        tmpIdx--;
                        incr++;
                    }
                    else
                    {
                    //Here, the index will remain in bounds if we increment it, so we
                    //exit the loop and signal that we're in bounds ...

                        inBounds = true;
                        checkBounds = false;

                    //End if/else
                    }

                //End if 
                }               
            //End while
            }
    //At this point, if we'er still in bounds, then we continue generating subsets, but if not, we abort immediately.

            if (!inBounds)
                done = true;
            else
            {
            //Here, we're still in bounds. We need to update the indices accordingly. NOTE: at this point, although a
            //left positioned index in the indices array may still be in bounds, incrementing it to generate indices to
            //the right may take those indices out of bounds. We therefore need to check this as we perform the index
            //updating of the indices array.

                tmpIndices[tmpIdx] = newIndex;

                inBounds = true;
                checking = true;
                i = tmpIdx + 1;

                while (checking)
                {
                    test = tmpIndices[i - 1] + 1;   //Find out if incrementing the left adjacent index takes it out of bounds

                    if (test >= bLen)
                    {
                        inBounds = false;           //If we move out of bounds, exit NOW ...
                        checking = false;
                    }
                    else
                    {
                        tmpIndices[i] = test;       //Otherwise, update the indices array ...

                        i++;                        //Now move on to the next index to the right in the indices array ...

                        checking = (i < cnt);       //And continue until we've exhausted all the indices array elements ...
                    //End if/else
                    }
                //End while
                }
                //At this point, if the above updating of the indices array has moved any of its elements out of bounds,
                //we abort subset construction from this point ...
                if (!inBounds)
                    done = true;
            //End if/else
            }
        }
        else
        {
        //Here, the rightmost index under consideration isn't moving out of bounds with respect to the base set when
        //we increment it, so we simply increment and continue the loop ...
            tmpIndices[idx] = test;
        //End if
        }
    //End while
    }
    return(result);
//End function
}


function MakePowerSet(baseSet)
{
    var bLen = baseSet.length;
    var result = [];
    var i = 0;
    var partialSet = [];

    result.push([]);    //add the empty set to the power set

    for (i=1; i<bLen; i++)
    {
        partialSet = MakeCombinationSubsets(baseSet, i);
        result = result.concat(partialSet);
    //End i loop
    }
    //Now, finally, add the base set itself to the power set to make it complete ...

    partialSet = [];
    partialSet.push(baseSet);
    result = result.concat(partialSet);

    return(result);
    //End function
}

Я проверил это с набором ["a", "b", "c", "d", "e", "f"] в качестве базового набора и запустил код для получения следующего набора мощности:

[]
["a"]
["b"]
["c"]
["d"]
["e"]
["f"]
["a","b"]
["a","c"]
["a","d"]
["a","e"]
["a","f"]
["b","c"]
["b","d"]
["b","e"]
["b","f"]
["c","d"]
["c","e"]
["c","f"]
["d","e"]
["d","f"]
["e","f"]
["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"]
["a","b","c","d"]
["a","b","c","e"]
["a","b","c","f"]
["a","b","d","e"]
["a","b","d","f"]
["a","b","e","f"]
["a","c","d","e"]
["a","c","d","f"]
["a","c","e","f"]
["a","d","e","f"]
["b","c","d","e"]
["b","c","d","f"]
["b","c","e","f"]
["b","d","e","f"]
["c","d","e","f"]
["a","b","c","d","e"]
["a","b","c","d","f"]
["a","b","c","e","f"]
["a","b","d","e","f"]
["a","c","d","e","f"]
["b","c","d","e","f"]
["a","b","c","d","e","f"]

Просто скопируйте и вставьте эти две функции «как есть», и у вас будут основы, необходимые для извлечения различных k-подмножеств набора из n элементов, и сгенерирует набор мощности этого набора из n элементов, если хотите.

Я не утверждаю, что это элегантно, просто он работает после долгого тестирования (и превращения воздуха в синий на этапе отладки :)).

Короткая версия javascript (ES 5)

let combine = (list, n) =>
  n == 0 ?
    [[]] :
    list.flatMap((e, i) =>
      combine(
        list.slice(i + 1),
        n - 1
      ).map(c => [e].concat(c))
    );

let res = combine([1,2,3,4], 3);
res.forEach(e => console.info(e.join()));

Ниже приведен итерационный алгоритм на C++, в котором не использует ни STL, ни рекурсия, ни условные вложенные циклы. Это быстрее, он не выполняет замену элементов и не нагружает стек рекурсией, а также его можно легко перенести на ANSI C, заменив mallloc(), free() и printf() на new, delete и std::cout соответственно.

Если вы хотите отображать элементы с другим или более длинным алфавитом, измените параметр *alphabet, чтобы он указывал на строку, отличную от "abcdefg".

void OutputArrayChar(unsigned int* ka, size_t n, const char *alphabet) {
    for (int i = 0; i < n; i++)
        std::cout << alphabet[ka[i]] << ",";
    std::cout << endl;
}
    

void GenCombinations(const unsigned int N, const unsigned int K, const char *alphabet) {
    unsigned int *ka = new unsigned int [K];  //dynamically allocate an array of UINTs
    unsigned int ki = K-1;                    //Point ki to the last elemet of the array
    ka[ki] = N-1;                             //Prime the last elemet of the array.
    
    while (true) {
        unsigned int tmp = ka[ki];  //Optimization to prevent reading ka[ki] repeatedly

        while (ki)                  //Fill to the left with consecutive descending values (blue squares)
            ka[--ki] = --tmp;
        OutputArrayChar(ka, K, alphabet);
    
        while (--ka[ki] == ki) {    //Decrement and check if the resulting value equals the index (bright green squares)
            OutputArrayChar(ka, K, alphabet);
            if (++ki == K) {      //Exit condition (all of the values in the array are flush to the left)
                delete[] ka;
                return;
            }                   
        }
    }
}
    

int main(int argc, char *argv[])
{
    GenCombinations(7, 4, "abcdefg");
    return 0;
}

ВАЖНО: параметр *alphabet должен указывать на строку, содержащую не менее N символов. Вы также можете передать адрес строки, которая определена где-то еще.

Комбинации: Из «7 Выбери 4».

Вот простое и непонятное рекурсивное решение C++:

#include<vector>
using namespace std;

template<typename T>
void ksubsets(const vector<T>& arr, unsigned left, unsigned idx,
    vector<T>& lst, vector<vector<T>>& res)
{
    if (left < 1) {
        res.push_back(lst);
        return;
    }
    for (unsigned i = idx; i < arr.size(); i++) {
        lst.push_back(arr[i]);
        ksubsets(arr, left - 1, i + 1, lst, res);
        lst.pop_back();
    }
}

int main()
{
    vector<int> arr = { 1, 2, 3, 4, 5 };
    unsigned left = 3;
    vector<int> lst;
    vector<vector<int>> res;
    ksubsets<int>(arr, left, 0, lst, res);
    // now res has all the combinations
}