Take the 2-minute tour ×

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.

share|improve this question

47 Answers 47

up vote 196 down vote accepted

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. There are many of these, and for different uses, based on the distance of elements. Do we want to maximize the differences between successive applications? 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 it's index (in lexicographical order), realizing that the index should be some amount of change from right to left based on the index.

So, we have a set {1,2,3,4,5,6}... when we want three elements {1,2,3} we can say that the difference between the elements is one and in order. {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.

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 other minor changes --I used the index of the sets rather then 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:, it's concept is easier to grasp and program but it's without the optimizations of Buckles. Fortunately, it does not produce duplicate combinations:

The set, $x_k...x_1 \in \mathbb{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
    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)
    if x < 0 then failwith "errors" else
    let idxs =  iterate (List.length set) x k in
    List.map (List.nth set) (List.sort (-) idxs)
share|improve this answer
Awesome answer. Can you please provide summary of the run time and memory analysis for each of the algorithms? –  doc_180 May 10 '12 at 21:18
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 '13 at 10:08
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 '13 at 8:12

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


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


share|improve this answer
This is a really neat piece of code... excellent! –  Aaron Murgatroyd Sep 26 '12 at 12:28
+1 for elegant linq code –  Chasefornone Dec 8 '12 at 7:55

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

Example usage:

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

I like it for its simplicity.

share|improve this answer
len(tuple(itertools.combinations('abcdefgh',3))) will achieve the same thing in Python with less code. –  hgus1294 Jul 17 '12 at 10:46
@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 '12 at 14:20

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:

^ ^ ^
i j k

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

^ ^   ^
i j   k

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

^   ^ ^
i   j k

^   ^   ^
i   j   k

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

  ^ ^ ^
  i j k

  ^ ^   ^
  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]);
share|improve this answer
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 '09 at 3:49
@Dr.PersonPersonII And why are triangles of any relevance to the OP? –  MestreLion Oct 10 '12 at 14:13

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.

share|improve this answer
Very good description in English of the algorithm used by many of the answers –  MestreLion Oct 10 '12 at 14:22

In C++ the following routine will produce all combinations of length distance(first,k) between the range [first,last):

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;
   if (last == i1)
      return false;
   i1 = last;
   i1 = k;
   while (first != i1)
      if (*--i1 < *i2)
         Iterator j = k;
         while (!(*i1 < *j)) ++j;
         i2 = k;
         while (last != j)
         return true;
   return false;

It can be used like this:

std::string s = "12345";
std::size_t comb_size = 3;
   std::cout << std::string(being,begin + comb_size) << std::endl;
while(next_combination(begin,begin + comb_size,end));
share|improve this answer
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? –  Sergej Andrejev Jun 10 '11 at 10:14
@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. –  Anthony Labarre Jul 5 '11 at 11:49
what is happening? i1 = last; --i1; i1 = k; –  Manoj R Mar 21 '12 at 15:14
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
            foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
                yield return characters[i] + next;
share|improve this answer

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){
        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]
share|improve this answer

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) {
    } 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:








share|improve this answer
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

First iterations:


A COBOL example:

    05  FILLER     PIC X(8)    VALUE  "VALUE_01".
    05  FILLER     PIC X(8)    VALUE  "VALUE_02".
    05  ARAY_ITEM       PIC X(8).

01  OUTPUT_ARAY   OCCURS  50000   PIC X(32).

01   MAX_NUM   PIC 99 COMP VALUE 34.

    05  IDX1            PIC 99.
    05  IDX2            PIC 99.
    05  IDX3            PIC 99.
    05  IDX4            PIC 99.
    05  OUT_IDX   PIC 9(9).


* Stop the search when IDX1 is on the third last array element:



   COMPUTE IDX2 = IDX1 + 1
      COMPUTE IDX3 = IDX2 + 1
         COMPUTE IDX4 = IDX3 + 1
            ADD 1 TO OUT_IDX
            STRING  ARAY_ITEM(IDX1)
                    INTO OUTPUT_ARAY(OUT_IDX)
            ADD 1 TO IDX4
         ADD 1 TO IDX3
      ADD 1 TO IDX2
   ADD 1 TO IDX1
share|improve this answer

Short example in Python:

def comb(sofar, rest, n):
    if n == 0:
        print sofar
        for i in range(len(rest)):
            comb(sofar + rest[i], rest[i+1:], n-1)

>>> comb("", "abcde", 3)

For explanation, the recusive 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)

share|improve this answer

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"

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
share|improve this answer

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



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
share|improve this answer

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 :: _}
share|improve this answer

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.

