新手问题 排列组合

bluexuemei · 2014年05月06日 · 最后由 bluexuemei 回复于 2014年05月06日 · 3023 次阅读

m 取 n 排列组合在不预先生成全部列表的情况下,按大小顺序如何快速取得某个索引号对应的字符串或某个字符串对应的索引号? 如: 49 选 6 一共 13983816 个组合,如何取得第 1000000 个组合是什么?或 “24 29 33 37 40 45” 排第几?

大哥,你是来求作业的吗? 哈哈

#1 楼 @skandhas 觉得这个问题比较有趣却又有点棘手,所以和大家分享一下,有兴趣的大神可以试一试。

#3 楼 @blacktulip 非也,本人从不玩彩票,从别处看到的题目,觉得有趣,就贴出来,大家一起玩玩!

楼主说的排列组合是不是这种?C(3,2) =3 且排序是 1,2,13, 23 ?? 如果是这种,下面的有可能(10%...)是对的(纯粹无聊,抛砖引玉,坐等答案!)。。。

nth = 1000 i = 1 C(n,r) = C(n-1,r-1) + C(n-1,r) 两种情况 C(n-1,r-1) > 1000 (1) C(n-1,r-1) > 1000 (2)

情况(1) nth = nth - C(n-1,r-1) n = n - 1 r = r -1

情况(2)nth - C(n-1,r-1) nth = nth n = n-1 r = r -1 这个时候记录下 i。

nth = 0 的时候停止,把记录的所有 i 搞出来,应该就是解(1 成的把握是正确的吧。。。sorry)。

解释下公式,如果我没记错的话 C(n,r) = C(n-1,r-1) + C(n-1,r) ---- () () 的右半部分是考虑两种可能,取第 n 个 + 和不取第 n 个。 n 个可以理解为第 n 个球,而我是倒着给球编号的。

解释下思路 有两种可能,第 nth(1000),他取得 i 和不取得 i 如果 nth 小于 C(n-1,r-1), 则意味着要取 i,那么记录 i,更改 nth,n,r,做递归 如果 nth 大于 C(n-1,r-1),以为着不取 i。 nth = nth - C(n-1,r-1)(所有去 i 的可能的情况)。做递归。

#6 楼 @yfractal 你的理解是对的,求代码

需要 登录 后方可回复, 如果你还没有账号请 注册新账号