Алгоритм для генерации всех перестановок путем выбора некоторых или всех charaters

Question

Мне нужно сгенерировать всю перестановку строки с выбором некоторых элементов. Например, если моя строка - это «abc», то вывод будет {a, b, c, ab, ba, ac, ca, bc, cb, abc, acb, bac, bca, cab, cba}.

Я думал о базовом алгоритме, в котором я генерирую всю возможную комбинацию «abc», которые являются {a, b, c, ab, ac, bc, abc}, а затем переставляют их все.

Итак, есть эффективный алгоритм перестановки, с помощью которого я могу сгенерировать все возможные перестановки с разным размером.

Код я написал для этого:

#include <iostream> 
    #include <stdio.h> 
    #include <stdlib.h> 
    #include <map> 
    using namespace std; 

    int permuteCount = 1; 


    int compare (const void * a, const void * b) 
    { 
     return (*(char*)a - *(char*)b); 
    } 

    void permute(char *str, int start, int end) 
    { 
     // cout<<"before sort : "<<str; 

     // cout<<"after sort : "<<str; 
      do 
     { 
       cout<<permuteCount<<")"<<str<<endl; 
       permuteCount++; 
     }while(next_permutation(str+start,str+end)); 
    } 

void generateAllCombinations(char* str) 
{ 
    int  n, k, i, j, c; 
    n = strlen(str); 

    map<string,int> combinationMap; 

for(k =1; k<=n; k++) 
{ 
    char tempStr[20]; 
    int index =0; 
    for (i=0; i<(1<<n); i++) { 
     index =0; 
     for (j=0,c=0; j<32; j++) if (i & (1<<j)) c++; 
     if (c == k) { 

     for (j=0;j<32; j++) 
      if (i & (1<<j)) 
       tempStr[ index++] = str[j];   
     tempStr[index] = '\0'; 
     qsort (tempStr, index, sizeof(char), compare); 
     if(combinationMap.find(tempStr) == combinationMap.end()) 
     { 
     // cout<<"comb : "<<tempStr<<endl; 
     //cout<<"unique comb : \n"; 
      combinationMap[tempStr] = 1; 
      permute(tempStr,0,k); 
     } /* 
     else 
     { 
      cout<<"duplicated comb : "<<tempStr<<endl; 
     }*/ 
     } 
    } 


} 
} 


    int main() { 


      char str[20]; 
      cin>>str; 

      generateAllCombinations(str); 

      cin>>str; 
    } 

мне нужно использовать хэш для избежания такой же комбинации, поэтому, пожалуйста, дайте мне знать, как я могу сделать этот алгоритм лучше.

Спасибо, GG

Answer 1

Я не думаю, что вы можете написать программу гораздо быстрее, чем у вас уже. Основная проблема - размер вывода: он имеет порядок n!*2^n (количество подмножеств * среднее число перестановок для одного подмножества), которое уже равно > 10^9 для строки из 10 разных символов.

Поскольку STL's next_permutation добавляет очень ограниченную сложность для таких маленьких строк, временная сложность вашей программы уже почти O(output size).

Но вы можете сделать свою программу немного проще. В частности, цикл for(k =1; k<=n; k++) кажется излишним: вы уже вычисляете размер подмножества в переменной c внутри. Итак, просто введите int k = c вместо if (c == k). (Вы должны будете также рассмотреть случай пустого подмножества: i == 0)

редактировать
На самом деле, есть только 9864100 выходы для n == 10 (не ~ 10^9). Тем не менее, мой вопрос остается тем же: ваша программа уже тратит только «O (next_permutation)» время для каждого выхода, что очень и очень мало.

Answer 2

увидеть этот Algorithm to return all combinations of k elements from n

очень подробные решения вашей проблемы

Answer 3

#include <algorithm> 
#include <iostream> 
#include <string> 

int main() { 
    using namespace std; 
    string s = "abc"; 
    do { 
    cout << s << '\n'; 
    } while (next_permutation(s.begin(), s.end())); 
    return 0; 
} 

Next_permutation использует постоянный размер, но вы можете добавить цикл, чтобы иметь дело с различными размерами. Или просто хранить в наборе, чтобы устранить лишние простофили для вас:

#include <set> 

int main() { 
    using namespace std; 
    string s = "abc"; 
    set<string> results; 
    do { 
    for (int n = 1; n <= s.size(); ++n) { 
     results.insert(s.substr(0, n)); 
    } 
    } while (next_permutation(s.begin(), s.end())); 
    for (set<string>::const_iterator x = results.begin(); x != results.end(); ++x) { 
    cout << *x << '\n'; 
    } 
    return 0; 
}