Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Unique numbers in C++ [closed]

I'm trying to efficiently list numbers between 1 and 100. However I have to get rid of numbers with same digits.
Example: 12 according to this rule is the same of 21 13 is 31 14 is 41 so the for loop it won't go over the same numbers.
I'm thinking a few tricks such as getting all the numbers from 1 to 100 and then deleting the found permutations of current number. The reason I'm asking this because in large limits like 100000 it will fail. Another example: 124 is equal to 142,241,214,412,421

like image 649
Ali Avatar asked Jan 29 '12 20:01

Ali


1 Answers

You can apply recursion. Prototype of this function is then like:

print_digits(int num_of_remaining_digits,int start_from_digit, int current_number);

EDIT: for completion I present here my solution (i think it has better readbility than from Ben Voigt and ascending output order

void print_digits(int num_of_remaining_digits,int start_from_digit, int current_number)
{
  if(num_of_remaining_digits == 0) 
  {
    std::cout << current_number << std::endl;
    return;
  }

  for(int i=start_from_digit;i<=9;i++)
  {
     print_digits(num_of_remaining_digits-1,i,10*current_number+i);
  }
}

and here is testing code

http://ideone.com/Xm8Mv

How this works?

It is one of classics in recursion. First there is stopping condition. And then there is main loop.
Main loop where goes from start_from_digit because all generated digits will be in non decreasing order. For instance if current_number is 15 it will call print_digits whith

print_digits(num_of_remaining_digits-1,5,155)
print_digits(num_of_remaining_digits-1,6,156)
print_digits(num_of_remaining_digits-1,7,157)
print_digits(num_of_remaining_digits-1,8,158)
print_digits(num_of_remaining_digits-1,9,159)

In each call it will check if we reached end whit num_of_remaining_digits and if not will continue from digit that is pushed as start_from_digit (2nd param) using current_number

like image 146
Luka Rahne Avatar answered Oct 07 '22 07:10

Luka Rahne