Thread: 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

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);

Originally Posted by Memloop

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.