Google Answers Logo
View Question
Q: Algorithm to Calculate a list of Unique Combinations ( Answered 5 out of 5 stars,   3 Comments )
Subject: Algorithm to Calculate a list of Unique Combinations
Category: Computers > Algorithms
Asked by: gotquestion-ga
List Price: $20.00
Posted: 26 Aug 2004 08:52 PDT
Expires: 25 Sep 2004 08:52 PDT
Question ID: 392914
I would like an algorithm to calculate the number of unique
combinations and then to list the unique combinations. This is for a
Computer Program.

I have 3 letters: A,B,C and want to know how many unique Sets of 2
letters I can create and what these sets are.

Any help would be appreciated.

Request for Question Clarification by mathtalk-ga on 28 Aug 2004 19:01 PDT
Hi, gotquestion-ga:

I'm not sure if you were satisfied with the responses you got below in
the form of Comments.

Calculating the _number_ of unique of combinations of N (distinct)
things taken K at a time can be computed in a loop over K, which would
require only integer multiplcations and divisions to evaluate the
standard formula (shown by sachit-ga).

Programs that can list all these combinations have been discussed in
several Google Answers threads.  For example:

[Q: All possible Combinations]

The Customer asked about ways of programming all combinations of N
things taken K at a time, and I outlined three general approaches to
coding it.

[Q: converting MATLAB routine to an executable file]

Another Customer (who had posted some related Questions on generating
all possible combinations) asks hereabout getting a Matlab function
definition converted to a format he could execute.

If the Comments below or those previous Answers are sufficient to your
needs, you may want to Close (Expire) this Question to avoid incurring
a charge for an Answer.  On the other hand if you would like further
information about programming either the count or the enumeration of
the combinations, please post a Clarification about what further
assistance is desired.

regards, mathtalk-ga
Subject: Re: Algorithm to Calculate a list of Unique Combinations
Answered By: leapinglizard-ga on 01 Sep 2004 09:13 PDT
Rated:5 out of 5 stars
Dear gotquestion,

I'll begin with the problem of enumerating all combinations of M
elements drawn from a set of size N. Let us number the elements n_0,
n_1, ..., n_N. Observe that if M = 1, we can run through the elements
one by one, and each will constitute a combination on its own.

If M > 1, then let's first enumerate all combinations that include the
element n_0. To do so, we remove n_0 from the set, and now we
enumerate all combinations of M-1 elements drawn from the remaining
N-1 elements. To make a full combination of length M, we concatenate
n_0 with the combination of length M-1.

The subproblem of enumerating all combinations of M-1 elements from a
set of size of N-1 is solved similarly to the original problem. We
remove an element and then enumerate all combinations of M-2 elements
from the remaining N-2. Eventually, we will end up with the subproblem
of enumerating combinations of 1 element.

Once we've run through all combinations for the original problem that
include the element n_0, we can proceed to enumerate all remaining
combinations that include n_1. To do so, we take out n_1 in addition
to the already removed n_0, so that N-2 elements remain in the set. We
are now considering combinations that begin with the element n_1, so
we enumerate all combinations of M-1 elements from the remaining set
of size N-2. When that is done, we take out n_2 and enumerate all
combinations of M-1 elements from a set of size N-3, and so on. Once
we've reached the element n_M, we are done.

