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

Question

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

Answer 1

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

Проще говоря, если low = 1 и high = 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

Кажется, я наконец обнял проблему.

Давайте возьмем диапазон [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

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

Answer 3

Может быть, это поможет вам начать: математические комбинации

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