Уникальные числа в C ++

Я пытаюсь эффективно перечислять числа от 1 до 100. Однако мне приходится избавляться от чисел с одинаковыми цифрами.
Пример: 12 в соответствии с этим правилом совпадает с 21 13, равно 31 14 равно 41, поэтому для цикла for он не будет переходить по тем же номерам.
Я думаю несколько трюков, таких как получение всех чисел от 1 до 100, а затем удаление найденных перестановок текущего номера. Причина, по которой я спрашиваю об этом, потому что в больших пределах, таких как 100000, это провалится. Другой пример: 124 равен 142,241,214,412,421

Вы можете применить рекурсию. Прототипом этой функции тогда является:

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

EDIT: для завершения я представляю здесь свое решение (я думаю, что он имеет лучшую читаемость, чем у Ben Voigt и восходящий порядок вывода

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

и вот тестовый код

http://ideone.com/Xm8Mv

Как это работает?

Это одна из classиков в рекурсии. Сначала условие остановки. И тогда есть основной цикл.
Основной цикл, где идет от start_from_digit потому что все сгенерированные цифры будут в неубывающем порядке. Например, если current_number равен 15 он будет вызывать 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) 

В каждом вызове он проверяет, достигли ли мы конца num_of_remaining_digits и если не будет продолжаться от цифры, которая будет нажата как start_from_digit (2-й параметр), используя current_number

Вы ищете комбинацию некоторых символов (0..9) с определенной длиной (100 = 2, 1000 = 3).

Посмотрите здесь Алгоритм, чтобы вернуть все комбинации k элементов из n

Я бы написал class, удовлетворяющий вашим потребностям сравнения, перегружая правильных операторов (от верхней части головы, которые должны быть less ), и переходите к std::set .

Я бы использовал хеш-таблицу, что-то вроде этого

1) Выведите ключ из числа, полученного таким образом, что цифры с одинаковым номером имеют один и тот же ключ (например, суммируйте цифры, поэтому «124» и «142» имеют ключ 7 или возьмите произведение цифр ( +1), поэтому «124» и «142» имеют ключ 30 – должны иметь +1 для цифры 0)

2) Поместите числа в hash-таблицу, индексированную по ее ключу

Теперь тест на то, что у вас уже есть номер с одинаковыми цифрами, ограничен сущностями в hash-таблице с тем же ключом. Этот алгоритм требует линейного хранения, и его производительность зависит от того, насколько хорош ключ, с которым вы можете столкнуться.

 #include  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')); } 

Демо: http://ideone.com/BWGdg

Во-первых, обратите внимание, что ваше правило исключает кратные 11. (Почему?)

Начните с создания всех двузначных чисел с первой цифрой = 1.

Теперь сгенерируйте все двузначные числа с первой цифрой = 2, но не генерируйте числа, соответствующие номерам в первом списке.

Повторите для 3, но не генерируйте числа из первых двух списков.

Обратите внимание, что для любого 2-значного числа ab, для того, чтобы оно получило квалификацию, должно быть, что a

В PASCAL, только потому, что я чувствую себя 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; 

ДОБАВЛЕНЫ МАЛЕНЬКИЙ ПОЗЖЕ

Обратите внимание, что числа, которые вы хотите создать, всегда будут иметь свои monoтонно возрастающие цифры. Для определения числа 2abc, заметим, что 2

Позволяет принимать от 1 до 1000. Поскольку в 1000 единиц есть четыре цифры, я печатаю 1 как 0001, поэтому 0001, 0010, 0100, 1000 имеют такое же количество, как в моем алгоритме. Также 0120, 0012, 0210, 0102, 0201, 0021 являются одинаковыми номерами.

Вот программа:

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

Похоже, это может быть так просто:

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

Действительно, интересно только условие if : необходимо изучить все соответствующие свойства элементов списка.

Создайте функцию, которая берет строку и возвращает массив строк со всеми возможными перестановками символов в этой строке. Это было бы непросто, но, вероятно, было бы проще сделать рекурсивный. Хотя, проще сказать, чем сделать.

Когда у вас есть эта функция и она возвращает массив, вы просто просматриваете массив и удаляете индексы, которые имеют общее число с одним в массиве.

Я бы использовал set для перестановок цифр числа:

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

Затем цикл от 0 до предела, не добавляя ненужные номера, проверяя, находятся ли они в наборе set_unwanted :

 std::vector numbers; numbers.reserve(limit - set_unwanted.count()); for (int i = 0; i < limit; ++i) if (!set_unwanted.count(i)) 

Если у вас есть набор цифр, любая перестановка этого набора не является допустимым решением, поэтому прежде всего создайте функцию, чтобы установить, если набор цифр является перестановкой другого набора. Чтобы получить отдельные цифры, вы можете разделить на 10 рекурсивно, пока не получите нулевое значение. Если вы поместили все цифры в массив, подобный [1,2,4], чтобы проверить, является ли antoher-массив перестановкой (вы проверяете его, только если они имеют одинаковую длину) набора antoher:

 bool permutation(int *a, int *b, int n) // n leading dimension { bool result=true, vector[n]={false}; for(int i=0;i 

Я не тестировал его, но я думаю, что он работает, иначе скажите мне. Что касается ввода всех цифр в массив, я думаю, что это довольно легко. После генерации всех чисел вы проверяете, что определенное число не является перестановкой уже принятого числа.

Вот моя идея, поскольку каждое значение помещает цифры в набор. Используйте это как ключ к другому набору, который отслеживает, какие номера были использованы. В моем случае я использую битовое поле как набор для цифр, то есть цифра 0 представлена ​​цифрой 1, цифра 1 представлена ​​2 (2 на 4 и так далее). Слишком устал объяснять, вот код:

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