Sponsored Content
Full Discussion: C++ help
Top Forums Programming C++ help Post 302466116 by Corona688 on Monday 25th of October 2010 01:44:29 PM
Old 10-25-2010
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:

Code:
$ ./a.out | sort -u | wc -l
7893600 combinations
7893600
$

..if there were any duplicates, 'sort -u' would have removed them and reduced the count from wc -l.

Last edited by Corona688; 10-25-2010 at 02:58 PM.. Reason: more comments igor!
 
All times are GMT -4. The time now is 07:53 AM.
Unix & Linux Forums Content Copyright 1993-2022. All Rights Reserved.
Privacy Policy