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

Мне нужно сгенерировать все перестановки строки с выбором некоторых элементов. Например, если в моей строке "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;
    }

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

Спасибо, Г.Г.

 Andre Holzner02 окт. 2010 г., 09:25
Обратите внимание, что для строки длиныN у тебя будет2^N-1 отдельные непустые подмножества в худшем случае (если все символы разные) и для каждого подмножества, состоящего изL персонажи, вы будете иметьL! Перестановки.
 rwong02 окт. 2010 г., 09:13
Я не читал ваш код, но ваше словесное описание звучит правильно: используйте [en.wikipedia.org/wiki/Power_set] вместе с перестановкой. Перечислитьнабор мощностиПодумайте об увеличении двоичного числа, где каждая «цифра» соответствует числу раз, которое входной элемент был выбран для отображения в выходных данных. Для повторяющихся элементов во входном наборе некоторые «цифры» «двоичного» числа станут троичными, или число повторений этого элемента.

Ответы на вопрос(3)

видеть этоАлгоритм возврата всех комбинаций k элементов из n

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

 arbithero02 окт. 2010 г., 21:53
Хорошо, мой плохой.
 Roger Pate02 окт. 2010 г., 09:11
Используйте комментарии вместо ответов для этого.
 GG.02 окт. 2010 г., 09:40
Я уже посетил ссылку, но моя проблема в другом.
 Nikita Rybak02 окт. 2010 г., 09:31
Похоже, это решениеочень другая проблема
#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;
}

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

#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;
}
 GG.02 окт. 2010 г., 09:16
Я не могу понять, как это сделать, можете ли вы уточнить немного?
 Roger Pate02 окт. 2010 г., 09:52
@GG: Ах, сначала я пропустил: next_permutation требует, чтобы начальное состояние было отсортировано, если вы хотите пройти через все перестановки. Используйте std :: sort при необходимости.
 GG.02 окт. 2010 г., 09:31
Я думаю, здесь есть некоторые проблемы. позволяет сказать, что строка «acbc» ваши результаты: 1a2ac3acb4acbc5acc6accb7b8ba9bac10bacc11bc12bca13bcac14bcc15bcca16c17ca18cab19ca bc20cac21cacb22cb23cba24cbac25cbc26cbca27cc28cca29ccab30ccb31ccba, но это должно быть 1a2c3b4ac5ca6ab7ba8bc9cb10cc11bc12cb13abc14acb15bac16bca17cab18cba19acc20cac21cc a22abc23acb24bac25bca26cab27cba28bcc29cbc30ccb31abcc32acbc33accb34bacc35bcac36bc ca37cabc38cacb39cbac40cbca41ccab42ccba
Решение Вопроса

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

С СТЛ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)" для каждого вывода, что очень и очень мало.

 Nikita Rybak03 окт. 2010 г., 10:23
@ Г.Г. Я думаю, ваши решения будут иметь сопоставимую скорость. (Хотя Роджер наверняка использует больше памяти, как вы заметили.) Но есть очень простой способ проверить, что быстрее: запускать их с одним и тем же вводом.
 Nikita Rybak02 окт. 2010 г., 09:26
@GG Простая печать 10 ^ 9 различных строк должна занять время, близкое к часу (и около 10 ГБ дискового пространства). Это то, что вы хотите?
 GG.02 окт. 2010 г., 13:00
Я получил ответ, в случаях Роджера количество дубликатов было бы слишком много. и я храню комбинации только тогда, когда он хранит все различные перестановки. Так что это неэффективно с точки зрения памяти и времени. Я прав?
 GG.02 окт. 2010 г., 12:37
не является ли решение, данное Роджером, более эффективным?
 Nikita Rybak02 окт. 2010 г., 09:37
@GG Нет способа напечатать 10 ^ 9 строк без их печати. (Если вы измените требования, например, если вы решите, что вы хотите знать только количество этих строк, это будет другой историей.) Поэтому я предлагаю остаться с вашей текущей программой: вы не получите намного более быстрого решения.
 GG.02 окт. 2010 г., 09:23
поэтому я могу сделать размер вывода длинным, так как я использую его для печати серийного номера. Для int я могу сгенерировать комбинацию до n = 32
 GG.02 окт. 2010 г., 09:30
@nikita Я не вижу другого пути? Или я должен поставить ограничение, которое не должно давать мне число больше 9.
 GG.02 окт. 2010 г., 09:41
Спасибо Никита, я лучше буду придерживаться требований.

Ваш ответ на вопрос