大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
组合
1.位计算来实现所需的组合:
。即。将每一个组合与一个二进制数相应起来。枚举二进制的同一时候,枚举每一个组合。如字符串:abcde,则有
00000———null
00001———a
00010 ——–b
00011———ab
00100———c
… …
11111——–abcde
给出程序例如以下所看到的:
#include <stdio.h> #include <string.h> void printCombination(char* str, int i); void combination(char* str) { int len = strlen(str); //共同拥有(1<<len)个组合,当中有一次什么都不打印外 for(int i=0; i< (1<<len); ++i) { printCombination(str, i); printf("\n"); } } void printCombination(char* str, int i) { int len = strlen(str); for(int j=0; j<len; ++j) { //看s中哪些位为 int s = i&(1<<j); if(s) printf("%c", str[j]); } } int main() { char str[] = "abc"; combination(str); }
2.递归的思路解决
#include <stdio.h> #include <string.h> void printCombination(char* str, int len, int m, int* arr, const int M); void combination(char* str) { int len = strlen(str); int* arr = new int[len]; for(int i=1; i<=len; ++i) { printCombination(str, len, i, arr, i); } delete[] arr; } //从n中选m个数进行组合 /************************************** a. 首先从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数, 直到从n-(m-1)个数中选取个数为止。 b. 从n个数中选取编号次小的一个数,继续运行步。直到当前可选编号最大的数为m。 ******************************************/ void printCombination(char* str, int len, int m, int* arr, const int M) { for(int i=len; i>=m;--i) { //依次选择编号最大的数,次大的数.... arr[m-1] = i-1; if(m>1) { //选择的数目大于。从剩余的i-1个数中选取m-1个数的组合 printCombination(str,i-1,m-1,arr,M); } else { //打印M个数字 for(int j=M-1; j>=0; --j) { printf("%c ", str[arr[j]]); } printf("\n"); } } } int main() { char str[] = "abcd"; combination(str); return 0; }
3.非递归实现
首先,初始化一个n个元素的数组(所有由0。1组成),将前m个初始化为1。后面的为0。这时候就能够输出第一个组合了。
为1的元素的下标所相应的数。
算法開始:从前往后找,找到第一个10组合,将其反转成01。然后将其前面的所有1,所有往左边推。即保证其前面的1都在最左边。然后就能够依照这个01序列来输出一个组合结果了。
而假设找不到10组合。就表示说全部情况都输出了,为什么?你想,(以n=5,m=3为例)一開始是11100,最后就是00111。已经没有10组合了。
这样的将问题转换为01序列(也就是真假序列)的想法值得我们考虑和借鉴。
比如求5中选3的组合:
1 1 1 0 0 //1,2,3
1 1 0 1 0 //1,2,4
1 0 1 1 0 //1,3,4
0 1 1 1 0 //2,3,4
1 1 0 0 1 //1,2,5
1 0 1 0 1 //1,3,5
0 1 1 0 1 //2,3,5
1 0 0 1 1 //1,4,5
0 1 0 1 1 //2,4,5
0 0 1 1 1 //3,4,5
实现代码例如以下:
#include <stdio.h> #include <stdlib.h> #include <string.h> int l=0; //function definition void composition(const char [],int,int); void printCompostion(const char[],const bool[],int); //function implementation void printCompostion(const char source[],const bool comp[],int n){ int i; for (i=0;i<n;i++) if (comp[i]==true) printf ("%c-",source[i]); printf ("\n"); } void compostion(const char* source,int n,int m){ bool * comp = (bool*)malloc(n*sizeof(bool)); int i; for (i=0;i<m;i++) comp[i]=true; for (i=m;i<n;i++) comp[i]=false; printCompostion(source,comp,n); l++; while(true){ for (i=0;i<n-1;i++) if (comp[i]==true&&comp[i+1]==false) break; if (i==n-1) return; //all the compostion is found out comp[i]=false; comp[i+1]=true; int p=0; while (p<i){ while (comp[p]==true) p++; while (comp[i]==false) i--; if (p<i) { comp[p]=true; comp[i]=false; } } printCompostion(source,comp,n); l++; } } //test function void testCompostion(){ char* testcase = "abcdefghijklmno"; int n=strlen(testcase); int m=7; compostion(testcase,n,m); } //main function void main(){ testCompostion(); printf ("total=%d\n",l); }
全排列:
1. 递归
分治算法:这个算法利用了分而治之的思想。
我们先从2个数開始,比方说4,5。他们的全排列仅仅有两个45和54。假设在前面加个3,那么全排列就是345,354,也就是3(54),括号表示里面的数的全排列。当然还有4(35),5(34)…写到这里,各位看官应该已经看出点门道了吧。
三个数的全排列,能够分为三次计算。第一次计算3和(45)的全排列。第二次计算4和(35)的全排列…..也就是说,将序列第一个元素分别与它以及其后的每个元素代换,得到三个序列,然后对这些序列的除首元素外的子序列进行全排列。
思想事实上还是挺简单的:
代码实现例如以下:
#include <stdio.h> #include <string.h> #include <stdlib.h> #define LENGTH 27 int n=0; void permute(int[],int,int); void swapint(int &a,int &b); void printIntArray (int[],int); //Function Implementation void swapint(int &a,int &b){ int temp; temp = a; a = b; b = temp; } void printIntArray(int target[],int length){ int i; for (i=0;i<length;i++) printf ("%d",target[i]); printf ("\n"); } void permute(int target[],int begin,int end){ if (begin==end) { printIntArray(target,end+1); n++; return; } int i; for (i=begin;i<=end;i++){ swapint(target[begin],target[i]); permute(target,begin+1,end); swapint(target[begin],target[i]); } } //test Functions void testPermute(){ int len; scanf ("%d",&len); int *testcase =(int *)malloc(len*sizeof(int)); int i; for (i=0;i<len;i++) testcase[i]=i+1; permute(testcase,0,len-1); } //Main Function void main(){ testPermute(); printf ("n=%d",n); }
2. 字典序
有时候递归的效率使得我们不得不考虑除此之外的其它实现,非常多把递归算法转换到非递归形式的算法是比較难的,这个时候我们不要忘记了标准模板库已经实现的那些算法。这让我们非常轻松。STL有一个函数next_permutation(),它的作用是假设对于一个序列。存在依照字典排序后这个排列的下一个排列,那么就返回true且产生这个排列。否则返回false。注意,为了产生全排列,这个序列要是有序的,也就是说要调用一次sort。
直接用STL上的
#include "iostream" #include "algorithm" using namespace std; void permutation(char* str,int length) { sort(str,str+length); //必须得先排序 do { for(int i=0;i<length;i++) cout<<str[i]; cout<<endl; }while(next_permutation(str,str+length)); } int main(void) { char str[] = "acb"; cout<<str<<"全部全排列的结果为:"<<endl; permutation(str,3); system("pause"); return 0; }
当中next_permutation()的实现例如以下:
template<class BidirectionlIterator> bool next_permutation(BidirectionalIterator firt, BidirectionalIterator last) { if(first == last) return false; //空区间 BidirectionalIterator i = first; ++i; if(i == last) return false; //仅仅有一个元素 i = last; //i指向尾端 --i; for(;;){ BidrectionalIterator ii = i; --i; //以上,锁定一组(两个)相邻元素 if(*i < *ii) //假设前一个元素小于后一个元素 { BidrectionalIterator j = last; //令j指向尾端 while(!(*i < *--j)); //由尾端往前找,直到遇上比*i大的元素 iter_swap(i,j); //交换i,j reverse(ii, last); //将ii之后的元素所有逆向重排 return true; } if(i == first) //进行到最前面了 { reverse(first, last); //所有逆向重置 return false; } } }
自己设计函数next_permutation():
#include <stdio.h> #include <algorithm> #include <string.h> using namespace std; //反转数组 void reverse(char* str, int first, int last) { if(str == NULL || *str == '#include <stdio.h> #include <algorithm> #include <string.h> using namespace std; //反转数组 void reverse(char* str, int first, int last) { if(str == NULL || *str == '\0') return; while(first < last) { char ch = str[first]; str[first] = str[last]; str[last] = ch; first++; last--; } } //打印数组 void printfString(char* str) { for(int i=0; i<strlen(str); ++i) { printf("%c", str[i]); } printf("\n"); } //找到下一个数组 bool next_permutation(char* str) { if(str == NULL || *str=='\0') return false; int len = strlen(str); int i = len - 2; int ii = i+1; int j = len - 1; //从后端開始找到第一对str[i]<str[j]的数字 while(str[i] > str[ii]) { --i; --ii; //假设i<0,则表示已经所有排列 if(i<0) { //所有翻转 reverse(str, i+1, len-1); return false; } } //从后面找到第一个大于str[i]的数字 while(str[j] < str[i]) { --j; } //交换 char ch = str[i]; str[i] = str[j]; str[j] = ch; //翻转j之后的数组 reverse(str, ii, len-1); return true; } int main() { char str[] = "cab"; int len = strlen(str); //必须先排序 sort(str, str + len); printfString(str); //打印全排列 while(next_permutation(str)) { printfString(str); } return 0; }') return; while(first < last) { char ch = str[first]; str[first] = str[last]; str[last] = ch; first++; last--; } } //打印数组 void printfString(char* str) { for(int i=0; i<strlen(str); ++i) { printf("%c", str[i]); } printf("\n"); } //找到下一个数组 bool next_permutation(char* str) { if(str == NULL || *str=='#include <stdio.h> #include <algorithm> #include <string.h> using namespace std; //反转数组 void reverse(char* str, int first, int last) { if(str == NULL || *str == '\0') return; while(first < last) { char ch = str[first]; str[first] = str[last]; str[last] = ch; first++; last--; } } //打印数组 void printfString(char* str) { for(int i=0; i<strlen(str); ++i) { printf("%c", str[i]); } printf("\n"); } //找到下一个数组 bool next_permutation(char* str) { if(str == NULL || *str=='\0') return false; int len = strlen(str); int i = len - 2; int ii = i+1; int j = len - 1; //从后端開始找到第一对str[i]<str[j]的数字 while(str[i] > str[ii]) { --i; --ii; //假设i<0,则表示已经所有排列 if(i<0) { //所有翻转 reverse(str, i+1, len-1); return false; } } //从后面找到第一个大于str[i]的数字 while(str[j] < str[i]) { --j; } //交换 char ch = str[i]; str[i] = str[j]; str[j] = ch; //翻转j之后的数组 reverse(str, ii, len-1); return true; } int main() { char str[] = "cab"; int len = strlen(str); //必须先排序 sort(str, str + len); printfString(str); //打印全排列 while(next_permutation(str)) { printfString(str); } return 0; }') return false; int len = strlen(str); int i = len - 2; int ii = i+1; int j = len - 1; //从后端開始找到第一对str[i]<str[j]的数字 while(str[i] > str[ii]) { --i; --ii; //假设i<0,则表示已经所有排列 if(i<0) { //所有翻转 reverse(str, i+1, len-1); return false; } } //从后面找到第一个大于str[i]的数字 while(str[j] < str[i]) { --j; } //交换 char ch = str[i]; str[i] = str[j]; str[j] = ch; //翻转j之后的数组 reverse(str, ii, len-1); return true; } int main() { char str[] = "cab"; int len = strlen(str); //必须先排序 sort(str, str + len); printfString(str); //打印全排列 while(next_permutation(str)) { printfString(str); } return 0; }
參见:
http://blog.csdn.net/hackbuteer1/article/details/7462447
http://xiaomage.blog.51cto.com/293990/74094
http://blog.csdn.net/hackbuteer1/article/details/6657435
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117766.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...