rank 和 unrank 组合将 k 个球分配到 n 个不同容量的箱中 [英] Rank and unrank combinations to distribute k balls into n bins of different capacities

问题描述

我想将 k 个球分配到 n 个不同容量的箱子中.如何对给定 n、k 和 bin 容量的分布进行排序和取消排序?

I want to distribute k balls into n bins of different capacities. How can I rank and unrank the distributions given n, k, and the bin capacities?

示例:

n := 3

k := 4

bin 容量 := 3,2,1

垃圾桶里的球:

1,2,1, 2,1,1, 2,2,0, 3,0,1, 3,1,0 := 5

1,2,1, 2,1,1, 2,2,0, 3,0,1, 3,1,0 := 5

有公式吗?

推荐答案

我不知道这种技术是否有标准名称，但这是一种我已经成功解决了很多次的问题编程.

I do not know if there is a standard name for this technique, but this is a kind of problem that I have successfully solved many times with a twist on dynamic programming.

我使用动态编程来构建一个数据结构，从中可以进行排名/取消排名，然后构建逻辑来执行排名/取消排名.

What I do using dynamic programming to build a data structure from which the rank/unrank can happen, and then build logic to do the rank/unrank thing.

动态规划部分是最难的.

The dynamic programming piece is hardest.

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)

这是生成排名解决方案的代码:

Here is code to produce a ranked solution:

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)

这是生成解决方案排名的代码.请注意，如果提供无效答案，它会爆炸.

Here is code to produce the rank for a solution. Note that it will blow up if provided with an invalid answer.

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)))

这篇关于rank 和 unrank 组合将 k 个球分配到 n 个不同容量的箱中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！