Unique numbers in C ++

Question

I try to efficiently list numbers from 1 to 100. However, I have to get rid of numbers with the same numbers.
<B> Example: 12 according to this rule, the same is from 21 13 - 31 14 - 41 so the for loop will not go through the same numbers.
I think a few tricks, such as getting all numbers from 1 to 100, and then deleting the found permutations of the current number. The reason I ask about this is because in large limits, such as 100,000, it will fail. Another example: 124 is 142,241,214,412,421

Answer 1

You can apply recursion. The prototype of this function is then:

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

EDIT: to complete, I present my solution here (I think it has better readability than Ben Voigt and increasing 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 the test code

http://ideone.com/Xm8Mv

How it works?

This is one of the classics in recursion. First, the stop condition. And then there is the main cycle.
The main loop, where goes from start_from_digit , because all the generated numbers will be in non-decreasing order. For example, 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 checks to see if we have reached the end of num_of_remaining_digits , and if it does not continue with the digit that will be pressed as start_from_digit (2nd parameter) using current_number

Answer 2

You are looking for a combination of some characters (0..9) with a specific length (100 = 2, 1000 = 3).

Look here Algorithm for returning all combinations of k elements from n

Answer 3

I would write a class that satisfies your comparison needs, overloading the correct operators (from the top of the head, which should only be less ), and go to std::set .

Answer 4

I would use a hash table, something like this

1) Derive the key from the number obtained in such a way that the numbers with the same number have the same key (for example, sum the numbers, so "124" and "142" have the key 7 or take the product of the number (+1), therefore " 124 "and" 142 "have a key of 30 - must have +1 for the number 0)

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

Now checking to see if you 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 may encounter.

Answer 5

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

Start by creating all two-digit numbers with the first digit = 1.

Now generate all two-digit numbers with the first digit = 2, but do not generate numbers corresponding to the numbers in the first list.

Repeat for 3, but do not generate numbers from the first two lists.

Note that for any 2-digit number ab, in order for it to qualify, it must be b, or you have already created the corresponding number ba.

In PASCAL, just because I feel orerery:

 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 LESS LATER

Observe that the numbers you want to generate will always have strictly monotonically increasing numbers. To determine the number 2abc, make sure 2 <a <b <s. (Example: 2539 corresponds to 2359 and must 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

Let's take from 1 to 1000. Since there are 4 digits in 1000, I print 1 as 0001, so 0001, 0010, 0100, 1000 is the same amount as in my algorithm. Also 0120, 0012, 0210, 0102, 0201, 0021 are the 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

It seems like it could be that simple:

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

Indeed, only the if condition is interesting: you need to study all the relevant properties of the list items.

Answer 9

Create a function that takes a string and returns an array of strings with all possible permutations of characters in that string. It would not be easy, but it would probably be easier to do recursive. Although, easier said than done.

Once you have this function and it will return an array, you just go to the array and delete the indexes that have a total number with one in the array.

Answer 10

I would use set to permute the digits of a 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 without adding unnecessary numbers, checking to see if they are in 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 numbers, any permutation of this set is not a valid solution, so first of all create a function to set if the set of numbers is a permutation of another set. To get individual 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 the antoher array is a permutation (you only check if they have the same length) of the 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 have not tested it, but I think it works, otherwise tell me. As for entering all the digits into an array, I think this is pretty easy. After creating all the numbers, you verify that a certain number is not a permutation of an already accepted number.

Answer 12

Here is my idea, for each value put its numbers in a set. Use this as a key to another set that keeps track of which numbers have been used. In my case, I use the bit field as a set for numbers, that is, the number 0 is represented by the number 1, the number 1 is represented by 2 (2 by 4, and so on). Too tired to explain, here is the code:

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