Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!bagate!dsinc!unix.cis.pitt.edu!zaphod.mps.ohio-state.edu!julius.cs.uiuc.edu!apple!uokmax!munnari.oz.au!metro!cluster!ultima!fidogate
From: jeremy.kothe@f1000.n711.fido.oz.au (Jeremy Kothe)
Newsgroups: comp.lang.c
Subject: Re: STRING GENERATION/COMBINAT
Message-ID: <18596@ultima.socs.uts.edu.au>
Date: 7 Nov 90 10:33:00 GMT
Sender: fido@ultima.socs.uts.edu.au
Organization: A Fidonet node, gated through ultima.socs.uts.edu.au
Lines: 64

Original to: anigbogu@loria.crin.fr
>        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.
>                worb
>                word
>                ward
>                warb

Give this 'un a go. It's a little raw, but it works, no dupes.

void genstrs(char *str1, char *str2)
{
   int column,wordno;
   int rlen=0;              /* "real" length - length minus common letters */
   int len=0;              /* length of words */
   int nwords;            /* number of words to generate (calculated) */
   int repval;
   char *answers;       /* area of mem to put answers in */

   for (len=0 ; (str1[len] && str2[len]) ; len++)        /*  calcs len &  */
      rlen+=(str1[len] != str2[len]);                  /*  rlen         */

   answers=malloc((nwords=1<<rlen)*(++len));      /* gets mem for answers */

   repval=nwords>>1;  /* initialise repeat value to half the no. of words */

   for (column=0;column<len;column++)               /* loops thru columns */
   {
      char ch=str1[column];                    /* initialise repeat value */

      if (str1[column] == str2[column])   /*  if letter common, set this  */
      for (wordno=0 ; wordno<nwords ; wordno++)       /*  column in all  */
         answers[(len*wordno)+column]=str1[column]; /*  words the same  */
      else
      {
         for (wordno=0 ; wordno<=nwords ; wordno++)  /*  else loop thru  */
         {                                          /*  words           */
            answers[wordno*len+column]=ch;

            if (((wordno+1) % repval)==0)        /* changing source  */
            {                                   /* words when nec.  */
               if (ch==str1[column]) ch=str2[column];
               else ch=str1[column];
            }

         }
         repval>>=1;               /* for next column, halve repeat value */
      }
   }

   for (wordno=0 ; wordno<nwords ; wordno++)     /*  and, finally,     */
      printf("%s\n",answers+(len * wordno));   /*  print the results. */
}


               Jeremy Kothe



.ORIGIN: 302/021
--- PreMail GT Gate v0.91 
 * Origin: From GTnet via the Black Hole Star Gate! (3:711/1000)