文章详情

  • 游戏榜单
  • 软件榜单
关闭导航
热搜榜
热门下载
热门标签
php爱好者> php文档>Permutations of a String

Permutations of a String

时间:2010-08-05  来源:sinodragon21

Question: Print all the permutations of a string. Write code in C.

Answer: Here is a recursive solution to print all the permutations of a string. However, this solution does not take care of duplicates. It is assumed that there are no duplicates in the string. I left out the implementation of the swap method since that implementation is not important here.

The idea is to keep the first character constant and generate permutations with the rest. Then keep the first two characters constant and generate permutations with the rest until you are out of characters

void permutate( char[] str, int index )
{
int i = 0;
if( index == strlen(str) )
{ // We have a permutation so print it
printf(str);
return;
}
for( i = index; i < strlen(str); i++ )
{
swap( str[index], str[i] ); // It doesn't matter how you swap.
permutate( str, index + 1 );
swap( str[index], str[i] );
}
}
permutate( "abcdefgh", 0 );

Now what do we do if there are duplicates in the string? The trick is to sort the characters in the alphabetical order first. We can then ignore the duplicates easily when generate the permutation.

void permutate( char[] str, int index )
{
int i = 0;
static lastChar = 0;
if( index == strlen(str) )
{ // We have a permutation so print it
printf(str);
return;
}
for( i = index; i < strlen(str); i++ )
{
if( lastChar == str[i] ) {
continue;
} else {
lastChar = str[i];
}
swap( str[index], str[i] ); // It doesn't matter how you swap.
permutate( str, index + 1 );
swap( str[index], str[i] );
}
}
permutate( sort("Hello World"), 0 );

Simple right? Any comments or suggestions are always welcome.

Like this post? Please Digg it or Stumble it.
相关阅读 更多 +
排行榜 更多 +
空中跑酷汉化版

空中跑酷汉化版

赛车竞速 下载
修仙传说

修仙传说

角色扮演 下载
魔界零之迷宫

魔界零之迷宫

冒险解谜 下载