2

他の同様の質問は複雑すぎると思います。

ポットが与えられたら、組み合わせはポットオプトトップポット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);
        }
    }

もっと良い方法はありますか？

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のどちらが特定のスポットを埋めるかは問題ではないため、提供される一意の文字の量によって一意性が与えられるためです。これも難しい問題であり、ある意味ではALLNを生成する必要があります。最初に単語を検索し、次に2番目のアルゴリズムを実行して繰り返し単語を検索し、削除します。その場でユニークな単語を生成するより賢い方法があるかもしれません。

于 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 に答える