N Digit Combinations

This is a discussion on N Digit Combinations within the C Programming forums, part of the General Programming Boards category; I need help understanding a programming assignment. I need to use recursion to create all the possible combinations of n-digit ...

  1. #1
    Registered User
    Join Date
    Jun 2010
    Posts
    2

    N Digit Combinations

    I need help understanding a programming assignment.

    I need to use recursion to create all the possible combinations of n-digit numbers (n <= 5) that can be obtained from a list of single digit, non-repeating numbers (1-9).

    For example if I have an array containing {1,2} and I wanted all the 3 digit combinations from that I would get: 111 112 121 122 211 212 221 222. Like wise if I wanted all of the 2 digit combinations from {1,2,3} it would be 11 12 13 21 22 23 31 32 33.

    It seems to me that the number of combinations will be k^n, where k is the number of numbers and n is the number of digits but I'm not sure if this is an accurate observation.

    I understand how to solve the problem with a fixed number of digits using loops but I can't seem to figure out how to deal with a variable number of digits other then I would need n-loops for n-digits.

    I don't understand what the base or recursive case for this problem would be. Any hints or pointers would be much appreciated.

    Thanks in advance.

    - Z

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,205
    If you can't describe how you would do it yourself, you can't hope to write code which tells the computer how to do it.

    Imagine you were asked to generate these combinations by hand (on a piece of paper). Describe the approach you would use. Since your brain is not recursive (your brain can't create a temporary new brain to address parts of the problem), the way you would do it yourself will probably be a valid method.
    Right 98% of the time, and don't care about the other 3%.

  3. #3
    Registered User
    Join Date
    Mar 2009
    Posts
    399
    There are different ways of doing it depending on whether or not you want the set of numbers sorted. One easy way of doing it is to pass an accumulator variable along with each recursive call.

    Code:
    void print_combinations(int n, int accumulator);
    For each iteration, pass
    Code:
    print_combinations(n - 1, accumulator + 10^(n - 1) * i)
    where i is the current number from the set of allowed numbers (use a for loop where you call print_combinations).

    For example, for n=3 and the set of allowed numbers={1, 2} we get:
    Code:
    print_combinations(3, 0);
      print_combinations(2, 100);
      print_combinations(2, 200);
        print_combinations(1, 110);
        print_combinations(1, 120);
        print_combinations(1, 210);
        print_combinations(1, 220);
          print_combinations(0, 111);
          print_combinations(0, 112);
          print_combinations(0, 121);
          print_combinations(0, 122);
          print_combinations(0, 211);
          print_combinations(0, 212);
          print_combinations(0, 221);
          print_combinations(0, 222);

  4. #4
    Registered User
    Join Date
    Jun 2010
    Posts
    45
    your call tree is confusing? your sorted it by depth level for some reason...? are the trailing zeroes required?

    this is clearer in my mind, shows the recursion

    Code:
    print_combinations(3, 0);
      print_combinations(2, 1);
        print_combinations(1, 11);
          print_combinations(0, 111);
          print_combinations(0, 112);
        print_combinations(1, 12);
          print_combinations(0, 121);
          print_combinations(0, 122);
      print_combinations(2, 2);
        print_combinations(1, 21);
          print_combinations(0, 211);
          print_combinations(0, 212);
        print_combinations(1, 22);
          print_combinations(0, 221);
          print_combinations(0, 222);
    Last edited by LordPc; 06-20-2010 at 06:04 AM.

  5. #5
    Registered User
    Join Date
    Jun 2010
    Posts
    2
    Quote Originally Posted by Memloop View Post
    There are different ways of doing it depending on whether or not you want the set of numbers sorted. One easy way of doing it is to pass an accumulator variable along with each recursive call.

    Code:
    void print_combinations(int n, int accumulator);
    For each iteration, pass
    Code:
    print_combinations(n - 1, accumulator + 10^(n - 1) * i)
    where i is the current number from the set of allowed numbers (use a for loop where you call print_combinations).

    For example, for n=3 and the set of allowed numbers={1, 2} we get:
    Code:
    print_combinations(3, 0);
      print_combinations(2, 100);
      print_combinations(2, 200);
        print_combinations(1, 110);
        print_combinations(1, 120);
        print_combinations(1, 210);
        print_combinations(1, 220);
          print_combinations(0, 111);
          print_combinations(0, 112);
          print_combinations(0, 121);
          print_combinations(0, 122);
          print_combinations(0, 211);
          print_combinations(0, 212);
          print_combinations(0, 221);
          print_combinations(0, 222);
    brilliant! Shows me how to deal with the variable digits and I can finally see how to break up the recursive cases. Thank you.

  6. #6
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,435
    Come on, people! Since the OP is unable to formula an algorithm to solve the problem, he/she was asked to formulate how he/she would this by hand.
    Then you come in and throw solution to the OP who sill hasn't done the first part.
    Logic is a necessary tool not to be handed out, but to be learned!
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Yes, what would be great would be a "no advice" forum
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Displaying the rightmost digit of a positive number
    By randoms4ever in forum C Programming
    Replies: 6
    Last Post: 10-04-2009, 07:50 AM
  2. error msg instead of the result so far
    By maybabier in forum C Programming
    Replies: 25
    Last Post: 03-20-2009, 02:45 PM
  3. Need help with a program, theres something in it for you
    By engstudent363 in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 12:41 PM
  4. newbie programmer - needs help bad.
    By hortonheat in forum C Programming
    Replies: 17
    Last Post: 10-20-2004, 05:31 PM
  5. Roman number converter
    By BalanusBob in forum C++ Programming
    Replies: 8
    Last Post: 04-23-2002, 06:29 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21