x***y
发帖数: 633 | 1 有k个标上序号为0，1，。。。k-1的球， 拿其中的任意n个(1<=n<=k)进行组合, 一共有2
^k-1 种组合。 把这些组合按以下规则排列：
1. 组合中球的数目小的排在前面 （比如， （0，1）的组合就排在（0，1，2)的前面）
2. 对于球的数目相同的组合， 比较两个组合中序号最小的球， 小的那个组合排在前
面 （比如 组合（0，1，2）就排在（1，2，3）的前面， 因为第一个组合的最小值0
小于 第二个组合中的最小值1）
问题是对于任意 整数值 m ( 1<=m<=2^k-1), 如何知道 第 m个组合包括的球的序号是
多少？
哪位知道算法可以说一下吗？ 我会发包子的。。。。 | g*****y
发帖数: 7271 | 2 m is a k-bit binary number : e.g. 01100... Each possible value indicate
one way of selection.
You could say that each "1" bit indicates the corresponding ball to be
selected. Then, by looking at all "1" bits, you know the smallest index of
the balls selected, right?
共有2
面）
【在 x***y 的大作中提到】
: 有k个标上序号为0，1，。。。k-1的球， 拿其中的任意n个(1<=n<=k)进行组合, 一共有2
: ^k-1 种组合。 把这些组合按以下规则排列：
: 1. 组合中球的数目小的排在前面 （比如， （0，1）的组合就排在（0，1，2)的前面）
: 2. 对于球的数目相同的组合， 比较两个组合中序号最小的球， 小的那个组合排在前
: 面 （比如 组合（0，1，2）就排在（1，2，3）的前面， 因为第一个组合的最小值0
: 小于 第二个组合中的最小值1）
: 问题是对于任意 整数值 m ( 1<=m<=2^k-1), 如何知道 第 m个组合包括的球的序号是
: 多少？
: 哪位知道算法可以说一下吗？ 我会发包子的。。。。
| X****r
发帖数: 3557 | 3 给定m，先找到n：因为在k个球里取n个的组合有C(k,n)种，让n从1到k循环不断从m里减去
C(k,n)直到不能减（差将为零或负）为止，就找到了n，称m剩下的正数为m'。
然后找这n个数中最小的一个：让x1从1到k-n循环不断从m'里减去C(k-x1,n-1)直到不能
减为止就找到了第一个数x1；找第二小的数：让x2从x1+1到k-n+1循环不断减去
C(k-x1-x2,n-2)；依次类推直到找到最后一个数。
如果认为整数加减乘除都是常数时间的话以上算法时间复杂度O(k^2)，不然的话为O(k^
3)。
共有2
面）
【在 x***y 的大作中提到】
: 有k个标上序号为0，1，。。。k-1的球， 拿其中的任意n个(1<=n<=k)进行组合, 一共有2
: ^k-1 种组合。 把这些组合按以下规则排列：
: 1. 组合中球的数目小的排在前面 （比如， （0，1）的组合就排在（0，1，2)的前面）
: 2. 对于球的数目相同的组合， 比较两个组合中序号最小的球， 小的那个组合排在前
: 面 （比如 组合（0，1，2）就排在（1，2，3）的前面， 因为第一个组合的最小值0
: 小于 第二个组合中的最小值1）
: 问题是对于任意 整数值 m ( 1<=m<=2^k-1), 如何知道 第 m个组合包括的球的序号是
: 多少？
: 哪位知道算法可以说一下吗？ 我会发包子的。。。。
| X****r
发帖数: 3557 | 4 查了一下，这个的方法更巧妙一些：
http://msdn.microsoft.com/en-us/library/aa289166(VS.71).aspx
不过好像渐进时间复杂度还是一样的。
减去
k^
【在 X****r 的大作中提到】
: 给定m，先找到n：因为在k个球里取n个的组合有C(k,n)种，让n从1到k循环不断从m里减去
: C(k,n)直到不能减（差将为零或负）为止，就找到了n，称m剩下的正数为m'。
: 然后找这n个数中最小的一个：让x1从1到k-n循环不断从m'里减去C(k-x1,n-1)直到不能
: 减为止就找到了第一个数x1；找第二小的数：让x2从x1+1到k-n+1循环不断减去
: C(k-x1-x2,n-2)；依次类推直到找到最后一个数。
: 如果认为整数加减乘除都是常数时间的话以上算法时间复杂度O(k^2)，不然的话为O(k^
: 3)。
:
: 共有2
: 面）
| x***y
发帖数: 633 | | a**********s
发帖数: 588 | 6 稍微改进(或者说整理)一下, 先用Xentar的方法找到N, 这个是o(k), 归结为在K个球里
面取N个球的第m'种情况
然后看最高位的球B(k-1)该不该拿, 这个需要考虑剩下的k-1个球拿N个球的可能性有没
有超过m', 如果超过了, 那么B(k-1)不该拿, 否则就该拿, and let m' <-- m' - C(k-
1, N); N--; 依次类推...
从k-1到k-2这一步, 需要计算C(k-2, N)或者C(k-2, N-1), 这些都是可以从前面的计算
结果中用常数时间得出
这样的话, 总的时间是O(k)的. | g*******y
发帖数: 1930 | 7 指出两个小失误:
m' = m' - C(k-1,N-1) not m' - C(k-1,N)
还有就是复杂度，在K个球里取N个球的第m'中情况，由于每次操作k都能减1，所以最多
是O(k)次。但是，因为你要事先算出 C(1,1)...C(k,k)的matrix，所以总复杂度还是 O
(k^2)
k-
这里是
【在 a**********s 的大作中提到】
: 稍微改进(或者说整理)一下, 先用Xentar的方法找到N, 这个是o(k), 归结为在K个球里
: 面取N个球的第m'种情况
: 然后看最高位的球B(k-1)该不该拿, 这个需要考虑剩下的k-1个球拿N个球的可能性有没
: 有超过m', 如果超过了, 那么B(k-1)不该拿, 否则就该拿, and let m' <-- m' - C(k-
: 1, N); N--; 依次类推...
: 从k-1到k-2这一步, 需要计算C(k-2, N)或者C(k-2, N-1), 这些都是可以从前面的计算
: 结果中用常数时间得出
: 这样的话, 总的时间是O(k)的.
| a**********s
发帖数: 588 | 8
这里你要再想想...减去C(k-1,N), m'的前面C(k-1,N)都是最高位的球不拿的情况
O
这里为什么需要算整个matrix?
【在 g*******y 的大作中提到】
: 指出两个小失误:
: m' = m' - C(k-1,N-1) not m' - C(k-1,N)
: 还有就是复杂度，在K个球里取N个球的第m'中情况，由于每次操作k都能减1，所以最多
: 是O(k)次。但是，因为你要事先算出 C(1,1)...C(k,k)的matrix，所以总复杂度还是 O
: (k^2)
:
: k-
: 这里是
| g*******y
发帖数: 1930 | 9 {0 1 2...k-1} 选N，两种情况
情况一：0 + {1..k-1}选N-1 C(k-1, N-1)
情况二：{1..k-1}选N C(k-1,N)
所有第一种情况的编号，要小于所有第二种情况的编号 (估计algorithmics就是这里有
个小疏忽吧)
所以，m'如果是大于 C(k-1, N-1)的话，就是第二种情况了，m'就要减去C(k-1,N-1)
【在 a**********s 的大作中提到】
:
: 这里你要再想想...减去C(k-1,N), m'的前面C(k-1,N)都是最高位的球不拿的情况
: O
: 这里为什么需要算整个matrix?
| a**********s
发帖数: 588 | 10 嗯，是我弄反了
【在 g*******y 的大作中提到】
: {0 1 2...k-1} 选N，两种情况
: 情况一：0 + {1..k-1}选N-1 C(k-1, N-1)
: 情况二：{1..k-1}选N C(k-1,N)
: 所有第一种情况的编号，要小于所有第二种情况的编号 (估计algorithmics就是这里有
: 个小疏忽吧)
: 所以，m'如果是大于 C(k-1, N-1)的话，就是第二种情况了，m'就要减去C(k-1,N-1)
| g*******y
发帖数: 1930 | 11 关于复杂度的评论，是我没有想清楚。O(k)是正确的。
【在 a**********s 的大作中提到】
: 嗯，是我弄反了
|
|
