查找给定范围内具有给定位数的整数的算法 [英] algorithm to find number of integers with given digits within a given range

问题描述

如果以列表 list 的形式提供了完整的数字集，并且我想知道在给定范围内它们可以形成多少个(有效)整数 [A，B] ，我可以使用哪种算法有效地做到这一点?

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?

例如，给定一个数字列表(包含重复和零)， list = {5、3、3、2、0、0} ，我想知道可以形成多少个整数范围在 [A，B] = [20，400] (含)范围内.例如，在这种情况下， 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 均有效.

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.

推荐答案

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 

通过案例解决:

对于数字大小为2，即__:

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)

对于尺寸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.

更有趣的情况是最大限制为522(而不是400):

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

在您的情况下: countComb(''，2,400,20，['0'，'0'，'2'，'3'，'3'，'5'])+countComb(''，3,400,20，['0'，'0'，'2'，'3'，'3'，'5'])将给出答案.

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.

这篇关于查找给定范围内具有给定位数的整数的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！