I am new to C++ and programming in general. (Only 1 years experience with python and some perl)
I wrote a program that creates all possible words using the character set (char_set) = 'abcdefghijklmnopqrstuvwxyz' from a word length of 1 to a word length of 5.
x1 = 0
x2 = 0
It first takes char_set[x1] and sets that to the variable word. Then adds 1 to x1. Then repeats. Then once x1 == the length of char_set, it adds a new letter to the word. So word now equals char_set[x1]+char_set[x2] and repeats.
Combinations is a common problem but not exactly a trivial one! Took me a bit to figure out where to start.
Instead of making if-statements 9 levels deep (that's never efficient!) I'd keep a list of what I'm still allowed to use instead. No doublethink needed if incorrect values aren't still around to grab. Also, an array of what order to grab things in which you can update as you go, and stop when it goes past the end.
Writing this with C++ strings will be much less efficient than C-strings. By treating a C-string like an array we can do, often with single instructions, what C++ would need entire function calls to do.
Code:
#include <stdio.h>
#include <string.h>
int main(void)
{
// String of what letters can be used for input.
// The program doesn't need this hardcoded a-z, you could do
// 0-9 and it ought to still work.
unsigned char *charset= "abcdefghijklmnopqrstuvwxyz";
// What letters have already been used.
// 0,0,0,0,0 means always pick the first letter, whatever it may be.
// By removing it from the input set, we guarantee 0,0,... won't
// actually pick duplicates.
int chosen[16]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int running=1; // Set this to 0 to stop the main loop
// Might as well count combinations while we're at it
// We use an unsigned long int since the count could be really huge.
unsigned long int loopcount=0;
// Remember the length of the set, so we don't have to count again
const int maxpos=strlen(charset);
// How long an output string do we want?
// can be a maximum of 16 in this implementation)
const int outlen=5;
while(running) // Keep going until we're told to stop.
{
// Just a counter for loops.
int pos;
// A blank C-string, the current set of allowed characters.
char ltrs[64];
// A blank C-string, the current output string.
char out[17];
// Fill the input set, ltrs, with a-z.
strcpy(ltrs, charset);
loopcount++; // Count another loop.
// Create the output string character by character by setting
// out[0], out[1], ..., out[outlen-1]. Then finishing with
// out[outlen]='\0' to NULL-terminate it as a proper C-string.
for(pos=0; pos<outlen; pos++)
{
// Add the chosen letter to the output string.
out[pos]=ltrs[ chosen[pos] ];
// Remove the character from the input set.
// We do this by replacing it by the
// char at the end, and shrinking by one.
ltrs[ chosen[pos] ] = ltrs[ maxpos-(pos+1) ];
ltrs[ maxpos-(pos+1) ] = '\0';
}
out[outlen]='\0';// NULL-terminate it so we can print it
printf("%s\n", out);
// Advance to the next combination.
for(pos=0; pos<outlen; pos++)
{
// Pick one letter ahead.
chosen[pos]++;
// Are we beyond the max? letter 0 can choose
// 0-25, letter 1 can choose 0-24, etc, etc.
if(chosen[pos] >= (maxpos - pos))
{
// If we are, reset it to 0 and advance
// the next chosen character.
chosen[pos]=0;
// Out of digits! We are finished.
if(pos == (outlen - 1))
{
running=0;
break;
}
else
{
// We must advance the next
// digit. while loop keeps going
continue;
}
}
// This digit didn't overflow? stop the loop, we're done.
break;
}
}
// print to stderr instead of stdout, so we can pipe or redirect stdout
// and still see the combination count.
fprintf(stderr, "%lu combinations\n", loopcount);
return(0);
}
It run through all 7,893,600 combinations in 1.3 seconds on my 2.3GHz Athlon64, and I've proven all outputs are unique like so:
A quick update since I slightly misread your original problem. I had it generate strings of 1-5 characters by putting outlen in a for-loop.
Code:
#include <stdio.h>
#include <string.h>
int main(void)
{
// String of what letters can be used for input
unsigned char *charset= "abcdefghijklmnopqrstuvwxyz";
// Might as well count combinations while we're at it
unsigned long int loopcount=0;
// We need this in order to shrink the list efficiently
const int maxpos=strlen(charset);
// How long an output string do we want?
// can be a maximum of 16 in this implementation)
int outlen;
for(outlen=1; outlen<=5; outlen++)
{
// Set this to 0 to stop the main loop
int running=1;
// What letters have already been used.
// Every time outlen changes, we blank it to all zeros.
int chosen[16]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
while(running)
{
// Just a counter for loops.
int pos;
// A blank C-string, the current set of allowed characters.
char ltrs[64];
// A blank C-string, the current output string.
char out[17];
// Fill the output set with a-z.
strcpy(ltrs, charset);
loopcount++; // Count another loop.
// Generate the output string char by char.
// out[0]=x, out[1]=y, ...out[outlen-1]=q,
// out[outlen]='\0'
for(pos=0; pos<outlen; pos++)
{
// Add the chosen letter to the output string
out[pos]=ltrs[ chosen[pos] ];
// Remove the character from the input set.
// We do this by replacing it by the
// char at the end, and shrinking by one.
ltrs[ chosen[pos] ] = ltrs[ maxpos-(pos+1) ];
ltrs[ maxpos-(pos+1) ] = '\0';
}
out[outlen]='\0';// NULL-terminate it so we can print it
printf("%s\n", out);
// Advance to the next combination.
for(pos=0; pos<outlen; pos++)
{
// Pick one letter ahead.
chosen[pos]++;
// Are we beyond the max? letter 0 can choose
// 0-25, letter 1 can choose 0-24, etc, etc.
if(chosen[pos] >= (maxpos - pos))
{
// If we are, reset it to 0 and advance
// the next chosen character.
chosen[pos]=0;
// Out of digits! We are finished.
if(pos == (outlen - 1))
{
running=0;
break;
}
else
{
// We must advance the next
// digit. while loop keeps going
continue;
}
}
// No overflowing digits? We're done.
break;
}
}
}
fprintf(stderr, "%lu combinations\n", loopcount);
return(0);
}
The result is 8,268,676 combinations, which doesn't take much longer at all to do.
Last edited by Corona688; 10-25-2010 at 03:10 PM..
Reason: removed redundant variable
