i*****e
发帖数: 218 | 1 求救， F家onsite算法题
到F家onsite, 被问了这个题， 我不会， 请大家帮忙吧。
这是一个组合问题的算法题。
给一个自然数集，比如：1, 2, 3, 4, ...., 100.
又任给一个自然数， n, (n是一个变量），举例来说， n = 3,
找出这个自然数集中选出n个数的全部组合， 把它们打印出来。
举例来说， n = 3, 打印出：
1， 2， 3
1， 2， 4，
1， 2， 5
2, 3, 4
2, 3, 5
97, 98, 99
98, 99, 100
我知道总的组合数是： 100！/n!
我不知道怎么把这些组合都打印出来。
(打印的顺序可以自己定， 关键是把这些所有的组合都打印出来.
他们的要求是针对任何一个n < 100, 比如 n = 49, 打印出所有的组合).
多谢大家。
（当时还问了一个问题是， 如果用python 或 javascript 怎么实现它）。 | a**********t
发帖数: 631 | 2 FB还出这么简单的题？这是最基本的combination，随便找本算法书都能找到。最简单
的办法就是用recursion. | n**********5
发帖数: 1707 | 3 我的算法课没教过这个。我中学时是这样解的：
这是所谓穷举。你这个例子是n位100进制数。
开一个n数字的数组，初始值为最小数（1）。
while (true)
{
判断此组合是否合法，如合法则输出：如1,1,1不合法则不输出
最低位+1
从最低位向最高位循环，如>最大值则此位reset为最低值，高一位+1。如无更高位则程
序结束
}
视合法的条件，+1运算哪里可以优化
【在 i*****e 的大作中提到】
: 求救， F家onsite算法题
: 到F家onsite, 被问了这个题， 我不会， 请大家帮忙吧。
: 这是一个组合问题的算法题。
: 给一个自然数集，比如：1, 2, 3, 4, ...., 100.
: 又任给一个自然数， n, (n是一个变量），举例来说， n = 3,
: 找出这个自然数集中选出n个数的全部组合， 把它们打印出来。
: 举例来说， n = 3, 打印出：
: 1， 2， 3
: 1， 2， 4，
: 1， 2， 5
| i*****e
发帖数: 218 | 4 Thank you.
你的这个算法挺有意思。 但需要判断， 1， 2， 4 和 4， 2， 1； 和 2， 4， 1
是同一个组合， 这个工作量不小吧 ？
另外， 初始值应该设为：1, 2, 3 (举例来说， 对于3 位数）。
> 这是所谓穷举。你这个例子是n位100进制数。
> 开一个n数字的数组，初始值为最小数（1）。
> while (true)
> {
> 判断此组合是否合法，如合法则输出：如1,1,1不合法则不输出
> 最低位+1
> 从最低位向最高位循环，如>最大值则此位reset为最低值，高一位+1。如无更高位则程
> 序结束
> }
【在 n**********5 的大作中提到】
: 我的算法课没教过这个。我中学时是这样解的：
: 这是所谓穷举。你这个例子是n位100进制数。
: 开一个n数字的数组，初始值为最小数（1）。
: while (true)
: {
: 判断此组合是否合法，如合法则输出：如1,1,1不合法则不输出
: 最低位+1
: 从最低位向最高位循环，如>最大值则此位reset为最低值，高一位+1。如无更高位则程
: 序结束
: }
| n**********5
发帖数: 1707 | 5 我没修过你们的算法课。所以我的算法可能看起来很怪。
组合本质上就是计数。不过因为这是一个很大的整数，否则直接＋1然后取模也是可以
的。
如果不重复，只要保证数组是降序就行了。这样＋1的时候可以优化（直接跳过不可能
的组合）。
这是一切穷举的基础。其它的如任意N个加起来等于M的组合等等。
给你1-100你可以视为下标。问题还可以转变为100个字符求所有可能的组合等等。
有了这个基础，还有其它可能的优化如剪枝（＋1的时候直接跳过不可能的组合）。
【在 i*****e 的大作中提到】
: Thank you.
: 你的这个算法挺有意思。 但需要判断， 1， 2， 4 和 4， 2， 1； 和 2， 4， 1
: 是同一个组合， 这个工作量不小吧 ？
: 另外， 初始值应该设为：1, 2, 3 (举例来说， 对于3 位数）。
: > 这是所谓穷举。你这个例子是n位100进制数。
: > 开一个n数字的数组，初始值为最小数（1）。
: > while (true)
: > {
: > 判断此组合是否合法，如合法则输出：如1,1,1不合法则不输出
: > 最低位+1
|
|
