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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 求救, 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的算法课没教过这个。我中学时是这样解的: : 这是所谓穷举。你这个例子是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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
|
|