http://blog.csdn.net/zxasqwedc/article/details/42270215
permutation的程式码都会长成这样的格式：
] = { 'a', 'b', 'c' }; //字串，需要先由小到大排序过
]; //用来存放一组可能的答案
]; //纪录该字母是否使用过，用过为true
void permutation ( int k , int n )
{
// it's a solution
if ( k == n )
{
; i < n ; i ++)
cout << solution [ i ];
cout << endl ;
return ; // if-else改成return
}
// 针对solution[i]这个位置，列举所有字母，并各自递回
; i < n ; i ++)
if (! used [ i ])
{
used [ i ] = true ;
solution [ k ] = s [ i ]; //填入字母
permutation ( k + , n );
used [ i ] = false ;
}
}
字串排列
有个常见的问题是：列出字串abc的所有排列，要依照字典顺序列出。其实这就跟刚才介绍的东西大同小异，只要稍加修改程式码即可。
] = { 'a', 'b', 'c' }; //字串，需要先由小到大排序过
]; //用来存放一组可能的答案
]; //纪录该字母是否使用过，用过为true
void permutation ( int k , int n )
{
if ( k == n ) // it's a solution
{
; i < n ; i ++)
cout << solution [ i ];
cout << endl ;
}
else
{
// 针对solution[i]这个位置，列举所有字母，并各自递回
; i < n ; i ++)
if (! used [ i ])
{
used [ i ] = true ;
solution [ k ] = s [ i ]; //填入字母
permutation ( k + , n );
used [ i ] = false ;
}
}
}
] = { 'a', 'b', 'c' }; //字串，需要先由小到大排序过
]; //用来存放一组可能的答案
]; //纪录该字母是否使用过，用过为true
void permutation ( int k , int n )
{
// it's a solution
if ( k == n )
{
; i < n ; i ++)
cout << solution [ i ];
cout << endl ;
return ; // if-else改成return
}
// 针对solution[i]这个位置，列举所有字母，并各自递回
; i < n ; i ++)
if (! used [ i ])
{
used [ i ] = true ;
solution [ k ] = s [ i ]; //填入字母
permutation ( k + , n );
used [ i ] = false ;
}
}
避免重复排列
若是字串排列的问题改成：列出abb的所有排列，依照字典顺序列出。答案应该为abb、aba、baa。不过使用刚刚的程式码的话，答案却会变成这样：
abb abb bab bba bab bba
这跟预期的不一样。会有这种结果，是由于之前的程式有个基本假设：字串中的每个字母都不一样。尽管出现了一样的字母，但是程式还是把它当作是不一样的字母，依旧把所有可能的排列都列出，也就是现在的结果──有一些排列重复出现了。
要解决问题，在列举某一个位置的字母时，就必须避免一直填入一样的字母。如此就可以避免产生重复的排列。
] = { 'a', 'b', 'b' }; //字串，需要先由小到大排序过
];
];
void permutation ( int k , int n )
{
if ( k == n )
{
; i < n ; i ++)
cout << solution [ i ];
cout << endl ;
return ;
}
char last_letter = '\0' ;
; i < n ; i ++)
if (! used [ i ])
if ( s [ i ] != last_letter ) //避免列举一样的字母
{
last_letter = s [ i ]; //纪录刚才使用过的字母
used [ i ] = true ;
solution [ k ] = s [ i ];
permutation ( k + , n );
used [ i ] = false ;
}
}
因为输入的字串由小到大排序过，字母会依照顺序出现，所以只要检查上一个使用过的字母，判断一不一样之后，就可以避免列举一样的字母了。
程式码也可以改写成这种风格：
] = { 'a', 'b', 'b' }; //字串，需要先由小到大排序过
];
];
void permutation ( int k , int n )
{
if ( k == n )
{
; i < n ; i ++)
cout << solution [ i ];
cout << endl ;
return ;
}
char last_letter = '\0' ;
; i < n ; i ++)
{ // if not改成continue
if ( used [ i ]) continue ;
if ( s [ i ] == last_letter ) continue ; //避免列举一样的字母
last_letter = s [ i ]; //纪录刚才使用过的字母
used [ i ] = true ;
solution [ k ] = s [ i ];
permutation ( k + , n );
used [ i ] = false ;
}
}