[comp.lang.c] String Generation/Combination

anigbogu@loria.crin.fr (Julian Anigbogu) (10/24/90)

Dear Netters, I have a little problem and was wnadering if any of you has 
already solved an identical one. Here goes:
	Given two 2 equal length strings, say L, I would like to generate all
possible strings of length L. (2^L strings). String uniqueness is not 
necessary but if the function eliminates duplicates as it generates, that'll
be a bonus.

	ex. "worb" and "ward" should  generate
		worb
		word
		ward
		warb
		...
If you have a solution, I'd love to hear from you and in this newsgroup or by
email. Thanks in advance.

Julian
-- 
				---------------------------------------
e-mail:	anigbogu@loria.crin.fr 	| All opinions expressed here are      |
				|  naturally mine. However ...         |
				----------------------------------------

kohli@gemed (Jim Kohli) (10/26/90)

In article <2836@loria.crin.fr>, anigbogu@loria.crin.fr (Julian Anigbogu)
asks:
>Dear Netters, I have a little problem and was wnadering if any of you has 
>already solved an identical one. Here goes:
>	Given two 2 equal length strings, say L, I would like to generate all
>possible strings of length L. (2^L strings). String uniqueness is not 
>necessary but if the function eliminates duplicates as it generates, that'll
>be a bonus.
>
>	ex. "worb" and "ward" should  generate
>		worb
>		word
>		ward
>		warb
>		...
>If you have a solution, I'd love to hear from you and in this newsgroup or by
>email. Thanks in advance.
>
>Julian
>e-mail:	anigbogu@loria.crin.fr 	| All opinions expressed here are      |

yes, I have done something very similar to what you want.  you
may want to substitute something more meaningful for the word
"anigbogu" which describes this process.

#include <stdio.h>
/*
	this program will present all possible alternatives for the
	two alternatives of letters in two words.  it assumes the
	words will have less than 32 characters different.

	jim kohli
	GE Medical Systems
*/
#define NBITS 32

static int indices[NBITS];

#define ZOR1(n) ( n ? 1 : 0 )

main( argc, argv )
int argc;
char **argv;
{
int i;
int n,ndiff=0;
unsigned long index;
char alternatives[2][NBITS];
char *final_product;

if( argc != 3 ) {
	fprintf( stderr, "Usage: %s word1 word2, to anigbogu words\n", argv[0]);
	exit( 1 );
	}

if( (n = strlen( argv[1] )) != strlen(argv[2]) ) {
	fprintf( stderr, "The arguments to %s must be of the same length\n",
		argv[0] );
	exit( 2 );
	}

for( i=0 ; (i<n)&&(ndiff<NBITS) ; i++ ) if( argv[1][i] != argv[2][i] ) {
	alternatives[0][ndiff] = argv[1][i];
	alternatives[1][ndiff] = argv[2][i];
	indices[ndiff] = i;
	ndiff++;
	}

if( ndiff > NBITS ) {
	fprintf( stderr, "The arguments to %s must be < 32 chars long\n",
		argv[0] );
	exit( 3 );
	}

if( !strcmp( argv[1], argv[2] ) ) {
	fprintf( stderr, "%s and %s can't be anigbogued because they're the
same\n",
		argv[1], argv[2] );
	exit( 4 );
	}

final_product = (char *)malloc( n+1 );

for( index=0 ; index < (1<<ndiff) ; index++ ) {
	strcpy( final_product, argv[1] );
	for( i=0 ; i<ndiff ; i++ )
		final_product[indices[i]] = alternatives[ZOR1(index & (1<<i))][i];
	printf("%s\n", final_product);
	}

}

anigbogu@loria.crin.fr (Julian ANIGBOGU) (10/26/90)

Thanks to all the people who responded with algorithms and programs.
I've tried to reply individually but at the same time send to the net
so I don't get more responses. 

Maybe I didn't frame the question correctly or did not give sufficient
information but I can guarantee you it wasn't a homework assignment.
It was for a character recognition problem where for each character
recognized their is an attached alias which can be identical or
different and so I thought it might be interesting to generate all
possible combinations. Only one Paul Hilfinger deduced from my
affiliation that it couldn't have been homework. Thanks Paul.

At the risk of calling down flames on my head, but I thought the net
was for the exchange of ideas. What's the use of re-inventing the
wheel if somebody has already solved an identical before you. I've had
occasions to send in my little contribution too. Although it's not
wise to solve student's homeworks for them, but it's a risk that's
worth taking otherwise genuine problems won't ever get solved.

Julian
-- 
				---------------------------------------
e-mail:	anigbogu@loria.crin.fr 	| All opinions expressed here are      |
				|  naturally mine. However ...         |
				----------------------------------------