枚举Python中带标签的球和带标签的垃圾箱问题中的所有可能组合 [英] Enumerate all possible combinations in labeled balls and labeled bins problem in Python

问题描述

我正在寻找一种Python方式，可以将"标记的球放入标记的容器"中的所有可能选项进行枚举.问题.例如，给定2个标记的球和2个标记的垃圾箱，我想得到:

(A，B)

(AB，)

(，AB)

(B，A)

即(2 ^ 2)4个选项.如果我们给3个球和3个垃圾箱，则有27种可能性3 ^ 3.例如:

(A，B，C)(ABC，，)(，，ABC)(AB，C，)(出租车)(，BC，A)等等...

我正在考虑将解决方案(AB，)和(BA，)视为同一项目.

解决方案

计数对象

这些对象在许多地方也称为k分区.

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

在上面的总和中， e 表示空箱的数量，因此我们允许在 0 和 b 空箱之间，术语 binomial(b，e)将占空箱的任何位置，而其余的 b-e 非空垃圾箱通过 S(n，b-e)进行计数，但我们仍然需要考虑我们通过(b-e)！执行的非空bin的所有排列！

我们可以使用以下程序对此进行计数:

 <代码>#！/usr/bin/python3从sympy导入*来自sympy.functions.combinatorial.numbers进口斯特林##计算将n个球放入b盒的方法数量，允许#用于空盒子.#def count_k_partitions(n，b):ANS = 0对于范围(0，b + 1)中的e:ans + =二项式(b，e)*斯特林(n，b-e，种类= 2)*阶乘(b-e)返回ansprint("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):4c(3,3):27c(6,7):117649 

另请参阅:

• 此线程得出相同的公式

• 这两个线程讨论了放置球后 e 空箱的可能性link1 ， link2

生成对象

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

 <代码>#！/usr/bin/python3导入字符串导入副本##这会生成的所有可能的展示位置将#个球装入盒子(允许使用空盒子进行配置).#类BinPartitions:def __init __(自我，球，num_bins):self.balls =球self.bins = [{} for x in range(num_bins)]def print_bins(self，bins):L = []对于垃圾箱中的b:buf =''.join(sorted(b.keys()))L + = [buf]print(，".join(L))def _gen_helper(自我，球，垃圾桶):如果len(balls)== 0:self.print_bins(箱)别的:A，B =球[0]，球[1:]对于我在范围内(len(bins)):new_bins = copy.deepcopy(bins)new_bins [i] .update({A:1})self._gen_helper(B，new_bins)def get_all():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，CAC，B，A，BC，A，B，CAC，BA，C，BA，BCBC，A，B，AC，B，A，C出租车，，ABC，，AB，C出租车，AC，B，A，BC公元前B，C，A交流C，B，A，BC，A，B，AC出租车，出租车,, ABC 

其他用于生成对象的算法

基于分区的算法: link1 ； link2

Knuth的算法U: link1 ； link2 ； link3

本文中使用的所有代码均为在此处也可用

I'm looking for a Pythonic way of enumerating all possible options for the "labeled balls into labeled bins" problem. For example, given 2 labeled balls and 2 labeled bins I would like to get:

(A, B)

(AB, )

( ,AB)

(B, A)

That is (2^2) 4 options. In case we give 3 balls and 3 bins, there are 27 possibilities 3^3. For example:

(A, B, C) (ABC, , ) ( , , ABC) (AB, C , ) (C, , AB) ( ,BC, A) and so on...

I'm considering the solution (AB, ) and (BA, ) the same item.

解决方案

Counting the objects

These objects are also called k-partitions in many places.

We could count them at first, and then use the counting methods to test if we're generating the right amount of objects.

The Stirling numbers of the 2nd kind are counting the number of placements of n balls into b non-empty bins.

We can extend that to the following formula to allow for empty bins

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

In the sum above, e represents the number of empty bins, so we're allowing between 0 and b empty bins, the term binomial(b,e) will account for any position of the empty bins, while the remaining b-e non-empty bins are counted by S(n,b-e), but we still need to allow for all permutations of the non-empty bins which we're doing through (b-e)!.

We can count this using the following program:

#!/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))

OUTPUT:

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

See also:

• This thread derives the same formula

• These two threads discuss the probability of having e empty bins after placing the balls link1 , link2

Generating the objects

Here is a recursive algorithm that generates the placements of balls into bins. Each ball is placed in one of the bins, then the algorithm recurses further into the remaining balls to place the next ball. When there are no more balls to place, we're printing the contents of all bins.

#!/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()

OUTPUT:

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

Other algorithms for generating the objects

Partition-based algorithms: link1 ; link2

Knuth's Algorithm U: link1 ; link2 ; link3

All the code used in this post is also available here

这篇关于枚举Python中带标签的球和带标签的垃圾箱问题中的所有可能组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！