640

I want to write a function that takes an array of letters as an argument and a number of those letters to select.

Say you provide an array of 8 letters and want to select 3 letters from that. Then you should get:

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

Arrays (or words) in return consisting of 3 letters each.

9
  • 4
    Any preference of programming language? Sep 24, 2008 at 15:13
  • 9
    How do you want to deal with duplicate letters?
    – wcm
    Sep 24, 2008 at 15:21
  • No preference of language, i'm gonna code it in ruby but a general idea of what algorithms to use would be fine. Two letters of same value could exist but not the exact same letter twice.
    – Fredrik
    Sep 24, 2008 at 15:32
  • flash as3 solution stackoverflow.com/questions/4576313/…
    – Daniel
    Jan 2, 2011 at 6:28
  • In php, the following should do the trick: stackoverflow.com/questions/4279722/…
    – Kemal Dağ
    Jan 16, 2012 at 13:16

77 Answers 77

454
+500

Art of Computer Programming Volume 4: Fascicle 3 has a ton of these that might fit your particular situation better than how I describe.

Gray Codes

An issue that you will come across is of course memory and pretty quickly, you'll have problems by 20 elements in your set -- 20C3 = 1140. And if you want to iterate over the set it's best to use a modified gray code algorithm so you aren't holding all of them in memory. These generate the next combination from the previous and avoid repetitions. There are many of these for different uses. Do we want to maximize the differences between successive combinations? minimize? et cetera.

Some of the original papers describing gray codes:

  1. Some Hamilton Paths and a Minimal Change Algorithm
  2. Adjacent Interchange Combination Generation Algorithm

Here are some other papers covering the topic:

  1. An Efficient Implementation of the Eades, Hickey, Read Adjacent Interchange Combination Generation Algorithm (PDF, with code in Pascal)
  2. Combination Generators
  3. Survey of Combinatorial Gray Codes (PostScript)
  4. An Algorithm for Gray Codes

Chase's Twiddle (algorithm)

