Google Answers Logo
View Question
Q: Generating Combinations ( Answered,   2 Comments )
Subject: Generating Combinations
Category: Computers > Algorithms
Asked by: defusion-ga
List Price: $10.00
Posted: 04 Nov 2006 10:10 PST
Expires: 04 Dec 2006 10:10 PST
Question ID: 780070
How can I generate all combinations with x length for y numbers. E.g.
Say I want to generate all possible combinations of the numbers 1
through 10 with a maximum length of 4 numbers per combination.
Subject: Re: Generating Combinations
Answered By: maniac-ga on 05 Nov 2006 08:53 PST
Hello Defusion,

By "combination", I assume (unlike the comment from myoarin) that you
are choosing "x" items from a list of "y" numbers (and not a
k-permutation). I am pulling this definition from "Introduction to
Algorithms" by Cormen, Leiserson, and Rivest. There is also an
interesting discussion of the difference by the "Mathagony Aunt" at
or search with a phrase like
  permutation combination difference
for more references.

For a simple example of the difference, with the digits 0-3, a
2-combination includes the values:
  01, 02, 03, 12, 13, 23
where the 2-permutation includes the values:
  01, 02, 03, 10, 12, 13, 20, 21, 23, 30, 31, 32

Myoarin, however does make an interesting point if the range of values
is truly one through ten (and not zero through nine) and ten counts as
an item of length "2". Please make a clarification request if that is
important for your problem. The solutions below assume each value
selected is considered a single value when determining length.

Now, with that explanation, let's go through a few methods to generate
a combination and pointers to some source code to implement this.

If you need to print the combinations, a set of nested loops
structured like the following will work if "x" is fixed. (the example
below is for x=4).

FOR I1 = 0 to Y-3
  FOR I2 = I1+1 to Y-2
    FOR I3 = I2+1 to Y-1
      FOR I4 = I3+1 to Y
        PRINT I1, I2, I3, I4
      NEXT I4
    NEXT I3

You should notice that each inner loop starts at the value subsequent
to the current value of the outer loop. (the first value in this case
would be 0123, the last will be 6789 if y=9).

If you need a function that can be initialized and has a "get next" to
return the next combination (say in a loop doing actions for each
combination), see source code like
for source code in Java or
for source code in C#.

If some part of the answer is unclear or you need further information
on this topic, please make a clarification request.


Request for Answer Clarification by defusion-ga on 12 Nov 2006 12:43 PST
Let me try and clarify a little.

Say have have numbers 01 through to 15, and I want all the possible
combinations of 4 separate numbers, so assuming each number is 2
digits ( < 10 would have a leading zero) the result would be 8 digits.

Each number can only appear once in a given combination.

Does that help?

Clarification of Answer by maniac-ga on 13 Nov 2006 17:35 PST
Hello Defusion,

The nested loops I provided in the original answer would satisfy your
revised problem description with a slight change.

  Y = 15
to the beginning.

Change the first loop to read
  FOR I1 = 1 to Y-3

The print statement would need to be revised to print each number with
two digits. The method to do this varies by language. A BASIC with
"PRINT USING" could use something like
  PRINT USING "## ## ## ##", I1, I2, I3, I4
would display each number as two digits (with intervening spaces).

If the spaces are not desired, you could concatenate strings from an
array; something like:
  DIM A$(15)
  A$(1) = "01"
  A$(2) = "02"
  A$(15) = "15"
at the start

and then
  PRINT A$(I1)+A$(I2)+A$(I3)+A$(I4)
for the print statement.

If you need further explanation, please make another clarification request.

Subject: Re: Generating Combinations
From: myoarin-ga on 04 Nov 2006 15:28 PST
Count from 0000 to 9999 using leading zeros (e.g., 0001, 0100, etc.) for x = 4.

That would be 10,000 combinations, which happens to be 10^4 (10 to the
fourth power).  Same principle for x = 5, 6, ... n:  10^x

This is assuming that the different digits may be included more than
once in a combination.

If that is not allowed, please say so.

I have taken the liberty of restating your "numbers 1 through 10" to
"numbers 0 through 9", since this is usual in this sort of problem.

If you insist on using "10" within the combinations, that is, 10
taking two of the X numbers when it occurs, that could make the
exercise more "fun" for someone else.

This is a free comment, not an "answer" to your question.

If you have found this, you will have recognized that there is no
email notification system at present, so please check back by yourself
to see if an answer or other comments have been posted.
Subject: Re: Generating Combinations
From: xaviergisz-ga on 05 Nov 2006 18:56 PST
if you just want to find the Nth combination (rather than the full
list) then you could use the 'comb_unrank.m' found at

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