2

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

so I wrote the following code:

#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);
        }
    }

Is there a better way ?

4

2 回答 2

4

这个问题本质上是一个 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;
}

从外部调用如下：

projectName abc

使用“abc”的示例输出

abc
acb
bac
bca
cab
cba

如果有重复的字母，让我们说 a、a、b、c

那么总会有重复的话。

在这些情况下，UNIQUE 结果词的数量应该是唯一字符的数量，因此对于上述情况，它将是 3！不是4！。

这样做的原因是，a 中的哪个填充给定位置并不重要，因此唯一性是由提供的唯一字母的数量给出的。这也是一个难题，在某种程度上我会说你应该生成 ALL N！首先是单词，然后运行第二个算法来搜索重复的单词并删除。可能有更聪明的方法可以即时生成独特的单词。

于 2012-07-13T14:59:24.917 回答
3

以下解决方案是 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;
                }
            }
        }
    }
于 2012-07-13T20:04:15.997 回答