如果我以列表 list
的形式给出了完整的数字集,并且我想知道在给定范围内它们可以形成多少(有效)整数 [A, B]
,我可以使用什么算法来高效地完成它?
例如,给定一个数字列表(包含重复项和零)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
都是有效的。
最佳答案
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 的数字大小,即 __:
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)时:
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'])
会给出答案。
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.
关于查找给定范围内具有给定数字的整数个数的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9474985/