how to find distinct digit set numbers over a range of integers?

Question

Suppose i have a unsigned integer, call it low and one another call it high such that high>low. The problem is to find distinct digit set numbers over this range. For example, suppose low is 1 and high is 20 then the answer is 20, because all the numbers in this range are of distinct digit sets. If suppose low is 1 and high is 21, then the answer is 20, because 12 and 21 have same digit set i.e.1, 2. I am not looking for a bruteforce algo., if anyone has a better solution then a usual bruteforce approach, please tell..

Answer 1

Maybe this will get you started: mathematic combinations

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

Answer 2

I think I finally wrapped my head around the problem.

Let's take range [low,high] and put the numbers within this range in sets depending on their digits as such:

• "121" --> set "112"
• "122" --> set "122"
• "211" --> set "112"

We want to know the number of sets that will contain a unique element.

I would suggest that the simplest way to do this is actually... to do it like this.

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

Okay, it's bruteforce, but at least everybody should be on the same page now :)

Answer 3

There obviously is a mathematical answer to this, although I'll admit that I haven't worked it out as yet.

Simply put if the low = 1 and high = 99 then we have the following:

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

It would perhaps be easier to work out if we assumed that all numbers had to have the same number of digits, with leading zeros where required. For example 01, 02, 03, 04 for 1, 2, 3, 4. This would mean that 01 and 10 would match. Then our number distribution changes to:

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

You can see that it should be possible to base a recursive formula on this using factors of 10 to determine how many unique numbers there may be. The difficulty will be how to cope with the starting and ending points being variable e.g. low = 25 and high = 87. Still this is a start, I'll think further on it.