Там какие-либо лучшие методы должны сделать перестановку строки?

В частности, вы хотите std::next_permutation.

void permute(string elems, int mid, int end)
{
  int count = 0;
  while(next_permutation(elems.begin()+mid, elems.end()))
    cout << << ++count << " : " << elems << endl;
}

... или что-то в этом роде...

Почему бы не попробовать std::next_permutation() или std::prev_permutation()? ?

Ссылки:

std::next_permutation()
std::prev_permutation()

Простой пример:

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

int main()
{
   std::string s="123";
   do
   {

      std::cout<<s<<std::endl;

   }while(std::next_permutation(s.begin(),s.end()));
}

Выход:

123
132
213
231
312
321

] Любой алгоритм генерации перестановок будет выполняться в полиномиальное время, так как количество перестановок для символов внутри строки n-длины равно [](n!)[]. При этом существуют довольно простые встроенные алгоритмы генерации перестановок. Посмотрите на алгоритм Джонсона-Троттера [][].[

] Любой алгоритм, который использует или генерирует все перестановки, будет принимать время O(N!*N), O(N!), по крайней мере, для генерации всех перестановок и O(N), чтобы использовать результат, и это действительно медленная работа. Обратите внимание, что печать строки также O(N) afaik.[

]В секунду вы можете реально обрабатывать строки максимум до 10 или 11 символов, не зависимо от того, какой метод вы используете. Начиная с 11!*11 = 439084800 итераций (на большинстве машин это делается за секунду) и 12!*12 = 5748019200 итераций. Таким образом, даже самая быстрая реализация займет около 30-60 секунд на 12 символах. [

] Факториал растет слишком быстро, чтобы надеяться получить что-либо, написав более быструю реализацию, вы бы получили максимум один символ. Поэтому я бы посоветовал рекомендацию Прасуна. Она проста в программировании и довольно быстра. Хотя придерживаться своего кода тоже неплохо.[

]Я бы просто порекомендовал позаботиться о том, чтобы в строке случайно не было лишних символов, таких как нулевой символ. Так как это сделает ваш код на N медленнее.[

Недавно я написал алгоритм перестановки. Он использует вектор типа T (шаблон) вместо строки, и он не супербыстрый, потому что он использует рекурсию и много копий. Но, возможно, вам удастся почерпнуть вдохновение для кода. Вы можете найти код здесь .

Также можно щелкнуть правой кнопкой мыши по проекту - > Инструменты Android - > Исправить свойства проекта . Это должно привести к повторному созданию класса R.java.

Только способ значительно улучшить производительность - найти способ избежать итерации через все перестановки в первую очередь!

Перестановка - это неизбежно медленная операция (O (n!), или хуже, в зависимости от того, что вы делаете с каждой перестановкой), к сожалению, ничто, что вы не можете сделать, не изменит этот факт.

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

Я задал этот вопрос на Math Overflow и получил ответ на такой простой вопрос. Один из пользователей пожалел меня и сказал, что если я выложу его в Искусство решения проблем , он ответит на него; так я и сделал.

Вот ответ, который он опубликовал:
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1741600#1741600

Смущающе, моя математика-фу неадекватна, чтобы понять, что он разместил (парень 19 лет... что так удручает). Мне действительно нужно пройти некоторые занятия по математике.

С яркой стороны уравнение рекурсивно, поэтому должно быть простым делом превратить его в рекурсивную функцию с несколькими строками кода, кем-то, кто понимает математику.

Алгоритм случайной тасовки Кнута заслуживает изучения.

// In-place shuffle of char array
void shuffle(char array[], int n)
{
    for ( ; n > 1; n--)
    {
        // Pick a random element to move to the end
        int k = rand() % n;  // 0 <= k <= n-1  

        // Simple swap of variables
        char tmp = array[k];
        array[k] = array[n-1];
        array[n-1] = tmp;
    }
}

Я хотел бы до секунды Ответ Permaquid . Алгоритм, который он ссылается на принципиально по-разному из различных алгоритмов перечисления перестановок, которые были предложены. Он не генерирует все перестановки N объектов N, он генерирует различную специфическую перестановку, учитывая целое число между 0 и N! -1 . Если вам нужна только определенная перестановка, намного быстрее, чем их все, а затем выбирают один.

Даже если вам нужны все перестановки, он предоставляет варианты, которые не используют алгоритм перечисления перестановок. Однажды я написал крепильник Cryptarithm Brute-Force, который попробовал все возможное назначение букв в цифры. Для База-10 Проблемы, это было адекватно, поскольку есть только 10! Перестановки, чтобы попробовать. Но для базы-11 проблемы заняли пару минут и базы-12 проблемы заняли почти час.

Я заменил алгоритм переключения перестановок, который я использовал с простым I = 0-- N-1 для цикла, используя цитал алгоритма Permaquid. Результат был только немного медленнее. Но затем я разделился целочисленный диапазон в кварталах, и одновременно провел четыре петля, каждый из которых в отдельном потоке. На моем четырехъядерном процессоре полученная программа пробежала почти в четыре раза быстро.

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

Я не Подумайте, что это лучше, но он работает и не использует рекурсию:

#include <iostream>
#include <stdexcept>
#include <tr1/cstdint>

::std::uint64_t fact(unsigned int v)
{
   ::std::uint64_t output = 1;
   for (unsigned int i = 2; i <= v; ++i) {
      output *= i;
   }
   return output;
}

void permute(const ::std::string &s)
{
   using ::std::cout;
   using ::std::uint64_t;
   typedef ::std::string::size_type size_t;

   static unsigned int max_size = 20;  // 21! > 2^64

   const size_t strsize = s.size();

   if (strsize > max_size) {
      throw ::std::overflow_error("This function can only permute strings of size 20 or less.");
   } else if (strsize < 1) {
      return;
   } else if (strsize == 1) {
      cout << "0 : " << s << '\n';
   } else {
      const uint64_t num_perms = fact(s.size());
      // Go through each permutation one-by-one
      for (uint64_t perm = 0; perm < num_perms; ++perm) {
         // The indexes of the original characters in the new permutation
         size_t idxs[max_size];

         // The indexes of the original characters in the new permutation in
         // terms of the list remaining after the first n characters are pulled
         // out.
         size_t residuals[max_size];

         // We use div to pull our permutation number apart into a set of
         // indexes.  This holds what's left of the permutation number.
         uint64_t permleft = perm;

         // For a given permutation figure out which character from the original
         // goes in each slot in the new permutation.  We start assuming that
         // any character could go in any slot, then narrow it down to the
         // remaining characters with each step.
         for (unsigned int i = strsize; i > 0; permleft /= i, --i) {
            uint64_t taken_char = permleft % i;
            residuals[strsize - i] = taken_char;

            // Translate indexes in terms of the list of remaining characters
            // into indexes in terms of the original string.
            for (unsigned int o = (strsize - i); o > 0; --o) {
               if (taken_char >= residuals[o - 1]) {
                  ++taken_char;
               }
            }
            idxs[strsize - i] = taken_char;
         }
         cout << perm << " : ";
         for (unsigned int i = 0; i < strsize; ++i) {
            cout << s[idxs[i]];
         }
         cout << '\n';
      }
   }
}

Веселая вещь в этом заключается в том, что единственное состояние, которое он использует от перестановки к перестановке, является числом перестановки, общее количество перестановок и исходная строка. Это означает, что его можно легко инкапсулировать в итераторе или что-то в этом роде, без необходимости осторожно сохранить точное правильное состояние. Это может быть даже случайным доступом итератором.

Конечно :: std :: next_permution хранит состояние в отношениях между элементами, но это означает, что он не может работать над неупорядоченными вещами, и мне очень удивляются, что он делает, если у вас есть две равные вещи в последовательности. Вы можете решить, что постановляя индексы, конечно, но это добавляет немного больше осложнений.

Мой будет работать с любым произвольным доступом итераторным диапазоном, если достаточно коротко. И если это не так, вы никогда не пройдете все перестановки.

Основная идея этого алгоритма заключается в том, что каждая перестановка N элементов может быть перечислена. Общее число n! или факт (n) . И любая данная перестановка может рассматриваться как отображение источников из исходной последовательности в набор индексов назначения в новой последовательности. После того, как у вас есть перечисление всех перестановок, единственное, что осталось сделать, это сопоставить каждый номер перестановки в фактическую перестановку.

Первый элемент в раздвоенном списке может быть любой из N элементов из исходного списка. Второй элемент может быть любым из оставшихся элементов N - 1 и так далее. Алгоритм использует оператор % , чтобы разделить номер перестановки в набор выборов этой природы. Сначала это модуло номер перестановки, чтобы получить номер из [0, n). Он отбрасывает остаток, разделяя на N, то он модуль это по размеру списка - 1, чтобы получить число из [0, N-1) и так далее. Это то, что делает для (i = цикла.

Второй шаг переводит каждое число в индекс в исходный список. Первый номер прост, потому что это просто прямой индекс. Второй Номер - это индекс в списке, который содержит каждый элемент, но один удален при первом индексе и так далее. Это то, что делает цикл для (O = .

остатки Список индексов в последовательно мелкие списки. IDXS - это список индексов в исходном списке. Существует одно-одно сопоставление между значениями в остатках и IDXS . Каждый из них представляет собой одинаковое значение в разных «координатных пространствах».

ответ, указанный на ответом, вы выбрали, имеет одинаковую основную идею, но имеет гораздо более элегантный способ выполнения картографирования, чем мой скорее буквальный метод грубой силы. Таким образом будет немного быстрее, чем мой метод, но они оба примерно одинаковой скорости, и они оба имеют Такое же преимущество случайного доступа к пространству перестановки, которое облегчает целое количество вещей, в том числе (как ответ вы выбрали указанные) параллельные алгоритмы.

Настоящее пост: http://cplusplus.co.il/2009/11/14/ruumerating-permutations/ имеет дело с просьбой о чем угодно, а не только струны. Сам пост и комментарии ниже довольно информативны, и я не хотел бы копировать и вставить ..

Хотите пропустить все перестановки или посчитать количество перестановок?

Для первой, используйте std::next_permutation, как предлагали другие. Каждая перестановка занимает O(N) время (но менее амортизированное) и не требует памяти, кроме кадра вызова, времени O(N) и O(N) памяти для вашей рекурсивной функции. Весь процесс - O(N!), и вы не можете сделать лучше этого, как говорили другие, потому что вы не можете получить от программы больше, чем O(X), за время менее O(X)! Во всяком случае, без квантового компьютера.

Для последнего вам просто нужно знать, сколько уникальных элементов в строке.

big_int count_permutations( string s ) {
    big_int divisor = 1;
    sort( s.begin(), s.end() );
    for ( string::iterator pen = s.begin(); pen != s.end(); ) {
        size_t cnt = 0;
        char value = * pen;
        while ( pen != s.end() && * pen == value ) ++ cnt, ++ pen;
        divisor *= big_int::factorial( cnt );
    }
    return big_int::factorial( s.size() ) / divisor;
}

Скорость ограничена операцией поиска дублирующих элементов, что для chars может быть сделано во времени O(N) с помощью поисковой таблицы.