字符串面试题系列之七:字符串全排列

时间:2023-01-04 14:33:13

编译环境

   本系列文章所提供的算法均在以下环境下编译通过。

【算法编译环境】Federa 8,linux 2.6.35.6-45.fc14.i686
【处理器】 Intel(R) Core(TM)2 Quad CPU Q9400 @ 2.66GHz
【内存】 2025272 kB

前言

    这是一道排列组合的题目。对于排列组合的题目在面试当中也是十分常见,主要考察小伙伴们的思维的有序性和解决问题的能力。本题就曾出自腾讯的笔试当中。一般这类题目大家做的时候用树的方式来帮助思考会有一些效果。

    本系列文章均系笔者所写,难免有一些错误或者纰漏,如果小伙伴们有好的建议或者更好的算法,请不吝赐教。

正文

【题目】

   输入一个字符串,打印出该字符串中字符的所有排列。

【例子】

   输入字符串abc,则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。

【分析】

   这是一道排列组合的题目。而做排列组合的时候头脑要保持清醒并且有序。我们列举一个例子,假设有字符串abc,如果我们手动排列,过程是怎样的呢?

   一般人的分析习惯总是把大问题化成小问题来解决。这是我们的习惯。
首先保持a在第一位不动,我们看子字符串bc,bc的排列是bc和cb,这样我们得到结果是abc,acb ;
其次保持b在第一位不东,我们看子字符串ac,ac的排列是ac和ca,这样我们得到结果是bac,bca ;
再次保持c在第一位不东,我们看子字符串ab,ab的排列是ab和ba,这样我们得到结果是cab,cba
这样我们都得到三个字符的排列是abc,acb,bac,bca,cab,cba。这样思维是不是很清晰。

   参照上面的手工做法,我们如何用程序去实现呢。显然用递归的方式更符合我们的思维。

第一步:当字符串只有1个字符的时候,其排列是字符本身。
第二步:递归求出子字符串的排列
第三步:算法结束。

【代码】

#include <iostream>
#include
<cstring>

#define swap(a, b) { char c=a; a=b; b=c; }

void string_permutation( char * const string, int start, int end )
{
if( start == end )
{
std::cout
<< string << std::endl;
}
else
{
for( int i = start; i < end; i++)
{
// swap two characters
swap( string[i], string[start] );
string_permutation(
string, start + 1, end );
// recover
swap( string[i], string[start] );
}
}
}

int main( int argc, char ** argv )
{
char string[] = "abcd";
string_permutation(
string, 0, strlen(string) );
return 0;
}

【结论】

   我们输入字符串abcd,应该有16种排列组合的方式。得到的结果如下:

字符串面试题系列之七:字符串全排列

作者

   出处:http://www.cnblogs.com/gina

   本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。