algorithm to find number of integers with given digits within a given range

Question

If I am given the full set of digits in the form of a list list and I want to know how many (valid) integers they can form within a given range [A, B], what algorithm can I use to do it efficiently?

For example, given a list of digits (containing duplicates and zeros) list={5, 3, 3, 2, 0, 0}, I want to know how many integers can be formed in the range [A, B]=[20, 400] inclusive. For example, in this case, 20, 23, 25, 30, 32, 33, 35, 50, 52, 53, 200, 203, 205, 230, 233, 235, 250, 253, 300, 302, 303, 305, 320, 323, 325, 330, 332, 335, 350, 352, 353 are all valid.

Answer 1

For a list of n digits, z of which are zero, a lower bound l, and an upper bound u...

Step 1: The Easy Stuff

Consider a situation in which you have a 2-digit lower bound and a 4-digit upper bound. While it might be tricky to determine how many 2- and 4-digit numbers are within the bounds, we at least know that all 3-digit numbers are. And if the bounds were a 2-digit number and a 5-digit number, you know that all 3- and 4-digit numbers are fair game.

So let's generalize this to to a lower bound with a digits and an upper bound with b digits. For every k between a and b (not including a and b, themselves), all k-digit numbers are within the range.

How many such numbers are there? Consider how you'd pick them: the first digit must be one of the n numbers which is non-zero (so one of (n - z) numbers), and the rest are picked from the yet-unpicked list, i.e. (n-1) choices for the second digit, (n-2) for the third, etc. So this is looking like a factorial, but with a weird first term. How many numbers of the n are picked? Why, k of them, which means we have to divide by (n - k)! to ensure we only pick k digits in total. So the equation for each k looks something like: (n - z)(n - 1)!/(n - k)! Plug in every k in the range (a, b), and you have the number of (a+1)- to (b-1)-digit numbers possible, all of which must be valid.

Step 2: The Edge Cases

Things are a little bit trickier when you consider a- and b-digit numbers. I don't think you can avoid starting a depth-first search through all possible combinations of digits, but you can at least abort on an entire branch if it exceeds the boundary.

For example, if your list contained { 7, 5, 2, 3, 0 } and you had an upper bound of 520, your search might go something like the following:

Pick the 7: does 7 work in the hundreds place? No, because 700 > 520;
  abort this branch entirely (i.e. don't consider 752, 753, 750, 725, etc.)
Pick the 5: does 5 work in the hundreds place? Yes, because 500 <= 520.
    Pick the 7: does 7 work in the tens place? No, because 570 > 520.
      Abort this branch (i.e. don't consider 573, 570, etc.)
    Pick the 2: does 2 work in the tens place? Yes, because 520 <= 520.
        Pick the 7: does 7 work in the ones place? No, because 527 > 520.
        Pick the 3: does 3 work in the ones place? No, because 523 > 520.
        Pick the 0: does 0 work in the ones place? Yes, because 520 <= 520.
        Oh hey, we found a number. Make sure to count it. 
    Pick the 3: does 3 work in the tens place? No; abort this branch.
    Pick the 0: does 0 work in the tens place? Yes.
        ...and so on. 

...and then you'd do the same for the lower bound, but flipping the comparators. It's not nearly as efficient as the k-digit combinations in the (a, b) interval (i.e. O(1)), but at least you can avoid a good deal by pruning branches that must be impossible early on. In any case, this strategy ensures you only have to actually enumerate the two edge cases that are the boundaries, regardless of how wide your (a, b) interval is (or if you have 0 as your lower bound, only one edge case).

EDIT:

Something I forgot to mention (sorry, I typed all of the above on the bus home):

When doing the depth-first search, you actually only have to recurse when your first number equals the first number of the bound. That is, if your bound is 520 and you've just picked 3 as your first number, you can just add (n-1)!/(n-3)! immediately and skip the entire branch, because all 3-digit numbers beginning with 300 are certainly all below 500.

Answer 2

Step 1: Find the number of digits your answers are likely to fall in. In your 
        example it is 2 or 3.

Step 2: For a given number size (number of digits)

    Step 2a: Pick the possibilities for the first (most significant digit). 
    Find the min and max number starting with that digit (ascend or descending
    order of rest of the digits). If both of them fall into the range:
        step 2ai: Count the number of digits starting with that first digit and
        update that count
    Step 2b: Else if both max and min are out of range, ignore. 
    Step 2c: Otherwise, add each possible digit as second most significant digit
    and repeat the same step 

Solving by example of your case:

For number size of 2 i.e. __:

0_ : Ignore since it starts with 0
2_ : Minimum=20, Max=25. Both are in range. So update count by 3 (second digit might be 0,3,5)
3_ : Minimum=30, Max=35. Both are in range. So update count by 4 (second digit might be 0,2,3,5)
5_ : Minimum=50, Max=53. Both are in range. So update count by 3 (second digit might be 0,2,3)

For size 3:

0__ : Ignore since it starts with 0
2__ : Minimum=200, max=253. Both are in range. Find the number of ways you can choose 2 numbers from a set of {0,0,3,3,5}, and update the count.
3__ : Minimum=300, max=353. Both are in range. Find the number of ways you can choose 2 numbers from a set of {0,0,2,3,5}, and update the count.
5__ : Minimum=500, max=532. Both are out of range. Ignore.

A more interesting case is when max limit is 522 (instead of 400):

5__ : Minimum=500, max=532. Max out of range.
    50_: Minimum=500, Max=503. Both in range. Add number of ways you can choose one digit from {0,2,3,5}
    52_: Minimum=520, Max=523. Max out of range.
        520: In range. Add 1 to count.
        522: In range. Add 1 to count.
        523: Out of range. Ignore.
    53_: Minimum=530, Max=532. Both are out of range. Ignore.



def countComb(currentVal, digSize, maxVal, minVal, remSet):
    minPosVal, maxPosVal = calculateMinMax( currentVal, digSize, remSet)
    if maxVal>= minPosVal >= minVal and maxVal>= maxPosVal >= minVal
        return numberPermutations(remSet,digSize, currentVal)
    elif minPosVal< minVal and maxPosVal < minVal or minPosVal> maxVal and maxPosVal > maxVal:
        return 0
    else:
        count=0
        for k in unique(remSet):
            tmpRemSet = [i for i in remSet]
            tmpRemSet.remove(k)
            count+= countComb(currentVal+k, digSize, maxVal, minVal, tmpRemSet)
        return count

In your case: countComb('',2,400,20,['0','0','2','3','3','5']) + countComb('',3,400,20,['0','0','2','3','3','5']) will give the answer.

def calculateMinMax( currentVal, digSize, remSet):
    numRemain = digSize - len(currentVal)
    minPosVal = int( sorted(remSet)[:numRemain] )
    maxPosVal = int( sorted(remSet,reverse=True)[:numRemain] )
    return minPosVal,maxPosVal

numberPermutations(remSet,digSize, currentVal): Basically number of ways 
you can choose (digSize-len(currentVal)) values from remSet. See permutations
with repeats.

Answer 3

If the range is small but the list is big, the easy solution is just loop over the range and check if every number can be generated from the list. The checking can be made fast by using a hash table or an array with a count for how many times each number in the list can still be used.