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]); : }
|
|