Все возможные комбинации слова

Question

Я был на собеседовании, и они попросили меня сгенерировать список всех возможных перестановок данной строки . Мое решение было неэффективным, и парень, который взял у меня интервью, сказал мне, что я должен использовать рекурсию. Кто-нибудь знает этот вопрос?

Answer 1

Это классический вопрос интервью, решение выходит что-то вроде этого:

int permu(char* str, size_t len ,size_t index) 
{ 
    size_t i = index - 1; 

    if(index == len) { printf ("%s\n",str); } 

    while (++i < len) 
    { 
     swap (str,index,i);   /* swap between index and i */ 
     permu(str, len ,index + 1); /* recorsion */ 
     swap (str,index,i);   /* swap back between index and i */ 
    } 

    return(0); 
} 

Обратите внимание, что в этом коде пользователь должен дать 0 в индексе parmether так лучше, чтобы вызвать эту функцию, как это :

int permutations(char* str, size_t len) 
{ 
    return (permu(str, len ,0)); 
} 

static int permu(char* str, size_t len ,size_t index) 
{ //....}