如何通过算法计算字母表Σ的所有排列组合？

本文共计1136个文字，预计阅读时间需要5分钟。

python字符串表示 + 为 a，b，为字符，设计函数计算字符串 a 和 b 上方长度的字符串个数的和def count_strings_above(a, b, n=5): # 初始化计数器 count=0 # 计算字符串长度 len_a=len(a) len_b=len(b) # 遍历字符串a中的每个字符 for i in range(len_a): # 判断字符串b的长度是否小于n if len_b

给定n=5时，字符串个数的计算n=5result=count_strings_above(abcdef, bcdef, n)print(result)

字母表 ∑ 为 {a ， b} 1.设计函数，用以计算建立在 ∑上长度小于N 的字符串的个数，并给出N=5时的字符串个数。 2.在上述功能的基础上，增加列出所有符合条件的字符串功能。 输入输出样例： 输入： 1 输出： a b 输入： 2 输出： aa ab ba bb 输入： 3 输出： aaa aab aba abb baa bab bba bbb AC代码：

//方法1(递归解法)：#include<stdio.h>int i,n;char str[50];void DFS(int k){ if(k<n) { str[k+1]='a'; DFS(k+1); str[k+1]='b'; DFS(k+1); } else { for(i=1;i<=n;i++) { printf("%c",str[i]); } printf("\n"); }}int main(){ while(scanf("%d",&n)!=EOF) { DFS(0); } return 0;}

//方法2(规律解法)：#include<stdio.h>void zifu(int n){ int i=0,j; char a[50]={'a','a'}; while(1) { if(i==n) { for(j=1;j<=n;j++) printf("%c",a[j]); printf("\n"); } if(i<n) { a[++i]='a'; continue; } while(a[i]=='b') i--; if(i>0) a[i]++; else break; }}int main(){ int n; while(scanf("%d",&n)&&n) { zifu(n); } return 0;}

例如输入3：

结果：

3

aaa

aab

aba

abb

baa

bab

bba

bbb

分析过程：

先是aaa，无b，不执行while，

遇到if，最后一个+1变成b，

回到顶端输出aab。

之后b被while隔过去

剩aa，遇到if，最后一个+1变成b，此时为ab。

回到顶端发现不够3，加一个a(此时为aba)，

continue回到顶端，输出aba。

遇到if，最后一个+1变成b，

回到顶端输出abb。

之后bb被while隔过去

剩a，遇到if，最后一个+1变成b，此时为b。

回到顶端发现不够3，加两个a(此时为baa)，

continue回到顶端，输出baa。

遇到if，最后一个+1变成b，

回到顶端输出bab。

之后b被while隔过去

剩ba，遇到if，最后一个+1变成b，此时为bb。

回到顶端发现不够3，加一个a(此时为bba)，

continue回到顶端，输出bba。

遇到if，最后一个+1变成b，

回到顶端输出bbb。

之后bbb被while隔过去,

剩空串，break出去，算法结束。

即是：一开始是空串，然后遵循一下变化：

1.不够3位，补a。

2.后面有几位b，全去掉，若变成空串退出算法。

3.如果末尾是a，变成b，够3位输出。

//方法3(构建二叉树)：#include<stdio.h>#include<algorithm>#include<stdlib.h>struct per{ int L; int R; char v; }a[1000*3];int i,num;char b[1000*3];//构建二叉树void BuildTree(int n,int m){ if(m<10) { a[n].L=2*n; a[2*n].v='a'; a[n].R=2*n+1; a[2*n+1].v='b'; m++; BuildTree(a[n].L,m); BuildTree(a[n].R,m); } else { return; } }//查找void Find(int x,int y,int p,char b[]){ p++; b[p]=a[x].v; if(p==y) { for(i=1;i<=y;i++) printf("%c",b[i]); printf("\n"); return; } Find(a[x].L,y,p,b); Find(a[x].R,y,p,b);}int main(){ BuildTree(1,0); while(scanf("%d",&num)!=EOF) { a[1].v='a'; Find(1,num,0,b); a[1].v='b'; Find(1,num,0,b); } return 0;}

二叉树遍历字母表∑的模型：

以上算法并不一定是最优的，还有其他方法，就不在一一叙述，有兴趣的可以自己去研究。