Печать всех комбинаций струнного C++ `

Question

Проблемы: Учитывая строкух, сортировки, а затем печатать все комбинации. (найти на сайте кодирования, такие как hackerrank/interviewbit/geeksforgeeks)

Вот пример ...

Входной сигнал: строка х = "БАК"

Выход: [ABC, АВ, АС, ВС, А, в, с]

Текущий рабочий раствор: (работает только для случая, когда x.length() = 3)

void printCombinations(string q){ 
    stack<char> c; 
    stack<char> c2; 
    sort(q.begin(), q.end()); 
    for(int i = 0; i<q.size(); i++){ 
     cout<<q[i]; 
     c.push(q[i]); 
    } 
    cout<<endl; 

    for(int i = 0; i<q.size(); i++){ 
     char t = c.top(); 
     cout<<t<<endl; 
     for(int j=0; j<c.size(); j++){ 
     c.pop(); 
     c2.push(c.top()); 
     cout<< t << c.top() <<endl; 
     } 
     c.pop(); 
     c = c2; 
    } 
} 

Answer 1

void printCombinations(string q){ 
    cout<<"We are now printing out all the combinations of "<<q<<endl; 
    sort(q.begin(), q.end()); 
    bitset<10> b; 
    int count =0; 
    for(int i=0; i<pow(2,q.size()); ++i){ 
     for(int x=0;x<10;x++){ 
      if(b[x] == 1){ 
       cout<<q[x]; 
      } 
     } 
     count++; 
     cout<<endl; 
     for(int j=0; j<10;j++){ 
      if(b[j]==1){ 
       b[j].flip(); 
      } 
      else{ 
       b[j].flip(); 
       break; 
      } 
     } 
    } 
    cout<<"There are "<<count<<" combinations"<<endl; 
} 

Вот одно решение поставленной выше задачи.

Answer 2

Я не уверен, почему код, отправленный в вашем вопросе, работает только с трехсимвольными строками, но, тем не менее, есть несколько проблем с ним (например, вам не нужно обращаться к стеку).

Это может быть решена путем преобразования string в массив char и итерации. код похож на то, что вы после того, как можно найти here и та же страница также дает имя решения (backtracking) и миленький схема, поясняющая, как это работает, используя строку ABC в качестве примера:

http://www.geeksforgeeks.org/wp-content/uploads/NewPermutation.gif

Этот код, однако, не делать то, что вы хотите «из коробки», но тем не менее с небольшой модификацией коды он делает:

код имеет небольшую ошибку где-то в нем, что делает вывод странных символов с результат, но однако делает prin все комбинации. Заглядывая в это и обновляя код, когда у меня есть решение.

void swap(char *x, char *y) 
{ 
    char temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 


void permute(char *a, int i, int n) 
{ 
    int j; 
    if (i == n) 
     std::cout << string(a); 
    else 
    { 
     for (j = i; j <= n; j++) 
     { 
      swap((a + i), (a + j)); 
      permute(a, i + 1, n); 
      swap((a + i), (a + j)); //backtrack 
     } 
    } 
} 

int main() 
{ 
    char a[] = "BAC"; 
    int len = sizeof(a)/sizeof(a[0]); 
    permute(a, 0, len); 
    getchar(); 
    return 0; 
}