как найти различные цифры цифр в диапазоне целых чисел?

Question

Предположим, что у меня есть целое число без знака, назовите его низко и друг друга, назовите его высоким, чтобы высокий> низкий. Проблема заключается в том, чтобы найти различные цифры цифр в этом диапазоне. Например, допустим, что low равен 1, а высокий - 20, тогда ответ равен 20, потому что все числа в этом диапазоне имеют разные наборы цифр. Если предположить, что низкий - 1, а высокий - 21, тогда ответ равен 20, потому что 12 и 21 имеют одинаковый набор цифр, т.е. 1, 2. Я не ищу алгоритм bruteforce. Если у кого-то есть лучшее решение, тогда обычный подход с грубой силой , пожалуйста, сообщите ..

Answer 1

Там, очевидно, представляет собой математический ответ на этот вопрос, хотя я признаю, что я не работал его пока еще нет.

Проще говоря, если низкий уровень = 1 и высоких = 99, то мы имеем следующее:

0 - 9 = 10 unique numbers 
10-19 = 10 unique numbers 
20-29 = 9 unique numbers 
30-31 = 8 unique numbers 
40-49 = 7 unique numbers 
50-59 = 6 unique numbers 
60-69 = 5 unique numbers 
70-79 = 4 unique numbers 
80-89 = 3 unique numbers 
90-99 = 2 unique numbers 

Возможно, было бы легче работать, если мы предположили, что все номера должны были иметь одинаковое количество цифр , с ведущими нулями, где это необходимо. Например, 01, 02, 03, 04 для 1, 2, 3, 4. Это означало бы соответствие 01 и 10. Тогда наши изменения распределения числа к:

0 - 9 = 10 unique numbers 
10-19 = 9 unique numbers 
20-29 = 8 unique numbers 
30-31 = 7 unique numbers 
40-49 = 6 unique numbers 
50-59 = 5 unique numbers 
60-69 = 4 unique numbers 
70-79 = 3 unique numbers 
80-89 = 2 unique numbers 
90-99 = 1 unique numbers 

Вы можете видеть, что это должно быть возможно основывать рекурсивную формулу на этом с помощью коэффициентов 10, чтобы определить, сколько уникальных номеров может быть. Трудность заключается в том, как справляться с переменными, начиная с начальной и конечной точек, например. низкий = 25 и высокий = 87. Но все же это начало, я буду думать дальше.

Answer 2

Может быть, это поможет вам начать работу: mathematic combinations

http://www.codeguru.com/cpp/cpp/algorithms/combinations/article.php/c5117

Answer 3

Я думаю, что я, наконец, обернутый вокруг моей головы проблемы.

Давайте диапазон [low,high] и поместить число в пределах этого диапазона в наборы в зависимости от их цифр, например:

• "121" -> установить "112"
• "122" -> набор «122»
• «211» -> установить «112»

Мы хотим знать, количество наборов, который будет содержать единственный элемент.

Я бы предположил, что самый простой способ сделать это на самом деле ... сделать это вот так.

def rangeCount(low, high): 
    sets = defaultdict(list) 
    for i in range(low, high+1): 
    key = `i`.sort()   # obtain digits and sort them 
    sets[key].append(i) 

    count = 0 
    for v in sets.values(): 
    if len(v) == 1: count = count + 1 
    return count 

Хорошо, это перебор, но, по крайней мере, все должны быть на той же странице теперь :)