C - Generating all possibilities of X character wo

Question

EDIT: I meant Permutations, not combinations. Thanks.

I realize this is a rather open ended question, and I'm not looking for code per say, but really some hints where to start. What I want to make is a program, that can generate every combination of characters for a given length, i.e the user inputs 4, and the program will generate every possible combination of ASCII characters for a length of 4.

Not really sure where I would start, perhaps the use of a hash table? Of course loops will be needed but I'm unsure how to design them to produce combinations. Up until now, its always been a case of, loop until 1000 things have happened for example.

Any advice is much appreciated !

Cheers,

T.

Answer 1

Yeah, this pretty much calls for a recursive solution. To generate all N-length words, the basic algorithm is

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

If all you need to do is print these strings out to a file or something as you generate them, then you don't need any kind of complicated data structure. All you need is a single buffer to hold the generated word.

Important question: are you sure you want every possible combination of all ASCII characters (including punctuation, control characters, etc.)? Or all possible combinations of alhphanumeric strings? Or strictly alphabetic strings?

You might want to specify your alphabet in your code, like

char alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

and just index into that instead of assuming a particular character representation:

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

Answer 2

For permutations, you can use a recursive solution like this (which can probably be optimised and improved):

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;
}

Note that the output of this function (no matter how you implement it) is 26ⁿ, which is 456,976 when n (the input for this function) is 4.

Answer 3

Here's a complete and working solution I just converted to C++ from the documentation of the python method itertools.permutations. http://docs.python.org/library/itertools.html#itertools.permutations . In the original python form it's a generator (just think iterator) but I did not bother with that now although it would make a lot of sense.

The permutations method is a template so this works with any object you can store in a vector, not just char. With this code:

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

the result is a vector of 'vector' representing all the non-repeating 3-combinations of 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 

Here's the code (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;
}

As a note:

The alphabet is not checked to be unique, instead the permutations and selections are done by index so if you want to allow for more than one of an object just add more of it to the alphabet. The contents need also not be comparable.

Answer 4

Your question is too general. Any how, you could use the trie data structure to get what you want. But if you are going to do it in c it would still require a lot of work. I would suggest use a language where in you don't have to recreate the wheel.