View Question
 Question
 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.```
 ```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 http://www.mathagonyaunt.co.uk/TES_ARTICLES/Past_articles/2002/OCT_02/OCT_18_02/Oct_18_02.html 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 NEXT I2 NEXT I1 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 http://www.merriampark.com/comb.htm for source code in Java or http://www.codeproject.com/useritems/combinations.asp 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. --Maniac``` 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. Add 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. --Maniac```
 ```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.```
 ```if you just want to find the Nth combination (rather than the full list) then you could use the 'comb_unrank.m' found at http://www.csit.fsu.edu/~burkardt/m_src/subset/subset.html```