2 nxy006 nxy006 于 2016.01.24 23:26 提问

算法问题:n组对象配对,最终均不配对的结果总数是多少?

详细说明:

有n组已经一一配对的人,现在随机分组,重新一对一分配,求最终每个新分组都与之间不同(每个人配对的新人都与之前不同,不能存在其中某些人的分组没有变化的情况)的可能情况总数。(分组内外部均没有先后次序区别)

我的思路:

第一个人可以有n-1个选择,假设他选择了B,那么原本与B配对的人下一个选择,他有n-1个选择,然后假设他选择了C,原本与C配对的人下一个选择,他有n-2过选择……,最终结果是:(n-1) * (n-1)!


当然,结果是我是错的……

求问:

应该如何计算?我的思路错在哪里?

编程问题,所以程序解决思路也可以,不过我主要想知道数学原理。

8个回答

sssseeeeee
sssseeeeee   2016.01.25 10:53
已采纳

将问题理解成1,2,3...n的错位排列:1,2,3...n重排,k不在第k个位置上。记Si为有i个数在原来位置上的排列,个数为n!/(i!(n_i)!)=n!/i!。#表示乘号。即i个数在原位上,剩下的数全排,剩下的数在不在原位上无所谓,因为容斥原理,错排个数为n!_n!/1!+n!/2!_...+n!/n! (_1)#. #表示乘方

kernel_my
kernel_my   2016.01.24 23:50

关键你的匹配上的人没有减掉!

lm_whales
lm_whales   Rxr 2016.01.24 23:50

首先给出一个序列,滑动配对,就会不同
ABCD
cdab
计算该序列有几种配对方式。

    接着,把其中某些序列顺序打乱
找出不同于滑动序列的新的配对方式
    这些方式就是另外的可以配对的方式。
    把以上加起来求和
91program
91program   Ds   Rxr 2016.01.25 08:32

第一个人可以有n-1个选择,假设他选择了B,那么原本与B配对的人下一个选择,他有n-3个选择(减去第一个人和B,还有不能选自己吧)

nxy006
nxy006 因为这个时候B已经被第一个人选择了,剩下的只有n-1个人可以选,不过我确实没有考虑选到第一个人的配对的情况。这样一来,奇怪的是我的算法应该是忽略了形成小的环路的情况,但结果却是远大于正确结果,我的思路算出来的结果实际上多了……这是为什么呢?
接近 2 年之前 回复
sssseeeeee
sssseeeeee   2016.01.25 10:32

n!(1_1/1!+1/2!_...+(_1)#n/n!)

sssseeeeee
sssseeeeee   2016.01.25 10:33

n!(1_1/!+1/2!_...+(_1)#n/n!)

sssseeeeee
sssseeeeee   2016.01.25 11:01

怎么发图!!!!!!!!!!!图片

John_ToStr
John_ToStr   Rxr 2016.01.25 18:04

计算该序列有几种配对方式。接着,把其中某些序列顺序打乱找出不同于滑动序列的新的配对方式这些方式就是另外的可以配对的方式。把以上加起来求和.

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!