Unique numbers in C++

Question

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

Answer 1

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

Answer 2

You're look for combination of some characters (0..9) with a certain length (100=2, 1000=3).

Take a look here Algorithm to return all combinations of k elements from n

Answer 3

I would write a class suiting your comparision needs by overloading the correct operators (from the top of my head that should be only less) and go with a std::set.

Answer 4

I would use a hash table, something like this

1) Derive a key from the number derived in such a way that digits with the same number have the same key (e.g. sum the digits, so "124" and "142" have the key 7, or take the product of the digits(+1), so "124" and "142" have the key 30 - have to +1 for the digit 0)

2) Put the numbers in a hash table indexed by its key

Now the test as to whether you already have a number with the same digits is limited to entities in the hash table with the same key. This algorithm requires linear storage and its performance depends on how good a key you can come up with.

Answer 5

First, observe that your rule excludes multiples of 11. (Why?)

Start by generating all 2-digit numbers with the first digit = 1.

Now, generate all 2-digit numbers with the first digit = 2, but don't generate any numbers that match numbers in the first list.

Repeat for 3, but don't generate any numbers from the first two lists.

Observe that, for any 2-digit number ab, for it to qualify, it must be the case that a < b, or you would have already generated the corresponding number ba.

In PASCAL, just because I'm feeling ornery:

var i:integer;  j:integer;
begin
  for i := 1 to 8 do
    for j := i+1 to 9 do
      println(i*10+j);
end;

ADDED A LITTLE LATER

Observe that the numbers you want to generate will always have their digits strictly monotonically increasing. For a number 2abc to qualify, observe that 2 < a < b < c. (Example: 2539 is a match for 2359 and should be rejected.)

Answer 6

#include <stdio.h>

size_t enum_canonical(char* begin, char* end, char min, char max)
{
    if (begin == end) {
        puts(begin);
        putchar('\n');
        return 1;
    }

    size_t result_count = 0;
    --end;
    for( *end = min; *end <= max; ++*end )
        result_count += enum_canonical(begin, end, min, *end);

    return result_count;
}

int main(void)
{
    char buff[7];
    printf("%d results\n", enum_canonical(buff, &(buff[6] = '\0'), '0', '9'));
}

Demo: http://ideone.com/BWGdg

Answer 7

Lets take 1 to 1000. Since there are 4 digits in 1000, I print 1 as 0001, so 0001, 0010, 0100, 1000 are same number as per my algorithm. Also 0120, 0012, 0210, 0102, 0201, 0021 are same numbers.

Here is the program:

int main()
{
    int i=0, j=0, k=0;

    while(i<=9)
    {
        int unique=(i*100 + j*10 + k);
        printf("unique number : %3d\n", unique);

        if(j==9 && k==9)
        {
            i++;
            k=i;
            j=i;
        }
        else if(k==9)
        {
            j++;
            k=j;
        }
        else 
            k++;
    }

}

Answer 8

Seems like it can be as simple as this:

list = {}
for (j = 1 to 100)
     if (j is not excluded from list)
          list += j;

Really, only the if condition is interesting: needs to examine all relevant properties of the list items.

Answer 9

Create a function which takes a string, and returns an array of strings with all the possible permutations of the characters in that string. It wouldn't be hard, but it would probably be easiest to make recursive. Though, easier said than done.

Once you have that function, and it returns the array, you simply go through the array and remove the indecies which share a common number with one in the array.

Answer 10

I'd use a set for the permutations of the digits of the number:

std::vector<int> list_unwanted = digit_permutations(number);
std::unordered_set<int> set_unwanted(begin(list_unwanted), end(list_unwanted));

Then loop from 0 to the limit, not adding unwanted numbers by checking if they're in the set set_unwanted:

std::vector<int> numbers;
numbers.reserve(limit - set_unwanted.count());

for (int i = 0; i < limit; ++i)
    if (!set_unwanted.count(i))

Answer 11

If you have a set of digits, a whatever permutation of this set is not a valid solution, so first of all make a function to estabilish if a set of digits is a permutation of another set. To get single digits you can divide by 10 recursively, until you get a zero value. If you put all the digits in an array like [1,2,4], to check if antoher array is a permutation (you check it only if they have the same length) of antoher set:

bool permutation(int *a, int *b, int n) // n leading dimension
{
    bool result=true, vector[n]={false};
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n ;j++)
        {
            if(a[i]==b[j])
                vector[i]=false;
        }
    }
    for(int i=0;i<n && result;i++)
        result=(vector[i]==true);   // if vector[i] is false, result is false, is
                                    // not a permutation and the loop ends
    return result;
}

I haven't tested it, but I think it works, otherwise tell me. As for putting all digits in an array, I think it's pretty easy. Once generating all numbers, you check that a certain number is not a permutation of an already taken number.

Answer 12

Here's my idea, for each value put the digits of it in a set. Use that set as a key to another set that keeps track of which numbers have been used. In my case I use a bit field as a set for the digits, i.e. digit 0 is represented by a 1, digit 1 is represented by a 2 (2 by a 4 and so on). Too tired to explain, here's tha codez:

unsigned int get_digits(int v)
{
  unsigned int rv = 0;
  do
  {
    rv |= 1 << (v % 10);
    v /= 10;
  } while(v);
  return rv;
}

void unique_ints(int n)
{
  std::set<unsigned int> used_combinations;
  for(int i = 0; i < n; ++i)
  {
    const unsigned int d = get_digits(i);
    if(used_combinations.find(d) == used_combinations.end())
    {
      used_combinations.insert(d);
      // cout or some other way to store the value
      std::cout << i <<  std::endl;
    }
  }
}