C - Генерация всех возможностей X символов слова

Question

РЕДАКТИРОВАТЬ: я имел в виду перестановки, а не комбинации. Спасибо.

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

Не совсем уверен, с чего бы мне начать, возможно, использование хеш-таблицы? Конечно, понадобятся петли, но я не уверен, как их конструировать, чтобы создавать комбинации. Вплоть до настоящего момента, например, всегда происходило зацикливание, пока не произошло 1000 вещей.

Любой совет очень ценится!

Приветствия

Т.

Answer 1

Для перестановок вы можете использовать рекурсивное решение, подобное этому (которое, вероятно, можно оптимизировать и улучшить):

unordered_set<string> permute_string(int n) {    
    static const char chars[] = {
        'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
        'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'
    };

    unordered_set<string> s;

    if (n == 0) {
        s.insert("");

        return s;
    }

    unordered_set<string> perms = permute_string(n - 1);

    for (auto c = std::begin(chars); c < std::end(chars); ++c)
        for (auto i = perms.begin(); i != perms.end(); ++i)
            for (int pos = 0; pos < n; ++pos)
                s.insert(string(*i).insert(pos, 1, *c));

    return s;
}

Обратите внимание, что вывод этой функции (независимо от того, как вы ее реализуете) равен 26 ⁿ , что составляет 456 976, когда n (вход для этой функции) равен 4.

Answer 2

Вот полное и рабочее решение, которое я только что преобразовал в C ++ из документации по методу python itertools.permutations. http://docs.python.org/library/itertools.html#itertools.permutations. В исходной форме Python это генератор (просто подумайте итератор), но я не стал сейчас этим заниматься, хотя это имело бы большой смысл.

Метод перестановок - это шаблон, поэтому он работает с любым объектом, который вы можете сохранить в векторе, а не только с символом. С этим кодом:

vector<char> alphab={'a','b','c','d'};
auto perms=permutations(alphab,3);'

результатом является вектор 'vector', представляющий все неповторяющиеся 3-комбинации abcd:

abc abd acb acd adb adc bac bad bca bcd bda bdc
cab cad cba cbd cda cdb dab dac dba dbc dca dcb 

Вот код (C ++ 11):

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

size_t nperms(size_t n,size_t k){
   if(k<=0) return 1; // one empty set
   if(k>n) return 0;  // no possible ways
   size_t out=1;
   for (size_t i=n-k+1;i<=n;i++) out*=i;
   return out;
}

template<class T>
vector<T > permutations(T & iterable, size_t r=-1){    
   vector<T> out;
   T & pool = iterable;
   size_t n = pool.size();
   r = r>=0 ? r : n;
   if (r > n)
      return out;
   vector<size_t> indices;
   for (size_t i=0;i<n;++i) indices.push_back(i);
   vector<size_t> cycles;
   for (size_t i=n;i>(n-r);--i) cycles.push_back(i);

   vector<typename T::value_type> line; //e.g. vector of char
   line.reserve(r);

   for (size_t i=0;i<r;++i)
      line.push_back(pool[i]);
   out.reserve(nperms(n,r));    
   // first permutation:
   out.push_back(line);   
   while (1){
     bool done=1;
     for (size_t irev=0;irev<r;++irev){
       size_t i=r-1-irev;
       cycles[i] -= 1;
       if(cycles[i] == 0){
         // cycle upper part one step
         rotate(begin(indices)+i,begin(indices)+i+1,end(indices));
         cycles[i] = n-i;
       }else{
         int j = cycles[i];
         swap(indices[n-j],indices[i]);         
         for (size_t k=0;k<r;++k)
           line[k]=pool[indices[k]];
         out.push_back(line);
         done=0;
         break ;
       }
     }
     if(done) break;
   }
   return out;
}    
int main(){

   vector<char> alphab={'a','b','c','d'};
   auto perms=permutations(alphab,3);

   // print:
   cout <<"perms of size " <<perms.size()<<endl;
   for (auto &i : perms){
      for (auto &j : i){
     cout << j<<"";
      }
      cout <<" ";
   }
   cout <<endl;
   return 0;
}

Как примечание:

Алфавит не проверяется на уникальность, вместо этого перестановки и выборки делаются по индексу, поэтому, если вы хотите разрешить использование более одного объекта, просто добавьте его в алфавит. Содержание также не должно быть сопоставимым.

Answer 3

Да, это в значительной степени требует рекурсивного решения.Чтобы сгенерировать все слова длиной N, базовый алгоритм:

pick the next letter from the alphabet
  generate all N-l-length words starting with that letter    

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

Важный вопрос: вы уверены, что хотите использовать все возможные комбинации всех символов ASCII (включая знаки пунктуации, управляющие символы и т. Д.)?Или все возможные комбинации буквенно-цифровых строк?Или строго алфавитные строки?

Возможно, вы захотите указать свой алфавит в своем коде, например

char alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

, и просто индексировать его вместо того, чтобы предполагать представление конкретного символа:

char *p;
for (p = alphabet; *p != 0; p++)
  // generate all words starting with *p

Answer 4

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