Вопрос по algorithm, string, permutation – Какой оптимальный алгоритм для создания всех возможных комбинаций строки?

2

Я нахожу другой подобный вопрос слишком сложным.

Я думаю, что это означает, что если нам дают банк, то комбинации будут горшок выбирать Топ горшок ВОМ горшок

поэтому я написал следующий код:

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

Есть ли способ лучше ?

Ваш код работает только для трехбуквенных слов. Вы не можете заставить это сделать четырехбуквенное слово без добавления дополнительного цикла. Это должно объяснить всю дополнительную сложность «других алгоритмов». что вы видели. dasblinkenlight
В вашем примереotp а такжеtpo не хватает,pot дается три раза. Не проверял ваш код, но если это его вывод и вы хотите сгенерировать все перестановки букв в строке, это может быть неправильно. Wolfram
похожие вопросы Anubha
хорошо, я признаю, что испортил алгоритм кода, пожалуйста, дайте правильный код. Anubha
Имеете ли вы в виду другие подобные вопросы или ответы, так как есть общие варианты этого вопроса. Rndm

Ваш Ответ

2   ответа
3

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

иала). Причина в том, что для каждой позиции каждого потенциального слова будет уменьшаться количество возможностей символов, которые могут заполнить позицию, например, 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! если нет повторяющихся букв. Это также представляет СУММУ СЛОВ, с которыми вы должны получить результат.

Код для выполнения чего-то подобного может быть (ПРОВЕРЕН И РАБОТАЕТ В С)

#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

Если есть повторяющиеся буквы, скажем, а, а, б, в

тогда всегда будут повторяться слова.

В этих случаях количество уникальных результирующих слов должно равняться количеству факторных уникальных символов, поэтому для приведенного выше случая это будет 3! не 4 !.

Причина этого состоит в том, что не имеет значения, КАКОЙ из пунктов заполняет данное место, и, таким образом, уникальность определяется количеством предоставленных уникальных букв. Это также сложная проблема, и я бы сказал, что вы должны генерировать ВСЕ N! Сначала слова, а затем запустить второй алгоритм для поиска повторяющихся слов и удаления. Могут быть более умные способы генерирования уникальных слов на лету.

Значит ли это, что O (n!) - единственно возможное решение, а оптимизация невозможна?

Похожие вопросы