I'll summarize this algorithm with the following pseudocode. The input
parameter P is the currently known prefix of the combination. K is the
number of elements that remain to be drawn from the set S. If we
originally call ENUMERATE with empty P and with a value K = M, then it
is necessarily the case that when K reaches 0, P contains M elements
and is therefore a full combination.

  ENUMERATE (input: a list P; an integer K; a set S):
    if K is equal to 0:
      print P
      for each element s_i of S:
        let P' be P with s_i added to the end
        remove s_i from S
        ENUMERATE(P', K-1, S)    

An implementation in C follows. You'll notice that my function doesn't
take as a parameter the set itself, because in this program, S is a
global variable containing all elements. Instead, I pass the least
index number such that all lower-numbered elements of S have already
been considered. The effect of using this bound is to simulate the
removal of elements from S.

/* begin combs.c */

char *S = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
int N, count;
char P[100];

void enumerate(char *P, int K, int n_i) {
    int i;
    if (K == 0)
        printf("%d. %s\n", ++count, P);
        for (i = n_i; i < N; i++) {
            P[strlen(P)+1] = '\0';
            P[strlen(P)] = S[i];
            enumerate(P, K-1, i+1);
            P[strlen(P)-1] = '\0';

int main(int argc, char **argv) {
    int M, max = strlen(S);
    if (argc != 3) {
        printf("usage: combs <int M> <int N>\n");
        return 0;
    M = atoi(argv[1]);
    if (M < 1 || M > max) {
        printf("error: M must lie between 1 and %d, inclusive\n", max);
        return 0;
    N = atoi(argv[2]);
    if (N < M || N > max) {
        printf("error: N must lie between %d and %d, inclusive\n", M, max);
        return 0;
    enumerate(P, M, 0);
    return 0;

/* end combs.c */

I'm not sure what platform you're using, but I'm on a UNIX-type
system. To compile the program, I execute

  gcc combs.c -o combs

and then to run it, I pass a pair of integer arguments, as in the
following examples.

  ./combs 2 3
  ./combs 3 5
  ./combs 5 10

There's some error checking built into the main function, so it should
be fairly robust. Let me know if you have trouble compiling or running
my program, and I'll try to provide further assistance.

Observe that in the act of enumerating all combinations, we have also
counted them. It is possible, however, to compute the number of
combinations without enumeration. In fact, this is often preferred
because the combinations can easily get so numerous that printing them
all would take an impractical amount of time.

Consider how we choose the elements that make up any single
combination. The number of choices for the first element of the
combination is N, the size of the available set. When that element is
removed, we have N-1 choices for the second element of the
combination. Next, we have N-2 choices for the third element, and so
on, until we have built up the entire combination. Notice that in
making these M choices, we may have selected exactly the same elements
as in another combination, but in a different order. Thus, the number
of ways to choose M elements among N is not simply

  N * (N-1) * (N-2) * ... * (N-(M-1)).

This is the number of ways to order M elements among N. To find the
number of combinations, we must divide by the number of ways to order
M elements alone. The number of ways to do so is, by similar reasoning
to the above,

  M * (M-1) * (M-2) * ... * 1.

In conclusion, the number of combinations of M elements chosen among a
set of size N is

  N * (N-1) * (N-2) * ... * (N-(M-1)) / (M * (M-1) * (M-2) * ... * 1).

Here is some pseudocode to compute this number.

  COMBINATIONS (input: integer M; integer N):
    let T be 1
    for each integer i between N and N-(M-1), inclusive:
      let T be i*T
    for each integer i between M and 1, inclusive:
      let T be T/i
    return T

A C function follows.

int combinations(int M, int N) {
    long T = 1;
    int i;
    for (i = N; i >= N-(M-1); i--)
        T *= (long) i;
    for (i = M; i >= 1; i--)
        T /= (long) i;
    return (int) T;

To try out this code, you can insert it before the main function I
gave earlier, then replace the line

  enumerate(P, M, 0);


  printf("There are %d combinations.\n", combinations(M, N));

and compile the whole program before executing it. See how much faster
it runs without enumeration?

The algorithms I have given above apply only to the problem of drawing
elements from a set, where each member is unique. It is a more
complicated business to enumerate combinations made from a bag, also
known as a multiset, which may contain duplicates. Because you didn't
use the word bag or multiset in your question, I assumed that you were
dealing just with sets.

If you should find my answer incomplete or inaccurate in any way,
please post a clarification so that I have a chance to meet your needs
before you assign a rating.


gotquestion-ga rated this answer:5 out of 5 stars and gave an additional tip of: $10.00
Outstanding. A very complete answer.

Subject: Re: Algorithm to Calculate a list of Unique Combinations
From: sachit-ga on 26 Aug 2004 11:09 PDT
I know this is not the complete answer, but I just like helping to get
things going.

First off, the equation to find HOW MANY combinations there are is:

C(n,r) = n! / ((n-r)! r!)

Where "n" is number of total items.
Where "r" is number of items wanted in the set.

The only way I can think of doing this is using arrays. First you
would create an array size that includes all the possible items wanted
in the set. Another empty array of the same size would be created and
be used as a "checker".

Everytime an item is used, that identicle element in the second array
would be filled. Then, when the program notices that element is
"filled", it knows it cannot use that character.

I know this answer may not be the best or perfectly correct, but I
hope it helps you in figuring out your answer.

Subject: Re: Algorithm to Calculate a list of Unique Combinations
From: saem_aero-ga on 26 Aug 2004 11:32 PDT
Here is the code you want, i wrote it up in matlab format for fun. 
but anyone can figure out how it works. :)  Note that disp() is the
output command. by changing the variable combines you can set how many
varibles you want the unique combinations of ... for example if you
wanted abcde, then choose 5.

%comment - clear variables and screen. 

%create a character array... in this case... lets make it the alphabet.
chrarray = 'abcdefghijklmnopqrstuvwxyz';

%how many letters of the alphabet to find combinations for?
combines = 3;

%create the cute little combinations and print them out as they are
counter = 1;
for j = 1:combines
 for i = counter+1:combines
    output(1) = chrarray(counter);
    output(2) = chrarray(i);
 counter = counter + 1;
Output of the first seven alphabet chr, eg a,b,c,d,e,f,g:

Subject: Re: Algorithm to Calculate a list of Unique Combinations
From: gotquestion-ga on 01 Sep 2004 13:53 PDT
Thanks very much for the comments and the answers. I really
apporeciate the effort extended.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy