алгоритм комбинаций - PullRequest
Новая
       22

алгоритм комбинаций

5 голосов
/ 24 марта 2010

Я хочу сделать простой алгоритм сортировки.

с учетом ввода "abcde", я хотел бы вывод ниже.не могли бы вы рассказать мне алгоритм для этого? 

arr[0] = "a"
arr[1] = "ab"
arr[2] = "ac"
arr[3] = "ad"
arr[4] = "ae"
arr[5] = "abc"
arr[6] = "abd"
arr[7] = "abe"
...
arr[n] = "abcde"

arr[n+1] = "b"
arr[n+2] = "bc"
arr[n+3] = "bd"
arr[n+4] = "be"
arr[n+5] = "bcd"
arr[n+5] = "bce"
arr[n+5] = "bde"
...
arr[n+m] = "bcde"
...
...

Ответы [ 3 ]

7 голосов
/ 24 марта 2010

Алгоритм "генерации Power Set" из массива - это то, что вы ищете. Вы можете попробовать Google или другую поисковую систему, чтобы найти алгоритм, который наилучшим образом соответствует вашим потребностям.

6 голосов
/ 24 марта 2010

В C ++ задана следующая процедура: 

template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Mark Nelson http://marknelson.us */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator i1 = first;
   Iterator i2 = last;
   ++i1;
   if (last == i1)
      return false;
   i1 = last;
   --i1;
   i1 = k;
   --i2;
   while (first != i1)
   {
      if (*--i1 < *i2)
      {
         Iterator j = k;
         while (!(*i1 < *j)) ++j;
         std::iter_swap(i1,j);
         ++i1;
         ++j;
         i2 = k;
         std::rotate(i1,j,last);
         while (last != j)
         {
            ++j;
            ++i2;
         }
         std::rotate(k,i2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

Затем вы можете выполнить следующее: 

std::string s = "abcde";
for(std::size_t i = 1; i != s.size(); ++i)
{
   do
   {
      std::cout << std::string(s.begin(),s.begin() + i) << std::endl;
   }
   while(next_combination(s.begin(),s.begin() + i,s.end()));
}

Примечание: следует ожидать 2 ^ n-1 комбинаций, где n - длина массива или строки.

5 голосов
/ 24 марта 2010

Вы описываете блок питания . Вот некоторый код C ++: 

#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;

vector< string > string_powerset( string const &in ) {
    vector< string > result(1); // start output with one empty string
    result.reserve( 1 << in.size() ); // output size = 2^( in.size() )
    if ( result.capacity() != 1<<in.size() ) throw range_error( "too big" );

    for ( string::const_iterator it = in.begin(); it != in.end(); ++ it ) {
        size_t middle = result.size(); // duplicate what we have so far
        result.insert( result.end(), result.begin(), result.end() );

          // append current character onto duplicated output
        for_each( result.begin() + middle, result.end(),
           bind2nd( mem_fun_ref( &string::push_back ), * it ) );
    }
    return result;
}

Проверенные рабочие: v). Проверка дальности не самая лучшая, но все равно.

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

РЕДАКТИРОВАТЬ: Я написал next_subset ответ , и это не похоже на Бен.

...