使字符串的所有可能组合最佳的算法是什么? [英] What is optimal algorithm to make all possible combinations of a string?
问题描述
我发现其他类似的问题也太复杂了.
I find other similar question too complicated.
我认为这意味着如果我们得到锅，那么组合将是 锅 选择 最佳 锅 取力器 锅
I think it means if we are given pot then combinations will be pot opt top pot pto pot
所以我写了以下代码:
#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.
This problem is inherently an O(N!) (factorial) complexity problem. The reason is that for each position of each potential word, there will be a decrementing amount of possibilities of characters that can fill the position, An example with 4 letters a, b, c, and 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个字符串，复杂度来自于(在这种情况下)可以填充给定输出字的字符位置的潜在可能性，因此:
This is only for 1 string, the complexity comes from (in this case) the potential possibilities that can fill a character location for a given output word, thus:
4 * 3 * 2 * 1 = 4!
这可以扩展为任意数量的输入字母，并且恰好是N！如果没有重复的字母.这也代表您应得到的单词数量.
This can be extended to any amount of input letters and is exactly N! if there are no repeat letters. This also represents the AMOUNT OF WORDS you should result with.
可以执行以下操作的代码(在C中进行测试和工作):
Code to perform something like this could be (TESTED AND WORKING IN 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;
}
从外部，如下调用:
projectName abc
使用"abc"的示例输出
sample output from using "abc"
abc
acb
bac
bca
cab
cba
如果有重复的字母，请说a，a，b，c
If there are repeat letters lets say a, a, b, c
然后总是会有重复的单词.
then there will ALWAYS be repeat words.
在这种情况下，唯一结果字的数量应为阶乘的唯一字符的数量，因此在上述情况下为3！不是4！.
With these cases, the amount of UNIQUE result words should be the amount of unique characters factorial, so for the above case it would be 3! not 4!.
这样做的原因是，a的填充到给定位置无关紧要，因此，唯一性就是所提供的唯一字母的数量.这也是一个难题，从某种意义上说，我应该生成ALL N！首先输入单词，然后运行第二种算法以搜索重复单词并删除.可能会有更聪明的方式来动态生成唯一单词.
The reason for this is that it does not matter WHICH of the a's fills a given spot and thus the uniqueness is given be the amount of unique letters provided. This is also a hard problem, and in ways I would say you should generate ALL N! words first, then run a second algorithm to search for the repeat words and delete. There may be smarter ways of generating the unique words on the fly.
这篇关于使字符串的所有可能组合最佳的算法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
