c***g
发帖数: 472 | 1 关于排列组合的程序问题, 我一只都没理解太清楚, 现在厚脸皮来请教一下. 这些问题
一般都要涉及到递归, 我这里不是问的算法的问题, 而是程序的实现问题. 我一直不知
道怎么实现才是对的.
比如, 5 选 3 的全组合, a,b,c,d,e.
1 中间结果怎么保存, 是用一个vector来保存,还是用多个vector来保存?
2 如果用一个vector来保存, 递归的时候, 最终状态是什么? 何时pop, 何时push, ?
请问有谁可以贴个code学习一下么?
如果是排列问题, 是不是更麻烦? | g*******y
发帖数: 1930 | 2 排列有几种不同的方法。我喜欢的其中一种方法很直观，不需要保存中间结果。
N数排列:
template void Permutation(T *arr, int N, int count){
if(N<=0) return;
if(count == N){ printAll(arr,N);return;}
for(int i=count;i!=N;i++){
swap(arr[count],arr[i]);
Permutation(arr,N,count+1);
swap(arr[count],arr[i]);
}
}
组合用一个bool chosen[n]保存中间结果
int N; //N numbers
int m; //select m numbers;
int arr[N];
bool chosen[n];
void Combination(int start, int selected){
if(selected == m){ printCombination(arr, chosen); return;}
selected++;
for(int i=start | c***g
发帖数: 472 | 3 恩, 这个在那个programmer interview exposed里面介绍的 吧
请问这里的start到底是个什么角色? 是不是表示当前已经完成的个数?
return;}
【在 g*******y 的大作中提到】
: 排列有几种不同的方法。我喜欢的其中一种方法很直观，不需要保存中间结果。
: N数排列:
: template void Permutation(T *arr, int N, int count){
: if(N<=0) return;
: if(count == N){ printAll(arr,N);return;}
: for(int i=count;i!=N;i++){
: swap(arr[count],arr[i]);
: Permutation(arr,N,count+1);
: swap(arr[count],arr[i]);
: }
| r**u
发帖数: 1567 | 4 扔转。
/* Get all the permutations of a string, e.g. abc.*/
/* Use an int array to indicate if a char of the string
* has been used or not.
* out is the output.
*/
void permute(char *str, int level, char *out, int *used) {
if (!str || !*str) return;
if (level == n) {
printf("%s\n", out);
return;
}
int i = 0;
for (i = 0; i < n; i++) {
if (used[i]) continue;
out[level] = str[i];
out
【在 c***g 的大作中提到】
: 关于排列组合的程序问题, 我一只都没理解太清楚, 现在厚脸皮来请教一下. 这些问题
: 一般都要涉及到递归, 我这里不是问的算法的问题, 而是程序的实现问题. 我一直不知
: 道怎么实现才是对的.
: 比如, 5 选 3 的全组合, a,b,c,d,e.
: 1 中间结果怎么保存, 是用一个vector来保存,还是用多个vector来保存?
: 2 如果用一个vector来保存, 递归的时候, 最终状态是什么? 何时pop, 何时push, ?
: 请问有谁可以贴个code学习一下么?
: 如果是排列问题, 是不是更麻烦?
| g*******y
发帖数: 1930 | 5 这个有点问题，我刚刚在原帖中修改了。
【在 c***g 的大作中提到】
: 恩, 这个在那个programmer interview exposed里面介绍的 吧
: 请问这里的start到底是个什么角色? 是不是表示当前已经完成的个数?
:
: return;}
| a**x
发帖数: 154 | 6 如果直接print就不用考虑vector什么的保存问题， 一个数组就ok了 | a****n
发帖数: 1887 | 7 全排列，我觉得最好的是字典法， 可以处理重复元素
组合， 可以循环 1 ~ 2 ^ N, 然后check bit， print 相应元素
这两种都是非递归的方法， 适用于可以用brutal force的问题
5取3， 还是递归方便一点, 一般直接print, 也可以先压到vector里面去
另外求一个有重复元素的全排列的递归方案 | g*******y
发帖数: 1930 | 8 先sort一下
然后固定相同元素的顺序
比如 a[2]=5; a[3]=5;
那么第一个5就始终必须在全排列中在第二个5前面
参考我前面的全排序的递归程序，可以很容易的做相应修改
在：
for(int i=count;i!=N;i++){
这里，如果有相同的元素，i只取第一个
}
【在 a****n 的大作中提到】
: 全排列，我觉得最好的是字典法， 可以处理重复元素
: 组合， 可以循环 1 ~ 2 ^ N, 然后check bit， print 相应元素
: 这两种都是非递归的方法， 适用于可以用brutal force的问题
: 5取3， 还是递归方便一点, 一般直接print, 也可以先压到vector里面去
: 另外求一个有重复元素的全排列的递归方案
| a****n
发帖数: 1887 | 9 谢谢
【在 g*******y 的大作中提到】
: 先sort一下
: 然后固定相同元素的顺序
: 比如 a[2]=5; a[3]=5;
: 那么第一个5就始终必须在全排列中在第二个5前面
: 参考我前面的全排序的递归程序，可以很容易的做相应修改
: 在：
: for(int i=count;i!=N;i++){
: 这里，如果有相同的元素，i只取第一个
: }
| k***e
发帖数: 556 | 10 knuth的the art of computer programming第四卷第二集吧
此外可以参考stl的next permutation算法
当然了 此算法在knuth的书中有描述
【在 c***g 的大作中提到】
: 关于排列组合的程序问题, 我一只都没理解太清楚, 现在厚脸皮来请教一下. 这些问题
: 一般都要涉及到递归, 我这里不是问的算法的问题, 而是程序的实现问题. 我一直不知
: 道怎么实现才是对的.
: 比如, 5 选 3 的全组合, a,b,c,d,e.
: 1 中间结果怎么保存, 是用一个vector来保存,还是用多个vector来保存?
: 2 如果用一个vector来保存, 递归的时候, 最终状态是什么? 何时pop, 何时push, ?
: 请问有谁可以贴个code学习一下么?
: 如果是排列问题, 是不是更麻烦?
| | | s*****r
发帖数: 773 | 11 请问可以解释一下第一个算法的意思么? 为什么要swap两次, 第二次swap的意思是什么?
【在 g*******y 的大作中提到】
: 排列有几种不同的方法。我喜欢的其中一种方法很直观，不需要保存中间结果。
: N数排列:
: template void Permutation(T *arr, int N, int count){
: if(N<=0) return;
: if(count == N){ printAll(arr,N);return;}
: for(int i=count;i!=N;i++){
: swap(arr[count],arr[i]);
: Permutation(arr,N,count+1);
: swap(arr[count],arr[i]);
: }
| s*****r
发帖数: 773 | 12 为什么有这句话?
out[level+1] = '\0';
如果有这个的输出结果应该是不同长度的全排列吧?
【在 r**u 的大作中提到】
: 扔转。
: /* Get all the permutations of a string, e.g. abc.*/
: /* Use an int array to indicate if a char of the string
: * has been used or not.
: * out is the output.
: */
: void permute(char *str, int level, char *out, int *used) {
: if (!str || !*str) return;
: if (level == n) {
: printf("%s\n", out);
| r**u
发帖数: 1567 | 13 这句只是为了保证out这个string end with '\0'，
如果input = "abc", output是所有length = 3 的排列， if (level == n)才printf。
【在 s*****r 的大作中提到】
: 为什么有这句话?
: out[level+1] = '\0';
: 如果有这个的输出结果应该是不同长度的全排列吧?
| b****j
发帖数: 78 | 14 恢复原来的状态
么?
【在 s*****r 的大作中提到】
: 请问可以解释一下第一个算法的意思么? 为什么要swap两次, 第二次swap的意思是什么?
| y****w
发帖数: 3747 | 15 不用大师的，如果本科时候真的下苦工彻底研究过严蔚敏的习题集，这种算法的考察早
就被囊括的八九不离十了，
【在 k***e 的大作中提到】
: knuth的the art of computer programming第四卷第二集吧
: 此外可以参考stl的next permutation算法
: 当然了 此算法在knuth的书中有描述
| r**u
发帖数: 1567 | 16 如果要求非递归找所有的permutation，怎么弄
【在 c***g 的大作中提到】
: 关于排列组合的程序问题, 我一只都没理解太清楚, 现在厚脸皮来请教一下. 这些问题
: 一般都要涉及到递归, 我这里不是问的算法的问题, 而是程序的实现问题. 我一直不知
: 道怎么实现才是对的.
: 比如, 5 选 3 的全组合, a,b,c,d,e.
: 1 中间结果怎么保存, 是用一个vector来保存,还是用多个vector来保存?
: 2 如果用一个vector来保存, 递归的时候, 最终状态是什么? 何时pop, 何时push, ?
: 请问有谁可以贴个code学习一下么?
: 如果是排列问题, 是不是更麻烦?
| b****j
发帖数: 78 | 17 STL里的next_permutation，源码在algorithm的header里。
【在 r**u 的大作中提到】
: 如果要求非递归找所有的permutation，怎么弄
| m*****f
发帖数: 1243 | 18 5个数， 选择与否可以用0, 1 来表示
那么题目转化成 0 - 11111 这些自然数里面， 所有bit有三个1得数
很简单的一个循环
【在 r**u 的大作中提到】
: 如果要求非递归找所有的permutation，怎么弄
| a****n
发帖数: 1887 | 19 这个是combination
【在 m*****f 的大作中提到】
: 5个数， 选择与否可以用0, 1 来表示
: 那么题目转化成 0 - 11111 这些自然数里面， 所有bit有三个1得数
: 很简单的一个循环
| m*****f
发帖数: 1243 | 20 hmm...原题不就是问的组合?
【在 a****n 的大作中提到】
: 这个是combination
| a****n
发帖数: 1887 | | H*M
发帖数: 1268 | 22 。。。
没看懂。谁给个brief idea和brief注释?
【在 g*******y 的大作中提到】
: 排列有几种不同的方法。我喜欢的其中一种方法很直观，不需要保存中间结果。
: N数排列:
: template void Permutation(T *arr, int N, int count){
: if(N<=0) return;
: if(count == N){ printAll(arr,N);return;}
: for(int i=count;i!=N;i++){
: swap(arr[count],arr[i]);
: Permutation(arr,N,count+1);
: swap(arr[count],arr[i]);
: }
|
|