Phillip J Chase, `Algorithm 382: Combinations of M out of N Objects' (1970)

The algorithm in C...

Index of Combinations in Lexicographical Order (Buckles Algorithm 515)

You can also reference a combination by its index (in lexicographical order). Realizing that the index should be some amount of change from right to left based on the index we can construct something that should recover a combination.

So, we have a set {1,2,3,4,5,6}... and we want three elements. Let's say {1,2,3} we can say that the difference between the elements is one and in order and minimal. {1,2,4} has one change and is lexicographically number 2. So the number of 'changes' in the last place accounts for one change in the lexicographical ordering. The second place, with one change {1,3,4} has one change but accounts for more change since it's in the second place (proportional to the number of elements in the original set).

The method I've described is a deconstruction, as it seems, from set to the index, we need to do the reverse – which is much trickier. This is how Buckles solves the problem. I wrote some C to compute them, with minor changes – I used the index of the sets rather than a number range to represent the set, so we are always working from 0...n. Note:

  1. Since combinations are unordered, {1,3,2} = {1,2,3} --we order them to be lexicographical.
  2. This method has an implicit 0 to start the set for the first difference.

Index of Combinations in Lexicographical Order (McCaffrey)

There is another way:, its concept is easier to grasp and program but it's without the optimizations of Buckles. Fortunately, it also does not produce duplicate combinations:

The set x_k...x_1 in N that maximizes i = C(x_1,k) + C(x_2,k-1) + ... + C(x_k,1), where C(n,r) = {n choose r}.

For an example: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1). So, the 27th lexicographical combination of four things is: {1,2,5,6}, those are the indexes of whatever set you want to look at. Example below (OCaml), requires choose function, left to reader:

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

A small and simple combinations iterator

The following two algorithms are provided for didactic purposes. They implement an iterator and (a more general) folder overall combinations. They are as fast as possible, having the complexity O(nCk). The memory consumption is bound by k.

We will start with the iterator, which will call a user provided function for each combination

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

A more general version will call the user provided function along with the state variable, starting from the initial state. Since we need to pass the state between different states we won't use the for-loop, but instead, use recursion,

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
8
  • 2
    Yes it will Thomas. It is agnostic to the data in the array. You can always filter out duplicates first, if that's the desired effect, or choosing another algorithm.
    – nlucaroni
    Jul 2, 2010 at 14:10
  • 22
    Awesome answer. Can you please provide summary of the run time and memory analysis for each of the algorithms? May 10, 2012 at 21:18
  • 2
    Fairly good answer. 20C3 is 1140, the exclamation mark is confusing here as it looks like a factorial, and factorials do enter the formula for finding combinations. I will therefore edit out the exclamation mark.
    – CashCow
    Oct 28, 2013 at 10:08
  • 2
    doc_180: Chase's algorithm is more complicated than the other algorithms but has the added benefit that each successive combination differs from the previous by just one element. This can be useful if the work that needs to be performed on each combination can be made faster if using the partial work of the previous combination.
    – Eyal
    Dec 10, 2013 at 8:12
  • 7
    It sucks that many of the citations are behind a paywall. Is there a possibility to include either non-paywall links or include quotable snippets from sources?
    – Terrance
    May 24, 2018 at 18:19
206

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

Usage:

var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);

Result:

123
124
125
134
135
145
234
235
245
345
8
  • 3
    This solution works well for "small" sets but for bigger sets it uses a bit of memory. Aug 25, 2011 at 21:42
  • 1
    not directly related but, the code is very interesting/readable and I wonder which version of c# has this constructs/methods ? (I have only used c# v1.0 and not that much).
    – LBarret
    Jun 4, 2012 at 7:00
  • 1
    Definitely elegant, but the IEnumerable will be enumerated a lot of times. If this is backed by some significant operation... Dec 26, 2012 at 15:06
  • 3
    since it's an extension method your usage line can read: var result = new[] { 1, 2, 3, 4, 5 }.Combinations(3); Oct 25, 2013 at 7:54
  • 1
    Can you provide exact non linq version of this query using recursive loops
    – irfandar
    May 5, 2014 at 12:38
96

Short java solution:

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

Result will be

[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]
7
  • this seem to be O(n^3) right? I wonder is there a faster algorithm to doing this.
    – LZH
    Oct 29, 2014 at 0:27
  • I am working with 20 choose 10 and this seems to be fast enough for me (less than 1 second)
    – demongolem
    Aug 28, 2015 at 17:45
  • 5
    @NanoHead you are wrong. This is combination without repetition. And your case is with repetition.
    – Jakub S.
    Mar 21, 2017 at 8:22
  • 1
    This piece of code should be easier to find on the web... this is exactly what I was looking for!
    – Manuel S.
    Jun 14, 2017 at 8:47
  • I just tested this and 7 other java implementations - this one was by far the fastest. The 2nd fastest was over an order of magnitude slower.
    – stuart
    Jan 17, 2018 at 19:31
85

May I present my recursive Python solution to this problem?

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:], length-1):
                yield (elements[i],) + next
def choose(l, k):
    return list(choose_iter(l, k))

Example usage:

>>> len(list(choose_iter("abcdefgh",3)))
56

I like it for its simplicity.

3
  • 20
    len(tuple(itertools.combinations('abcdefgh',3))) will achieve the same thing in Python with less code.
    – hgus1294
    Jul 17, 2012 at 10:46
  • 72
    @hgus1294 True, but that would be cheating. Op requested an algorithm, not a "magic" method that is tied to a particular programming language.
    – MestreLion
    Oct 10, 2012 at 14:20
  • 1
    Shouldn't strictly speaking the first loop range be for i in xrange(len(elements) - length + 1):? Doesn't matter in python as going out of slice index is handled gracefully but it's the correct algorithm. May 6, 2017 at 9:31
70

Lets say your array of letters looks like this: "ABCDEFGH". You have three indices (i, j, k) indicating which letters you are going to use for the current word, You start with:

A B C D E F G H
^ ^ ^
i j k

First you vary k, so the next step looks like that:

A B C D E F G H
^ ^   ^
i j   k

If you reached the end you go on and vary j and then k again.

A B C D E F G H
^   ^ ^
i   j k

A B C D E F G H
^   ^   ^
i   j   k

Once you j reached G you start also to vary i.

A B C D E F G H
  ^ ^ ^
  i j k

A B C D E F G H
  ^ ^   ^
  i j   k
...

Written in code this look something like that

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]);
        }
    }
}
9
  • 136
    The problem with this approach is that it hard-wires the parameter 3 into the code. (What if 4 characters were desired?) As I understood the question, both the array of characters AND the number of characters to select would be provided. Of course, one way around that issue is to replace the explicitly-nested loops with recursion.
    – joel.neely
    Dec 14, 2009 at 3:49
  • 11
    @Dr.PersonPersonII And why are triangles of any relevance to the OP?
    – MestreLion
    Oct 10, 2012 at 14:13
  • 7
    You can always transform this solution to recursive one with arbitrary parameter.
    – Rok Kralj
    Jul 1, 2014 at 19:12
  • 5
    @RokKralj, how do we "transform this solution to recursive one with arbitrary parameter"? Seems impossible to me. Feb 4, 2015 at 15:32
  • 4
    An nice intuitive explanation of how to do it Aug 27, 2015 at 6:08
60

The following recursive algorithm picks all of the k-element combinations from an ordered set:

  • choose the first element i of your combination
  • combine i with each of the combinations of k-1 elements chosen recursively from the set of elements larger than i.

Iterate the above for each i in the set.

It is essential that you pick the rest of the elements as larger than i, to avoid repetition. This way [3,5] will be picked only once, as [3] combined with [5], instead of twice (the condition eliminates [5] + [3]). Without this condition you get variations instead of combinations.

2
  • 15
    Very good description in English of the algorithm used by many of the answers
    – MestreLion
    Oct 10, 2012 at 14:22
  • second the above; in particular, this helped me understand the solution posed by user935714. both are excellent. Jun 8, 2017 at 11:59
35

Short example in 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

For explanation, the recursive method is described with the following example:

Example: A B C D E
All combinations of 3 would be:

  • A with all combinations of 2 from the rest (B C D E)
  • B with all combinations of 2 from the rest (C D E)
  • C with all combinations of 2 from the rest (D E)
0
26

I found this thread useful and thought I would add a Javascript solution that you can pop into Firebug. Depending on your JS engine, it could take a little time if the starting string is large.

function string_recurse(active, rest) {
    if (rest.length == 0) {
        console.log(active);
    } else {
        string_recurse(active + rest.charAt(0), rest.substring(1, rest.length));
        string_recurse(active, rest.substring(1, rest.length));
    }
}
string_recurse("", "abc");

The output should be as follows:

abc
ab
ac
a
bc
b
c
2
  • 6
    @NanoHead This is not wrong. The output already shows "ac" - and "ca" is the same combination as "ac". You are talking about permutations (in math) where "ac" would not be the same as "ca". Jul 4, 2017 at 13:32
  • 3
    This is not n choose k.
    – shinzou
    Mar 6, 2018 at 13:46
26

In C++ the following routine will produce all combinations of length distance(first,k) between the range [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;
}

It can be used like this:

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

This will print the following:

123
124
125
134
135
145
234
235
245
345
3
  • 1
    What is begin, what is end in this case? How can it actually return something if all variables passed to this function are passed by value? Jun 10, 2011 at 10:14
  • 6
    @Sergej Andrejev: replace being and begin with s.begin(), and end with s.end(). The code closely follows STL's next_permutation algorithm, described here in more details. Jul 5, 2011 at 11:49
  • 6
    what is happening? i1 = last; --i1; i1 = k;
    – Manoj R
    Mar 21, 2012 at 15:14
21
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;
    }
}
4
  • Nice solution. I referenced it in answering this recent question: stackoverflow.com/questions/4472036/…
    – wageoghe
    Dec 17, 2010 at 19:08
  • The only problem with this function is recursiveness. While it's usually fine for software running on PC, if you're working with a more resource constrained platform (embedded for example), you're out of luck Aug 12, 2011 at 0:07
  • It will also allocate a lot of Lists and do a lot of work to duplicate the items of the array into each new one. It looks to me like these lists won't be collectible until the entire enumeration is complete. Feb 22, 2015 at 5:11
  • That is slick. Did you find an algorithm or is that from scratch?
    – paparazzo
    Aug 8, 2017 at 22:28
20

Simple recursive algorithm in Haskell

import Data.List

combinations 0 lst = [[]]
combinations n lst = do
    (x:xs) <- tails lst
    rest   <- combinations (n-1) xs
    return $ x : rest

We first define the special case, i.e. selecting zero elements. It produces a single result, which is an empty list (i.e. a list that contains an empty list).

For n > 0, x goes through every element of the list and xs is every element after x.

rest picks n - 1 elements from xs using a recursive call to combinations. The final result of the function is a list where each element is x : rest (i.e. a list which has x as head and rest as tail) for every different value of x and rest.

> combinations 3 "abcde"
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]

And of course, since Haskell is lazy, the list is gradually generated as needed, so you can partially evaluate exponentially large combinations.

> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"
> take 10 c
["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn",
 "abcdefgo","abcdefgp","abcdefgq"]
14

And here comes granddaddy COBOL, the much maligned language.

Let's assume an array of 34 elements of 8 bytes each (purely arbitrary selection.) The idea is to enumerate all possible 4-element combinations and load them into an array.

We use 4 indices, one each for each position in the group of 4

The array is processed like this:

    idx1 = 1
    idx2 = 2
    idx3 = 3
    idx4 = 4

We vary idx4 from 4 to the end. For each idx4 we get a unique combination of groups of four. When idx4 comes to the end of the array, we increment idx3 by 1 and set idx4 to idx3+1. Then we run idx4 to the end again. We proceed in this manner, augmenting idx3,idx2, and idx1 respectively until the position of idx1 is less than 4 from the end of the array. That finishes the algorithm.

1          --- pos.1
2          --- pos 2
3          --- pos 3
4          --- pos 4
5
6
7
etc.

First iterations:

1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
etc.

A COBOL example:

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.
1
  • but why {}{}{}{}
    – shinzou
    Mar 6, 2018 at 13:48
10

Another C# version with lazy generation of the combination indices. This version maintains a single array of indices to define a mapping between the list of all values and the values for the current combination, i.e. constantly uses O(k) additional space during the entire runtime. The code generates individual combinations, including the first one, in O(k) time.

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

Test code:

foreach (var combination in new[] {'a', 'b', 'c', 'd', 'e'}.Combinations(3))
{
    System.Console.WriteLine(String.Join(" ", combination));
}

Output:

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
2
  • This preserves the ordering. I'm expecting the result set to also contain c b a which it does not. Nov 16, 2016 at 16:43
  • 2
    The task is to generate all combinations that satisfy n over k. Binomial coefficients answer the question about how many ways there are choosing an unordered subset of k elements from a fixed set of n elements. Therefore the proposed algorithm does what it should.
    – Christoph
    Nov 15, 2019 at 11:11
9

Here is an elegant, generic implementation in Scala, as described on 99 Scala Problems.

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 :: _}
    }
}
9

If you can use SQL syntax - say, if you're using LINQ to access fields of an structure or array, or directly accessing a database that has a table called "Alphabet" with just one char field "Letter", you can adapt following code:

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

This will return all combinations of 3 letters, notwithstanding how many letters you have in table "Alphabet" (it can be 3, 8, 10, 27, etc.).

If what you want is all permutations, rather than combinations (i.e. you want "ACB" and "ABC" to count as different, rather than appear just once) just delete the last line (the AND one) and it's done.

Post-Edit: After re-reading the question, I realise what's needed is the general algorithm, not just a specific one for the case of selecting 3 items. Adam Hughes' answer is the complete one, unfortunately I cannot vote it up (yet). This answer's simple but works only for when you want exactly 3 items.

0
8

I had a permutation algorithm I used for project euler, in 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

If

n<len(l) 

you should have all combination you need without repetition, do you need it?

It is a generator, so you use it in something like this:

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

https://gist.github.com/3118596

There is an implementation for JavaScript. It has functions to get k-combinations and all combinations of an array of any objects. Examples:

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

Lets say your array of letters looks like this: "ABCDEFGH". You have three indices (i, j, k) indicating which letters you are going to use for the current word, You start with:

A B C D E F G H
^ ^ ^
i j k

First you vary k, so the next step looks like that:

A B C D E F G H
^ ^   ^
i j   k

If you reached the end you go on and vary j and then k again.

A B C D E F G H
^   ^ ^
i   j k

A B C D E F G H
^   ^   ^
i   j   k

Once you j reached G you start also to vary 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);

Based on https://stackoverflow.com/a/127898/2628125, but more abstract, for any size of pointers.

4
6

Here you have a lazy evaluated version of that algorithm coded in 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));
        }
    }

And test part:

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

Hope this help you!


Another version, that forces all the first k to appear firstly, then all the first k+1 combinations, then all the first k+2 etc.. It means that if you have sorted array, the most important on the top, it would take them and expand gradually to the next ones - only when it is must do so.

private static bool NextCombinationFirstsAlwaysFirst(int[] num, int n, int k)
{
    if (k > 1 && NextCombinationFirstsAlwaysFirst(num, num[k - 1], k - 1))
        return true;

    if (num[k - 1] + 1 == n)
        return false;

    ++num[k - 1];
    for (int i = 0; i < k - 1; ++i)
        num[i] = i;

    return true;
}

For instance, if you run the first method ("nextCombination") on k=3, n=5 you'll get:

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

But if you'll run

int[] nums = new int[k];
for (int i = 0; i < k; ++i)
    nums[i] = i;
do
{
    Console.WriteLine(string.Join(" ", nums));
}
while (NextCombinationFirstsAlwaysFirst(nums, n, k));

You'll get this (I added empty lines for clarity):

0 1 2

0 1 3
0 2 3
1 2 3

0 1 4
0 2 4
1 2 4
0 3 4
1 3 4
2 3 4

It's adding "4" only when must to, and also after "4" was added it adds "3" again only when it must to (after doing 01, 02, 12).

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

Clojure version:

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

Algorithm:

  • Count from 1 to 2^n.
  • Convert each digit to its binary representation.
  • Translate each 'on' bit to elements of your set, based on position.

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

Why does it work?

There is a bijection between the subsets of an n-element set and n-bit sequences.

That means we can figure out how many subsets there are by counting sequences.

e.g., the four element set below can be represented by {0,1} X {0, 1} X {0, 1} X {0, 1} (or 2^4) different sequences.

So - all we have to do is count from 1 to 2^n to find all the combinations. (We ignore the empty set.) Next, translate the digits to their binary representation. Then substitute elements of your set for 'on' bits.

If you want only k element results, only print when k bits are 'on'.

(If you want all subsets instead of k length subsets, remove the cnt/kElement part.)

(For proof, see MIT free courseware Mathematics for Computer Science, Lehman et al, section 11.2.2. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/ )

3
  • 1
    This solution was great for me. It has minimal iteration and is therefore very fast. Oct 26, 2022 at 15:47
  • Counting bits by converting an int to a base 2 string representation and then using regexes to count the number of 1s is frankly pretty disgusting. It will be far from "fast". The amount of allocation alone is crazy. var cnt = System.Runtime.Intrinsics.X86.Popcnt.PopCount(i); Apr 6 at 17:37
  • Great! You're right to introduce pop count. I wasn't aware of it then. The idea remains valid however; improving the constant time calculations within the loop is good. I'll leave this, though, because it makes the point clearly. Thanks! Apr 10 at 10:02
5

short python code, yielding index positions

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
1
  • This is very elegant/efficient and works well. I've just translated it to C++. Jun 11, 2020 at 17:03
4

All said and and done here comes the O'caml code for that. Algorithm is evident from the code..

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 []
;;
1
  • Evident for a camel, maybe. Terry Pratchett claimed they were the greatest mathematicians of the known universe.
    – kuroi neko
    Aug 1, 2021 at 15:30
4

Here is a method which gives you all combinations of specified size from a random length string. Similar to quinmars' solution, but works for varied input and k.

The code can be changed to wrap around, ie 'dab' from input '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);
    }
}

Output for "abcde":

abc abd abe acd ace ade bcd bce bde cde

4

Short javascript version (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.log(e.join()));

1
  • 1
    Would you please explain this a little bit or change it to a function? It's really hard for me to follow or understand what's happening Nov 8, 2022 at 4:24
4

Another python recusive solution.

def combination_indicies(n, k, j = 0, stack = []):   
    if len(stack) == k:            
        yield list(stack)
        return
        
    for i in range(j, n):
        stack.append(i)
        for x in combination_indicies(n, k, i + 1, stack):            
            yield x
        stack.pop()  
        
list(combination_indicies(5, 3))

Output:

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

I created a solution in SQL Server 2005 for this, and posted it on my website: http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm

Here is an example to show usage:

SELECT * FROM dbo.fn_GetMChooseNCombos('ABCD', 2, '')

results:

Word
----
AB
AC
AD
BC
BD
CD

(6 row(s) affected)
1
  • I'm interested but the link is dead. Nov 8, 2022 at 13:26
3

Here is my proposition in C++

I tried to impose as little restriction on the iterator type as i could so this solution assumes just forward iterator, and it can be a const_iterator. This should work with any standard container. In cases where arguments don't make sense it throws 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));
    }
}
3

Here is a code I recently wrote in Java, which calculates and returns all the combination of "num" elements from "outOf" elements.

// author: Sourabh Bhat (heySourabh@gmail.com)

public class Testing
{
    public static void main(String[] args)
    {

// Test case num = 5, outOf = 8.

        int num = 5;
        int outOf = 8;
        int[][] combinations = getCombinations(num, outOf);
        for (int i = 0; i < combinations.length; i++)
        {
            for (int j = 0; j < combinations[i].length; j++)
            {
                System.out.print(combinations[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static int[][] getCombinations(int num, int outOf)
    {
        int possibilities = get_nCr(outOf, num);
        int[][] combinations = new int[possibilities][num];
        int arrayPointer = 0;

        int[] counter = new int[num];

        for (int i = 0; i < num; i++)
        {
            counter[i] = i;
        }
        breakLoop: while (true)
        {
            // Initializing part
            for (int i = 1; i < num; i++)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i] = counter[i - 1] + 1;
            }

            // Testing part
            for (int i = 0; i < num; i++)
            {
                if (counter[i] < outOf)
                {
                    continue;
                } else
                {
                    break breakLoop;
                }
            }

            // Innermost part
            combinations[arrayPointer] = counter.clone();
            arrayPointer++;

            // Incrementing part
            counter[num - 1]++;
            for (int i = num - 1; i >= 1; i--)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i - 1]++;
            }
        }

        return combinations;
    }

    private static int get_nCr(int n, int r)
    {
        if(r > n)
        {
            throw new ArithmeticException("r is greater then n");
        }
        long numerator = 1;
        long denominator = 1;
        for (int i = n; i >= r + 1; i--)
        {
            numerator *= i;
        }
        for (int i = 2; i <= n - r; i++)
        {
            denominator *= i;
        }

        return (int) (numerator / denominator);
    }
}

Not the answer you're looking for? Browse other questions tagged or ask your own question.