Chinaunix首页 | 论坛 | 博客
  • 博客访问: 522467
  • 博文数量: 184
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1172
  • 用 户 组: 普通用户
  • 注册时间: 2016-06-21 13:40
个人简介

技术改变命运

文章分类

全部博文(184)

文章存档

2020年(16)

2017年(12)

2016年(156)

我的朋友

分类: C/C++

2016-08-16 10:20:32

题目描述: 
输入一个字符串,打印出该字符串中字符的所有排列。 
基本思路: 
从字符串中选出一个字符作为排列的第一个字符,然后对剩余的字符进行全排列,如此递归,从而得到所有字符的全排列。以对字符”abc”进行全排列为例,可以按下述步骤执行: 
将a固定在第一位,求后面bc的排列 
将b固定在第一位,求后面ac的排列 
将c固定在第一位,求后面ab的排列

#include #include #define swap(t,x,y) (t = (x),x = (y),y = (t)) void CalcAllPermutation(char *perm,int from,int to)
{ if (to < 0) return ; int i = 0; char t; if (from == to)
    { for (i = 0;i <= to;i++)
            printf("%c",perm[i]);
        printf("\n");
    } else { for (i = from;i <= to;i++)
        {
            swap(t,perm[i],perm[from]);//将from-to中的一个元素固定在第一位 CalcAllPermutation(perm,from+1,to);
            swap(t,perm[i],perm[from]);//恢复以前的状态 }
    }
} int main()
{ char s[] = "abcd";
    CalcAllPermutation(s,0,3); return 0;
} 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

运行结果(centos5.5) 
[root@localhost ~]# ./a.out 
abcd 
abdc 
acbd 
acdb 
adcb 
adbc 
bacd 
badc 
bcad 
bcda 
bdca 
bdac 
cbad 
cbda 
cabd 
cadb 
cdab 
cdba 
dbca 
dbac 
dcba 
dcab 
dacb 
dabc 
题目:输入一个字符串,输出该字符串中字符的所有组合。举个例子,如果输入abc,它的组合有a、b、c、ab、ac、bc、abc。 
上面我们详细讨论了如何用递归的思路求字符串的排列。同样,本题也可以用递归的思路来求字符串的组合。
假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符,我们有两种选择:第一是把这个字符放到组合中去,接下来我们需要在剩下的n-1个字符中选取m-1个字符;第二是不把这个字符放到组合中去,接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。下面是这种思路的参考代码:

 #include #include #include using namespace std; #include void Combination(char *string ,int number,vector<char> &result); void Combination(char *string)
{
    assert(string != NULL); vector<char> result; int i , length = strlen(string); for(i = 1 ; i <= length ; ++i)
        Combination(string , i ,result);
} void Combination(char *string ,int number , vector<char> &result)
{
    assert(string != NULL); if(number == 0)
    { static int num = 1; printf("第%d个组合\t",num++); vector<char>::iterator iter = result.begin(); for( ; iter != result.end() ; ++iter) printf("%c",*iter); printf("\n"); return ;
    } if(*string == '\0') return ;
    result.push_back(*string);
    Combination(string + 1 , number - 1 , result);
    result.pop_back();
    Combination(string + 1 , number , result);
} int main(void)
{ char str[] = "abc";
    Combination(str); return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46

运行结果如下:(centos5.5) 
[root@localhost ~]# ./a.out 
第1个组合 a 
第2个组合 b 
第3个组合 c 
第4个组合 ab 
第5个组合 ac 
第6个组合 bc 
第7个组合 abc

阅读(650) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~