[comp.sources.wanted] 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);
	}

}