首页 > 代码库 > backtracking(回溯算法)
backtracking(回溯算法)
http://blog.csdn.net/zxasqwedc/article/details/42270215
permutation的程式码都会长成这样的格式：
1 char s [ 3 ] = { ‘a‘, ‘b‘, ‘c‘ }; //字串，需要先由小到大排序过 2 char solution [ 3 ]; //用来存放一组可能的答案 3 bool used [ 3 ]; //纪录该字母是否使用过，用过为true 4 5 void permutation ( int k , int n ) 6 { 7 // it‘s a solution 8 if ( k == n ) 9 {10 for ( int i = 0 ; i < n ; i ++)11 cout << solution [ i ];12 cout << endl ;13 return ; // if-else改成return14 }15 16 // 针对solution[i]这个位置，列举所有字母，并各自递回17 for ( int i = 0 ; i < n ; i ++)18 if (! used [ i ])19 {20 used [ i ] = true ;21 22 solution [ k ] = s [ i ]; //填入字母23 permutation ( k + 1 , n );24 25 used [ i ] = false ;26 }27 }
字串排列
有个常见的问题是：列出字串abc的所有排列，要依照字典顺序列出。其实这就跟刚才介绍的东西大同小异，只要稍加修改程式码即可。
1 char s [ 3 ] = { ‘a‘, ‘b‘, ‘c‘ }; //字串，需要先由小到大排序过 2 char solution [ 3 ]; //用来存放一组可能的答案 3 bool used [ 3 ]; //纪录该字母是否使用过，用过为true 4 5 void permutation ( int k , int n ) 6 { 7 if ( k == n ) // it‘s a solution 8 { 9 for ( int i = 0 ; i < n ; i ++)10 cout << solution [ i ];11 cout << endl ;12 }13 else14 {15 // 针对solution[i]这个位置，列举所有字母，并各自递回16 for ( int i = 0 ; i < n ; i ++)17 if (! used [ i ])18 {19 used [ i ] = true ;20 21 solution [ k ] = s [ i ]; //填入字母22 permutation ( k + 1 , n );23 24 used [ i ] = false ;25 }26 }27 }
1 char s [ 3 ] = { ‘a‘, ‘b‘, ‘c‘ }; //字串，需要先由小到大排序过 2 char solution [ 3 ]; //用来存放一组可能的答案 3 bool used [ 3 ]; //纪录该字母是否使用过，用过为true 4 5 void permutation ( int k , int n ) 6 { 7 // it‘s a solution 8 if ( k == n ) 9 {10 for ( int i = 0 ; i < n ; i ++)11 cout << solution [ i ];12 cout << endl ;13 return ; // if-else改成return14 }15 16 // 针对solution[i]这个位置，列举所有字母，并各自递回17 for ( int i = 0 ; i < n ; i ++)18 if (! used [ i ])19 {20 used [ i ] = true ;21 22 solution [ k ] = s [ i ]; //填入字母23 permutation ( k + 1 , n );24 25 used [ i ] = false ;26 }27 }
避免重复排列
若是字串排列的问题改成：列出abb的所有排列，依照字典顺序列出。答案应该为abb、aba、baa。不过使用刚刚的程式码的话，答案却会变成这样：
abbabbbabbbababbba
这跟预期的不一样。会有这种结果，是由于之前的程式有个基本假设：字串中的每个字母都不一样。尽管出现了一样的字母，但是程式还是把它当作是不一样的字母，依旧把所有可能的排列都列出，也就是现在的结果──有一些排列重复出现了。
要解决问题，在列举某一个位置的字母时，就必须避免一直填入一样的字母。如此就可以避免产生重复的排列。
1 char s [ 3 ] = { ‘a‘, ‘b‘, ‘b‘ }; //字串，需要先由小到大排序过 2 char solution [ 3 ]; 3 bool used [ 3 ]; 4 5 void permutation ( int k , int n ) 6 { 7 if ( k == n ) 8 { 9 for ( int i = 0 ; i < n ; i ++)10 cout << solution [ i ];11 cout << endl ;12 return ;13 }14 15 char last_letter = ‘\0‘ ;16 for ( int i = 0 ; i < n ; i ++)17 if (! used [ i ])18 if ( s [ i ] != last_letter ) //避免列举一样的字母19 {20 last_letter = s [ i ]; //纪录刚才使用过的字母21 used [ i ] = true ;22 23 solution [ k ] = s [ i ];24 permutation ( k + 1 , n );25 26 used [ i ] = false ;27 }28 }
因为输入的字串由小到大排序过，字母会依照顺序出现，所以只要检查上一个使用过的字母，判断一不一样之后，就可以避免列举一样的字母了。
程式码也可以改写成这种风格：
1 char s [ 3 ] = { ‘a‘, ‘b‘, ‘b‘ }; //字串，需要先由小到大排序过 2 char solution [ 3 ]; 3 bool used [ 3 ]; 4 5 void permutation ( int k , int n ) 6 { 7 if ( k == n ) 8 { 9 for ( int i = 0 ; i < n ; i ++)10 cout << solution [ i ];11 cout << endl ;12 return ;13 }14 15 char last_letter = ‘\0‘ ;16 for ( int i = 0 ; i < n ; i ++)17 { // if not改成continue18 if ( used [ i ]) continue ;19 if ( s [ i ] == last_letter ) continue ; //避免列举一样的字母20 21 last_letter = s [ i ]; //纪录刚才使用过的字母22 used [ i ] = true ;23 24 solution [ k ] = s [ i ];25 permutation ( k + 1 , n );26 27 used [ i ] = false ;28 }29 }
http://www.cnblogs.com/guxuanqing/p/5602028.html
backtracking(回溯算法)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。