在 Python 中枚举标记球和标记箱问题中的所有可能组合

Question

我正在寻找一种 Pythonic 方式来枚举“带标签的球放入带标签的箱子”问题的所有可能选项。例如，给定 2 个带标签的球和 2 个带标签的箱子，我想得到：

(A, B)

(AB, )

( ,AB)

(B, A)

也就是 (2^2) 4个选项。如果我们给出 3 个球和 3 个箱子，则有 27 种可能性 3^3。例如：

(A, B, C) (美国广播公司, , ) ( , , 字母表) (AB, C, ) （出租车） ( ,BC, A) 等等...

我正在考虑解决方案 (AB, ) 和 (BA, ) 相同的项目。

Answer 1

计算对象

这些对象在很多地方也被称为 k-分区。

我们可以先对它们进行计数，然后使用计数方法来测试我们是否生成了正确数量的对象。

Stirling numbers of the 2nd kind 正在计算将 n 个球放入 b 非空垃圾箱的次数。

我们可以将其扩展到以下公式以允许空箱

\sum_{e=0}^{b} {b\choose e} S(n,b-e) (b-e)!

在上面的总和中，e代表空箱的数量，所以我们是允许 0 和 b 空箱之间，术语 binomial(b,e) 将占空箱的任何位置，而剩余的 b-e 非空 bins 按 S(n,b-e) 计数，但我们仍然需要考虑我们通过 (b-e)!.

进行的非空容器的所有排列

我们可以使用以下程序来计算：

#!/usr/bin/python3
from sympy import *
from sympy.functions.combinatorial.numbers import stirling

#
# Counting the number of ways to place n balls into b boxes, allowing
# for empty boxes.
#


def count_k_partitions(n,b):
    ans = 0
    for e in range(0,b+1):
        ans += binomial(b,e) * stirling(n,b-e,kind=2) * factorial(b-e)
    return ans

print("c(2,2):",count_k_partitions(2,2))
print("c(3,3):",count_k_partitions(3,3))
print("c(6,7):",count_k_partitions(6,7))

输出：

c(2,2): 4
c(3,3): 27
c(6,7): 117649

另请参阅：

This thread推导出同一个公式
这两个线程讨论了放置球后 e 空箱子的概率 link1 , link2

正在生成对象

这是一个递归算法，可以生成将球放置到箱子中的位置。每个球都放在其中一个容器中，然后算法进一步递归到剩余的球放置下一个球。当没有更多的球可以放置时，我们正在打印所有箱子的内容。

#!/usr/bin/python3
import string
import copy
#
# This generates all the possible placements of
# balls into boxes (configurations with empty boxes are allowed).
#
class BinPartitions:

    def __init__(self, balls, num_bins):
        self.balls = balls
        self.bins = [{} for x in range(num_bins)]

    def print_bins(self, bins):
        L = []
        for b in bins:
            buf = ''.join(sorted(b.keys()))
            L += [buf]
        print(",".join(L))

    def _gen_helper(self,balls,bins):
        if len(balls) == 0:
            self.print_bins(bins)
        else:
            A,B = balls[0],balls[1:]
            for i in range(len(bins)):
                new_bins = copy.deepcopy(bins)
                new_bins[i].update({A:1})
                self._gen_helper(B,new_bins)

    def get_all(self):
        self._gen_helper(self.balls,self.bins)

BinPartitions(string.ascii_uppercase[:3],3).get_all()
#BinPartitions(string.ascii_uppercase[:2],2).get_all()
#BinPartitions(string.ascii_uppercase[:3],3).get_all()
#BinPartitions(string.ascii_uppercase[:6],3).get_all()

输出：

ABC,,
AB,C,
AB,,C
AC,B,
A,BC,
A,B,C
AC,,B
A,C,B
A,,BC
BC,A,
B,AC,
B,A,C
C,AB,
,ABC,
,AB,C
C,A,B
,AC,B
,A,BC
BC,,A
B,C,A
B,,AC
C,B,A
,BC,A
,B,AC
C,,AB
,C,AB
,,ABC

生成对象的其他算法

基于分区的算法： ;

Knuth 算法 U：link1 ; ; link3

此post中使用的所有代码是also available here

在 Python 中枚举标记球和标记箱问题中的所有可能组合

Enumerate all possible combinations in labeled balls and labeled bins problem in Python

python

permutation

subset

combinatorics

python-3.x

计算对象

正在生成对象

生成对象的其他算法