An algorithm for finding the number of integers with given digits in a given range

Question

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

For example, given the 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, all 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 .

Answer 1

 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 

Solution for your case:

For the size of number 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. 

More interesting is the case when the maximum 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 an 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 2

If the range is small, but the list is large, a simple solution is simply to cycle through the range and check whether each number can be created from the list. Checking can be done quickly using a hash table or an array counting how many times each number in the list can still be used.

Answer 3

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

Step 1: Easy Stuff

Consider a situation in which you have a two-digit lower bound and a four-digit upper bound. Although it can be difficult to determine how many 2- and 4-digit numbers are within the boundaries, we at least know that all 3-digit numbers. And if the boundaries were a 2-digit number and a 5-digit number, you know that all 3-digit and 4-digit numbers are fair play.

So let me generalize this to the lower bound with numbers and the upper bound with b digits. For each 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? Think about how you selected them: the first digit should be one of n numbers other than zero (so that one of the (n - z) numbers), and the rest should be selected from an unprinted list, i.e. (N -1) choice for the second digit, (n-2) for the third, etc. So it looks like a factorial, but with a weird first term. How many numbers n are chosen? Why, k of them, which means we should divide by (n - k)! so that we can only dial k digits. So, the equation for each k looks something like this: (n - z) (n - 1)! / (N - k)! Connect each k in the range of (a, b), and you have a number of (a + 1) - to (b-1)-digit numbers, all of which must be valid.

Step 2: edge cases

A little harder if you are considering a- and b-digits. I don’t think that you can avoid starting the depth search with all possible combinations of numbers, but you can at least break the entire branch if it exceeds the border.

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

 Pick the 7: does 7 work in the hundreds place? No, because 700 > 520; abort this branch entirely (ie 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 (ie 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 do the same for the lower bound, but flip the comparators. This is not as effective as a combination of k-digits in the interval (a, b) (i.e. O (1)), but at least you can avoid a good deal by trimming branches that should be impossible at an early stage. In any case, this strategy ensures that you only need to list two extreme cases that are boundaries, no matter how wide your (a, b) span is (or if you have 0 as your lower border, only one edge).

EDIT:

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

When performing a depth search, in fact you only need to overwrite when your first number is equal to the first number of the binding. That is, if your binding is 520, and you just selected 3 as your first number, you can simply add (n-1)! / (N-3)! immediately and skip the whole branch, because all 3-digit numbers starting with 300 are certainly all below 500.