Thread: C program for generating combination

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    4

    C program for generating combination

    Respected members,

    I am new student of programming and currently learning C. I have an assignment of generating all possible combinations of n elements out of K numbers. After searching lot on google, I got following code using nested for loop. But its not working for me. Please help me.

    Code:
    int a = 0;
    int b = 0;
    int c = 0;
    int d = 0;
    int k[10]={1,2,3,4,5,6,7,8,9,10};
    int n = 4;
    int main()
    {
    	for (a = 0; a <= n - 3; ++a)
    	{
    		for (b = a+1; b <= n-2; b++)
    		{
    			for (c = b+1; c <= n-1; c++)
    			{
    				for (d = c+1; d <= n; d++)
    				{
    					printf("%d,%d,%d,%d", k[a],k[b],k[c],k[d];  
                        }
    			}
    		}
    	}
    }

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Are you trying to get all possible combinations, or all possible permutations?

    A combination is like a committee - you're either on it, or you're not on it - and everybody who is on it, is just the same. You might have 5 people on the committee, and every combination would include all those five people.

    With a permutation, you could have just 1 person, or all 5. Every person would have a unique set of values, different from the others. Think of a military board where each person could have any of 5 different ranks, and you need to account for all possibilities of rank, as well.

    When I see "combinations", that start with 0, as in your outer-most for loop, I start thinking "he wants permutations", since no combination would start with 0.

    If you allowed range of digits is 1 through 10, then make your digits inside each for loop, also range from 1 through 10. No zero's, and no <= are needed, I believe. Just <. Arrays are zero based in C.

    Try it with a range of 1 through 3, and see what you come up with. Forget what you can d/l from the net, OK? Learning isn't all about copying or modifying other people's code. We learn best when we learn by doing.

    This is a simple problem. Solve it by hand (pencil and paper), with a very small range. Then code it up with that very small range.

    Then code up your larger range, and if you get stuck, we're here.

  3. #3
    Registered User
    Join Date
    Feb 2009
    Posts
    35
    Quote Originally Posted by ymadhusoodan View Post
    Respected members,

    I am new student of programming and currently learning C. I have an assignment of generating all possible combinations of n elements out of K numbers. After searching lot on google, I got following code using nested for loop. But its not working for me. Please help me.

    Code:
    int a = 0;
    int b = 0;
    int c = 0;
    int d = 0;
    int k[10]={1,2,3,4,5,6,7,8,9,10};
    int n = 4;
    int main()
    {
    	for (a = 0; a <= n - 3; ++a)
    	{
    		for (b = a+1; b <= n-2; b++)
    		{
    			for (c = b+1; c <= n-1; c++)
    			{
    				for (d = c+1; d <= n; d++)
    				{
    					printf("%d,%d,%d,%d", k[a],k[b],k[c],k[d];  
                        }
    			}
    		}
    	}
    }
    the purpose of programming assignments is to give you a chance to learn the language through practice. your lecturer/tutor doesnt want a correct program for the sake of it. if they really wanted it they would write the program themselves.

    what they want is for you, the student, to go through the process of writing a program, making mistakes, learning and practicing how to program. they want a program that works, but ultimately its the process that is giving you the most benefit.

    you said you found this code on the net. i can already see two very big problems that will result in the code not compiling. it would take less than 30 seconds to fix the two problems and its quite concerning that you cannot see these problems since it involves understanding basic syntax as well as something you would have learnt when writing your helloworld program.

    so go back and study the notes, learn the content and try to write the program yourself. you cant google your way to a pass

  4. #4
    Registered User
    Join Date
    Nov 2009
    Posts
    4
    Respected ADAk and Brain_Child,

    I really worked on this problem and was stuck. I am sorry for using google, but I was searching for some hint with which I can go ahead.

    As you said I tried to make flowchart, initially on paper and then in a flowchart software. Logic seems correct to me, but code is not working. :-(

    I have attached my flowchart.

    Please help me in logic, and I will go ahead with that and try to write code.

    Thanks and regards

    Madhusoodan

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Take your flowchart and throw it out the window!

    Take the internet, and throw it out the window!

    Take a range between 1 and 3, and *WRITE OUT THE POSSIBLE COMBINATIONS* on a piece of paper (it's made from wood, usually white in color, and thin, holds graphite marks, rather well).

    We learn by studying and seeing others work, but we learn best, by *DOING* that something.

    Go get 'em, Tiger!

  6. #6
    Registered User
    Join Date
    Nov 2009
    Posts
    4
    All possible combinations of 3 in 10 numbers. Repetition not allowed. Sequence of course is not important. I could not do good alignment. Please read vertically.

    What is next step after this?

    1 2 3, 2 3 4, 3 4 5, 4 5 6, 5 6 7, 6 7 8, 7 8 9, 8 9 10.
    1 2 4, 2 3 5, 3 4 6, 4 5 7, 5 6 8, 6 7 9, 7 8 10,
    1 2 5, 2 3 6, 3 4 7, 4 5 8, 5 6 9, 6 7 10, 7 9 10,
    1 2 6, 2 3 7, 3 4 8, 4 5 9, 5 6 10, 6 8 9,
    1 2 7, 2 3 8, 3 4 9, 4 5 10, 5 7 8, 6 8 10,
    1 2 8, 2 3 9, 3 4 10, 4 6 7, 5 7 9, 6 9 10,
    1 2 9, 2 3 10, 3 5 6, 4 6 8, 5 7 10,
    1 2 10, 2 4 5, 3 5 7, 4 6 9, 5 8 9,
    1 3 4, 2 4 6, 3 5 8, 4 6 10, 5 8 10,
    1 3 5, 2 4 7, 3 5 9, 4 7 8, 5 9 10,
    1 3 6, 2 4 8, 3 5 10, 4 7 9,
    1 3 7, 2 4 9, 3 6 7, 4 7 10,
    1 3 8, 2 4 10, 3 6 8, 4 8 9,
    1 3 9, 2 5 6, 3 6 9, 4 8 10,
    1 3 10, 2 5 7, 3 6 10, 4 9 10,
    1 4 5, 2 5 8, 3 7 8,
    1 4 6, 2 5 9, 3 7 9,
    1 4 7, 2 5 10, 3 7 10,
    1 4 8, 2 6 7, 3 8 9,
    1 4 9, 2 6 8, 3 8 10,
    1 4 10, 2 6 9, 3 9 10,
    1 5 6, 2 6 10,
    1 5 7, 2 7 8,
    1 5 8, 2 7 9,
    1 5 9, 2 7 10,
    1 5 10, 2 8 9,
    1 6 7, 2 8 10,
    1 6 8, 2 9 10,
    1 6 9,
    1 6 10,
    1 7 8,
    1 7 9,
    1 7 10,
    1 8 9,
    1 9 10,

    Thanks and regards

    Madhusoodan

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Wow! I expected something with just a few combinations.

    OK, in doing the work by hand, what did you notice?

    Did it hit you that the right hand number increments the fastest?

    So nested loops are one way. Think of an odometer on a bike or car. Your numbers are like the wheels of that odometer, with the exception that the wheel on the right, must always be greater than the wheel on it's left.

    You had a start on that with your program, but the logic was too limited. Let me put together something for you, after I get some much-needed sleep.

    Here's a start:

    Code:
    /* 3 in 5.c getting every 3 numbers, chosen from 1-5 
    
    status: just starting
    
    */
    
    #include <stdio.h>
    
    int main() {
      int w1, w2, w3; 
      
      printf("\n\n\n");
      for(w1 = 1; w1 < 6; w1++) {
         
        for(w2 = w1+1; w2 < 6; w2++) {
          if(w2 == w1)                   //we don't want it :(
            continue;
          for(w3 = w2+1; w3 < 6; w3++) {
            if(w3 == w2 || w3 == w1)
              continue;                 //ditto
            else 
              printf("%2d %2d %2d\n", w1,w2,w3);
          }
        }
      }
    
      printf("\n\n\t\t\t     press enter when ready");
      w1 = getchar();
      return 0;
    }
    (BTW, to make anything "kind of" line up, you need to use code tags around it, but they don't line up as you'd hope). The forum software squeezes spaces if there's more than one between words.
    Last edited by Adak; 11-16-2009 at 06:05 AM.

  8. #8
    Registered User
    Join Date
    Nov 2009
    Posts
    4
    Thanks Sir,

    I understood logic. I also learned little about how to think for a problem solution. Thanks for teaching me different way of thinking about problem.

    Thanks and regards

    Madhusoodan

  9. #9
    Registered User
    Join Date
    May 2010
    Posts
    3
    hi..
    right now me too is strugling with generating combinations..
    this piece of information is really useful.....
    i understod this logic..
    but the thing is how do i save this combination in an array...
    because i need to do a set of calculations for each combination...
    so i need to save the combination and call each combination individually for the calculations.

  10. #10
    Registered User
    Join Date
    May 2010
    Posts
    3
    .5 1 20
    .5 1 40
    .5 1 60
    .5 2 20
    .5 2 40
    .5 2 60
    1.0 1 20
    1.0 1 40
    1.0 1 60
    1.0 2 20
    1.0 2 40
    1.0 2 60

    i need to repeat this till i get 5.0 2 60.
    i have generated the table.
    since the array index and these values are not related.. i am strugling to save this table in a 2 dimentional array.

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    If all you have are:

    .5, 1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5 5 = 10
    1, 2 = 2
    20, 40, 60 = 3

    Then you should have a possible: 10 * 2 * 3 = 60 conbinations? So, you need an array that is 60 rows long, by three columns wide. Or, you could make a structure to store those, since there are really a couple of different types data values, and just use an array of 60 of that structure.


    Quzah.
    Hope is the first step on the road to disappointment.

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by ymadhusoodan View Post
    Respected members,

    I am new student of programming and currently learning C. I have an assignment of generating all possible combinations of n elements out of K numbers. After searching lot on google, I got following code using nested for loop. But its not working for me. Please help me.
    Respect back at ya - IMHO you've kept your cool very well!
    That was a lot of effort you put into that flowchart only to be told to throw it out. Ditto for coming up with combinations manually.

    Now as for being constructive, the most important thing I'd like to get across (to everyone who ever uses these forums ideally, but I digress), is that when posting here you should never be stating that something just "doesn't work", "isn't working", "wont work", "is not working" etc.
    Always say what it actually does. Does it not compile? Does it crash? Does it get stuck in an infinite loop? Does it give an error? Does it give totally wrong output? Is the output simply formatted incorrectly? These are the kinds of things we need to know as soon as possible from the beginning, and by briefly describing what it actually does instead, you'll be ahead of many of the posters here.

    Do you know how to calculate the number of combinations?

    Could you update us with where you are at now?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  13. #13
    Registered User jephthah's Avatar
    Join Date
    May 2010
    Location
    seattle
    Posts
    49
    do you think our "Respected ymadhusoodan" is still following this thread -- or even working on that problem -- 6 months later?

  14. #14
    Registered User
    Join Date
    May 2010
    Posts
    3
    Quote Originally Posted by quzah View Post
    If all you have are:

    .5, 1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5 5 = 10
    1, 2 = 2
    20, 40, 60 = 3

    Then you should have a possible: 10 * 2 * 3 = 60 conbinations? So, you need an array that is 60 rows long, by three columns wide. Or, you could make a structure to store those, since there are really a couple of different types data values, and just use an array of 60 of that structure.


    Quzah.
    thanks quzah... so far i havent thought of structures while dealing this problem... let me step into it next...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with a program, theres something in it for you
    By engstudent363 in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 01:41 PM
  2. Replies: 4
    Last Post: 02-21-2008, 10:39 AM
  3. Combination program problem
    By Garland in forum C++ Programming
    Replies: 2
    Last Post: 10-10-2007, 03:35 PM
  4. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM