同学聚会

mathe · 发表于 2010-1-29 15:10:13

我的程序中x1代表一张桌子上出现的男同学和配偶同时出现的对数，y1代表女同学和配偶同时出现的对数。
x2代表某个男同学出现但是配偶不出现的数目，y2代表某个女同学出现但是配偶不出现的数目
x3代表某个男同学不出现但是配偶出现的数目，y3代表某个女同学不出现但是配偶出现的数目
显然对于一张桌子的条件是
${: (2*x1+x2+x3+2y1+y2+y3=10),(x1+x2+x3<=12),(y1+y2+y3<=8) :}$
然后程序中对于每个满足条件的方案，先制定每个人的编号，计算不同座位方案。

mathe · 发表于 2010-1-29 15:31:23

根据4张桌子完全不同的模式共有17202625个
对所有模式求和，所以如果完全不区分不同的桌子，而且只管每桌所坐人的性别以及它们是否具有配偶关系
我们已经可以得到解的数目为2677936124596800975372288
如果继续区分不同的人，那么结果还会更多，我们需要对每个模式求不同的人落座不同位置的排列组合数目。

sr2.tgz (1.46 KB, 下载次数: 2)

mathe · 发表于 2010-1-29 15:41:11

下一步，我们还需要对于每个模式，计算分配不同人到不同桌子的组合数目。
首先对于所有桌的x1,y1进行分配，这个方案很简单，为${12!}/{x11!x12!x13!x14!}{8!}/{y11!y12!y13!y14!}$
但是接下去对x2,x3,y2,y3进行分配的时候好像比较麻烦，这个好像还需要进行搜索。
由于总体模式数目比较多，直接进行搜索复杂度稍微有点大。

northwolves · 发表于 2010-1-29 20:37:37

我的想法基本与 mathe 一致,但到第一步就卡了.先努力研究研究mathe 的代码

mathe · 发表于 2010-1-30 09:39:04

22#数据实际意义还是不大。
不过如果完全区分每个人，现在计数总数目问题应该不大，只是有可能计算事件稍微有点长。
但是如果不区分不同的人（除非性别不同或者是主人和客人的区别），计数还是很有难度的。

mathe · 发表于 2010-1-30 11:28:23

为了解决不区分人的方案数目。我们定义下面两个4*4模式矩阵A和B,其中$A_{ij}$表示男同学坐在第i桌而且其配偶坐在第j桌的数目；$B_{ij}$表示女同学坐在第i桌而且其配偶坐在第j桌的数目。
谁先来穷举一下，满足条件的这样的模式矩阵对的数目。

mathe · 发表于 2010-2-3 09:52:01

满足26#的模式对我计算出来总共是
17501334348
种。其中不考虑置换不同桌子会出现等价情况。
如果考虑到不同桌子的置换情况，结果会更加少一些。
不过即使这个规模，已经不算大了。
接下去我们只需要对每个模式进行计数（这个只要结合上面已经得到的给定每桌的人员分布后的计数就可以了）。

pme.tgz (822 Bytes, 下载次数: 0)

mathe · 发表于 2010-2-3 10:07:17

现在如果要计算区分所有人的情况（但是不区分桌子和而且对于每张桌子只考虑相对位置），已经很简单了。
对于上面17501334348中模式，每种模式的人员组合分布可以很容易计算出来，就是
${12!}/{\prod A_{ij}!}{8!}/{\prod B_{ij}!}$,而对于每个模式给定人员组合分布以后，就可以查询前面每张桌子计算结果的表格（才700多个元素）。把上面组合数和4张桌子的查询结果都相乘，然后对所有模式的结果再累加。但是这个是区分桌子的结果，最后的结果再除以24就可以得到不区分桌子的结果。
但是如果要计算不区分人员的结果。那么我们需要对上面17501334348个模式在进行等价关系处理。而且对于每个模式，需要计算出有那些桌子还是处于对称状态。
但是现在对于每张桌子上的座位情况，我们还需要再次预处理，因为这时有些人可能会处于对称状态。这里还会有些复杂，需要通过排列组合来处理

northwolves · 发表于 2010-2-5 22:19:30

前些天同学聚会时想到的问题，没想到比我预想的还复杂。mathe 辛苦了！！！

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 同学聚会

评分