什么是最佳算法,使所有可能的字符串组合?
我发现其他类似的问题太复杂了。什么是最佳算法,使所有可能的字符串组合?
我认为,这意味着,如果我们给出锅然后组合将 锅 选择 顶部 锅 PTO 锅
所以我写了下面的代码:
#include<iostream>
#include<string.h>
using namespace std;
int main(){
char s[10];
char temp;
cin>>s;
char t[10];
for(int i=0;i<3;i++)
{
for(int j=i;j<3;j++)
{
strcpy(t,s);
temp=s[i];
s[i]=s[j];
s[j]=temp;
cout<<s<<"\n";
strcpy(s,t);
}
}
是否有更好的方法 ?
这个问题本质上是O(N!)(因子)复杂性问题。原因在于,对于每个潜在单词的每个位置,会有一个递减的可能性填充该位置的字符,这个例子有4个字母a,b,c和d。
-----------------
Positions: | 0 | 1 | 2 | 3 |
-----------------
In position 0, there are 4 possibilities, a, b, c, or d
Lets fill with a
-----------------
String: | a | | | |
-----------------
Now Position 1 has 3 possibilities of fill letters b, c, or d
Lets fill with b
-----------------
String: | a | b | | |
-----------------
Now Position 2 has 2 possibilities of fill letters c, or d
Lets fill with c
-----------------
String: | a | b | c | |
-----------------
Now Position 1 has only 1 possibility for a fill letter: d
-----------------
String: | a | b | c | d |
-----------------
这仅是1串,所述复杂性来自(在这种情况下),可以填充一个字符位置对于给定的输出字,从而潜在可能性:
4 * 3 * 2 * 1 = 4!
这可以是扩展到任意数量的输入字母,并且正好是N!如果没有重复的字母。这也代表了你应该得到的数量的话。像这样,可以(经测试和工作C)
代码来执行的东西:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
void printPermutations(int level, const char * inString, char * outString){
unsigned int len = strlen(inString);
char * unusedLetter;
int j;
if(1 == len){
printf("%s%s\n", outString, inString);
}else{
unusedLetters = (char *)malloc(sizeof(char) * (len - 1));
for(int startLetter = 0; startLetter < len; startLetter++){
outString[level] = inString[startLetter];
// setup the "rest of string" string
j = 0;
for(int i = 0; i < len; i++){
if(i != startLetter){
unusedLetter[j] = inString[i];
j++;
}
}
// recursive call to THIS routine
printPermutations(level+1, unusedLetters, outString);
}
}
}
int main(int argc, char * argv[]){
unsigned int len;
char * outString;
if(argc != 2) return 0;
len = strlen(argv[1]);
outString = (char *)malloc(sizeof(char) * (len + 1));
outstring[len] = '\0';
printPermutations(0, argv[1], outString);
return 0;
}
从外部调用此如下:使用 “ABC”
projectName abc
样本输出
abc
acb
bac
bca
cab
cba
如果有重复的字母可以说a,a,b,c
那么总会有重复的话。
在这些情况下,UNIQUE结果字的数量应该是唯一字符factorial的数量,因此对于上述情况,它应该是3!不是4 !.
其原因在于,a的哪一个填满给定的位置并不重要,因此唯一性是给定的唯一字母的数量。这也是一个难题,而且我会说你应该生成所有N!先运行单词,然后运行第二个算法搜索重复单词并删除。在飞行中产生独特的词语可能有更聪明的方法。 。
那么这是否意味着O(n!)是唯一可能的解决方案,并且不可能进行优化? – Ayusman 2013-08-15 02:53:42
下面的解决方案是O(N!)这需要反复考虑过:
#include<stdio.h>
void permute(char s[10],char *p);
int count=0;
main(){
char s[10];
int i;
scanf("%s",s);
permute(s,s);
}
//takes into account repetetion
void permute(char s[10],char *p){
char *swap,temp;
if(*(p+1)==0) {
count++;
printf("%4d] %s\n",count,s);
}
else{
for(swap=p;*swap;++swap){
char *same;
for(same=p;*same!=*swap;++same){};
if(same==swap){
temp=*swap;
*swap=*p;
*p=temp;
permute(s,p+1);
*p=*swap;/*restoring the original string*/
*swap=temp;
}
}
}
}
您的代码只针对三个字母的单词。不能添加一个额外的循环来做一个四个字母的单词。这应该解释你所看到的“其他算法”的额外复杂性。 – dasblinkenlight 2012-07-13 14:33:49
你是否指其他类似的问题或答案,因为这个问题有一些常见的变种。 – Rndm 2012-07-13 14:37:38
在你的例子中'otp'和'tpo'丢失了,'pot'被给出了三次。没有检查你的代码,但如果这是它的输出,你的意思是在字符串中生成所有字母的排列,那可能是错误的。 – Wolfram 2012-07-13 14:37:59