share|improve this answer


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

-> [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
share|improve this answer
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))


        if (out.length >= num) {


    return combinations;
share|improve this answer

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)
                    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];
                numbers[i] = i;

                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!

share|improve this answer


This link contains an explanation of and source code to a CombinationGenerator.

share|improve this answer
You shouldn't post just a link. You should atleast post a small explanation of the link with it. –  The.Anti.9 Sep 24 '08 at 15:52
You should really post a summary / paraphrase the solution from the link - if the link goes offline, your answer becomes useless. –  defines Jun 25 '09 at 16:50

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.
        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];
        // Below is the ugly side of using the sentinel. Well it had to haave some 
        // disadvantage. Try without it.
                                          current_combination.end() - 1));
share|improve this answer

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



(6 row(s) affected)
share|improve this answer

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] + " ");

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

            counter[i] = i;
        breakLoop: while (true)
            // Initializing part
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i] = counter[i - 1] + 1;

            // Testing part
                if (counter[i] < outOf)
                } else
                    break breakLoop;

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

            // Incrementing part
            counter[num - 1]++;
            for (int i = num - 1; i >= 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);
share|improve this answer

Here's some simple code that prints all the C(n,m) combinations. It works by initializing and moving a set of array indices that point to next valid combination. The indices are initialized to point to the lowest m indices (lexicographically the smallest combination). Then on, starting with the m-th index, we try to move the indices forward. if an index has reached its limit, we try the previous index (all the way down to index 1). If we can move an index forward, then we reset all greater indices.

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

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

    // 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.
    while ((j>=0) && !move_found)
        if (p[j]<(n-i)) 
            p[j]++; // point p[j] to next index
            for (k=j+1;k<m;k++)
    if (!move_found) done=true;
share|improve this answer

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

    for (int i=startIndex; i<data.length(); i++){
        choose(data,k,result, i+1);

Output for "abcde":

abc abd abe acd ace ade bcd bce bde cde

share|improve this answer
//This is a recursive program that generates combinations for nCk.Elements in collection are assumed to be from 1 to n


int nCk(int n,int loopno,int ini,int *a,int k)
    static int count=0;
    int i;
        return 0;
    return count;
    return 0;

void main()
    int n,k,*a,count;
    printf("Enter the value of n and k\n");
    scanf("%d %d",&n,&k);
    printf("No of combinations=%d\n",count);
share|improve this answer

Since programming language is not mentioned I am assuming that lists are OK too. So here's an OCaml version suitable for short lists (non tail-recursive). Given a list l of elements of any type and an integer n it will return a list of all possible lists containing n elements of l if we assume that the order of the elements in the outcome lists is ignored, i.e. list ['a';'b'] is the same as ['b';'a'] and will reported once. So size of resultant list will be ((List.length l) Choose n).

The intuition of the recursion is the following: you take the head of the list and then make two recursive calls:

  • recursive call 1 (RC1): to the tail of the list, but choose n-1 elements
  • recursive call 2 (RC2): to the tail of the list, but choose n elements

to combine the recursive results, list-multiply (please bear the odd name) the head of the list with the results of RC1 and then append (@) the results of RC2. List-multiply is the following operation lmul:

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

lmul is implemented in the code below as List.map (fun x -> h::x)

Recursion is terminated when the size of the list equals the number of elements you want to choose, in which case you just return the list itself.

So here's a four-liner in OCaml that implements the above algorithm:

    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)   
    | [], _ -> []    
share|improve this answer
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;
    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;

In the first function, m denotes how many more you need to choose, and start denotes from which position in array you must start choosing.

share|improve this answer










share|improve this answer

And here's a Clojure version that uses the same algorithm I describe in my OCaml implementation answer:

(defn select
     (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)
            (select n (rest items))
            (lmul (first items) (select (dec n) (rest items))))))))) 

It provides three ways to call it:

(a) for exactly n selected items as the question demands:

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

(b) for between n1 and n2 selected items:

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) for between 0 and the size of the collection selected items:

user=> (select '(1 2 3))
(() (3) (2) (1) (2 3) (1 3) (1 2) (1 2 3))
share|improve this answer
 #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 */
            if (i < k - 1) {
/* Turn the elements after it into a linear sequence */
                unsigned int j;
                    ar[j] = ar[j - 1] + 1;
            changed = 1;
        finished = i == 0;
    if (!changed) {
        /* Reset to first combination */
            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);
  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);
 } while (next_combination(numbers, n, k));
 return 0;
share|improve this answer

Your Answer


