Rank 和 unrank 组合将 k 个球分配到 n 个不同容量的箱子中
Rank and unrank combinations to distribute k balls into n bins of different capacities
我想将 k
个球分配到 n
个不同容量的箱子中。如何对给定 n
、k
和 bin 容量的分布进行排序和取消排序?
示例:
n := 3
k := 4
bin capacities := 3,2,1
垃圾箱中的球:
1,2,1
, 2,1,1
, 2,2,0
, 3,0,1
, 3,1,0
:= 5
有公式吗?
您可以递归定义此类组合的数量。给定 k
个球和容器容量 q_1, ..., q_n
,对于 0
和 q_1
之间的每个 j
,将 j
个球放入 q_1
和将剩余的 k-j
个球分配到其他箱子中。
这是一个快速 Python 实施:
from functools import lru_cache
@lru_cache(None)
def f(n, *qs):
if not qs:
return 1 if n == 0 else 0
q = qs[0]
return sum(f(n-j, *qs[1:]) for j in range(q+1))
f(4, 3, 2, 1)
# 5
这里有一个方法(伪代码),虽然它看起来不是很有效。在球的数量不适合总剩余容量的地方添加一些短路可能是明智的。如果给定的容量列表将被多次使用,一些巧妙的缓存可能会有所帮助。
所有数字都是非负整数。函数 ArrayTail(array a)
是其元素都是输入数组第一个之后的元素的子数组。函数 ArrayCon(number head, array a)
是数组,其元素为 head
后跟 a
.
的元素
function Count(array capacities, number balls) -> number
If balls == 0:
return 1
Else if capacities is empty:
return 0
Else:
Let sum: number
sum <- 0
For b from 0 to max(balls, capacities[0]):
sum <- sum + Count(ArrayTail(capacities), b)
End For
return sum
End If/Else
End function
function Rank(array capacities, array counts) -> number
Precondition: length(capacities) == length(counts)
Precondition: counts[i] <= capacities[i] for all i < length(counts)
If counts is empty:
return 0
Else:
Let total: number
total <- 0
For c in counts:
total <- total + c
End For
Let r: number
r <- Rank(ArrayTail(capacities), ArrayTail(counts))
For b from 0 to (counts[0]-1):
r <- r + Count(ArrayTail(capacities), total - b)
End For
return r
End If/Else
End function
function Unrank(array capacities, number balls, number rank) -> array
Precondition: rank < Count(capacities, balls)
If capacities is empty:
return empty array
Else
Let c0: number
c0 <- 0
Loop until "return":
Let subcount: number
subcount <- Count(ArrayTail(capacities), balls-c0)
If subcount <= rank:
c0 <- c0 + 1
rank <- rank - subcount
Else
return ArrayCon(c0, Unrank(ArrayTail(capacities), balls-c0, rank))
End If/Else
End Loop
End If/Else
End function
我不知道这种技术是否有一个标准的名称,但这是我已经成功解决了很多次动态规划的问题。
我使用动态编程构建一个数据结构,rank/unrank 可以从中发生,然后构建逻辑来完成 rank/unrank 事情。
动态规划最难
import collections
BallSolutions = collections.namedtuple('BallSolutions', 'bin count balls next_bin_solutions next_balls_solutions');
def find_ball_solutions (balls, bin_capacities):
# How many balls can fit in the remaining bins?
capacity_sum = [0 for _ in bin_capacities]
capacity_sum[-1] = bin_capacities[-1]
for i in range(len(bin_capacities) - 2, -1, -1):
capacity_sum[i] = capacity_sum[i+1] + bin_capacities[i]
cache = {}
def _search (bin_index, remaining_balls):
if len(bin_capacities) <= bin_index:
return None
elif capacity_sum[bin_index] < remaining_balls:
return None
elif (bin_index, remaining_balls) not in cache:
if bin_index + 1 == len(bin_capacities):
cache[(bin_index, remaining_balls)] = BallSolutions(
bin=bin_index, count=1, balls=remaining_balls, next_bin_solutions=None, next_balls_solutions=None)
else:
this_solution = None
for this_balls in range(min([remaining_balls, bin_capacities[bin_index]]), -1, -1):
next_bin_solutions = _search(bin_index+1, remaining_balls - this_balls)
if next_bin_solutions is None:
break # We already found the fewest balls that can go in this bin.
else:
this_count = next_bin_solutions.count
if this_solution is not None:
this_count = this_count + this_solution.count
next_solution = BallSolutions(
bin=bin_index, count=this_count,
balls=this_balls, next_bin_solutions=next_bin_solutions,
next_balls_solutions=this_solution)
this_solution = next_solution
cache[(bin_index, remaining_balls)] = this_solution
return cache[(bin_index, remaining_balls)]
return _search(0, balls)
这是生成排名解决方案的代码:
def find_ranked_solution (solutions, n):
if solutions is None:
return None
elif n < 0:
return None
elif solutions.next_bin_solutions is None:
if n == 0:
return [solutions.balls]
else:
return None
elif n < solutions.next_bin_solutions.count:
return [solutions.balls] + find_ranked_solution(solutions.next_bin_solutions, n)
else:
return find_ranked_solution(solutions.next_balls_solutions, n - solutions.next_bin_solutions.count)
这是生成解决方案排名的代码。请注意,如果提供无效答案,它将爆炸。
def find_solution_rank (solutions, solution):
n = 0
while solutions.balls < solution[0]:
n = n + solutions.next_bin_solutions.count
solutions = solutions.next_balls_solutions
if 1 < len(solution):
n = n + find_solution_rank(solutions.next_bin_solutions, solution[1:])
return n
这里是一些测试代码:
s = find_ball_solutions(4, [3, 2, 1])
for i in range(6):
r = find_ranked_solution(s, i)
print((i, r, find_solution_rank(s, r)))
我想将 k
个球分配到 n
个不同容量的箱子中。如何对给定 n
、k
和 bin 容量的分布进行排序和取消排序?
示例:
n := 3
k := 4
bin capacities := 3,2,1
垃圾箱中的球:
1,2,1
, 2,1,1
, 2,2,0
, 3,0,1
, 3,1,0
:= 5
有公式吗?
您可以递归定义此类组合的数量。给定 k
个球和容器容量 q_1, ..., q_n
,对于 0
和 q_1
之间的每个 j
,将 j
个球放入 q_1
和将剩余的 k-j
个球分配到其他箱子中。
这是一个快速 Python 实施:
from functools import lru_cache
@lru_cache(None)
def f(n, *qs):
if not qs:
return 1 if n == 0 else 0
q = qs[0]
return sum(f(n-j, *qs[1:]) for j in range(q+1))
f(4, 3, 2, 1)
# 5
这里有一个方法(伪代码),虽然它看起来不是很有效。在球的数量不适合总剩余容量的地方添加一些短路可能是明智的。如果给定的容量列表将被多次使用,一些巧妙的缓存可能会有所帮助。
所有数字都是非负整数。函数 ArrayTail(array a)
是其元素都是输入数组第一个之后的元素的子数组。函数 ArrayCon(number head, array a)
是数组,其元素为 head
后跟 a
.
function Count(array capacities, number balls) -> number
If balls == 0:
return 1
Else if capacities is empty:
return 0
Else:
Let sum: number
sum <- 0
For b from 0 to max(balls, capacities[0]):
sum <- sum + Count(ArrayTail(capacities), b)
End For
return sum
End If/Else
End function
function Rank(array capacities, array counts) -> number
Precondition: length(capacities) == length(counts)
Precondition: counts[i] <= capacities[i] for all i < length(counts)
If counts is empty:
return 0
Else:
Let total: number
total <- 0
For c in counts:
total <- total + c
End For
Let r: number
r <- Rank(ArrayTail(capacities), ArrayTail(counts))
For b from 0 to (counts[0]-1):
r <- r + Count(ArrayTail(capacities), total - b)
End For
return r
End If/Else
End function
function Unrank(array capacities, number balls, number rank) -> array
Precondition: rank < Count(capacities, balls)
If capacities is empty:
return empty array
Else
Let c0: number
c0 <- 0
Loop until "return":
Let subcount: number
subcount <- Count(ArrayTail(capacities), balls-c0)
If subcount <= rank:
c0 <- c0 + 1
rank <- rank - subcount
Else
return ArrayCon(c0, Unrank(ArrayTail(capacities), balls-c0, rank))
End If/Else
End Loop
End If/Else
End function
我不知道这种技术是否有一个标准的名称,但这是我已经成功解决了很多次动态规划的问题。
我使用动态编程构建一个数据结构,rank/unrank 可以从中发生,然后构建逻辑来完成 rank/unrank 事情。
动态规划最难
import collections
BallSolutions = collections.namedtuple('BallSolutions', 'bin count balls next_bin_solutions next_balls_solutions');
def find_ball_solutions (balls, bin_capacities):
# How many balls can fit in the remaining bins?
capacity_sum = [0 for _ in bin_capacities]
capacity_sum[-1] = bin_capacities[-1]
for i in range(len(bin_capacities) - 2, -1, -1):
capacity_sum[i] = capacity_sum[i+1] + bin_capacities[i]
cache = {}
def _search (bin_index, remaining_balls):
if len(bin_capacities) <= bin_index:
return None
elif capacity_sum[bin_index] < remaining_balls:
return None
elif (bin_index, remaining_balls) not in cache:
if bin_index + 1 == len(bin_capacities):
cache[(bin_index, remaining_balls)] = BallSolutions(
bin=bin_index, count=1, balls=remaining_balls, next_bin_solutions=None, next_balls_solutions=None)
else:
this_solution = None
for this_balls in range(min([remaining_balls, bin_capacities[bin_index]]), -1, -1):
next_bin_solutions = _search(bin_index+1, remaining_balls - this_balls)
if next_bin_solutions is None:
break # We already found the fewest balls that can go in this bin.
else:
this_count = next_bin_solutions.count
if this_solution is not None:
this_count = this_count + this_solution.count
next_solution = BallSolutions(
bin=bin_index, count=this_count,
balls=this_balls, next_bin_solutions=next_bin_solutions,
next_balls_solutions=this_solution)
this_solution = next_solution
cache[(bin_index, remaining_balls)] = this_solution
return cache[(bin_index, remaining_balls)]
return _search(0, balls)
这是生成排名解决方案的代码:
def find_ranked_solution (solutions, n):
if solutions is None:
return None
elif n < 0:
return None
elif solutions.next_bin_solutions is None:
if n == 0:
return [solutions.balls]
else:
return None
elif n < solutions.next_bin_solutions.count:
return [solutions.balls] + find_ranked_solution(solutions.next_bin_solutions, n)
else:
return find_ranked_solution(solutions.next_balls_solutions, n - solutions.next_bin_solutions.count)
这是生成解决方案排名的代码。请注意,如果提供无效答案,它将爆炸。
def find_solution_rank (solutions, solution):
n = 0
while solutions.balls < solution[0]:
n = n + solutions.next_bin_solutions.count
solutions = solutions.next_balls_solutions
if 1 < len(solution):
n = n + find_solution_rank(solutions.next_bin_solutions, solution[1:])
return n
这里是一些测试代码:
s = find_ball_solutions(4, [3, 2, 1])
for i in range(6):
r = find_ranked_solution(s, i)
print((i, r, find_solution_rank(s, r)))