Permutation excitation

This is a discussion on Permutation excitation within the C Programming forums, part of the General Programming Boards category; Hi. I've been trying to write something which would output every permutation of a group of chars.... Code: #include <stdio.h> ...

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    98

    Permutation excitation

    Hi.

    I've been trying to write something which would output every permutation of a group of chars....

    Code:
    #include <stdio.h>
    
    static void perm( char *, char * );
    static char * extract_letter( char *, int );
    
    int
    main( int argc, char *argv[] )
    {
      char word[5] = { 'a', 'b', 'c', 'd', 0 };
    
      perm( "", word );
    
      printf( "\n\n" );
    
      return(0);
    }
    
    static void
    perm( char *input,
          char *pool )
    {
      char output[5] = "";
      int ctr, target;
    
      strcat( output, input );
      target = strlen( output );
    
      for( ctr = 0 ; ctr < strlen( pool ) ; ctr++ )
      {
        output[target] = pool[ctr];
        perm( output, extract_letter( pool, ctr ));
      }
    
      printf( "\n%s", output );
    }
    
    
    static char *
    extract_letter( char *word, int letter )
    {
      int ctr;
      char *str;
    
      str = (char *) malloc( strlen( word ) - 1);
    
      for( ctr = 0 ; ctr < letter ; ctr++ )
        str[ctr] = word[ctr];
    
      for( ctr = letter ; ctr < strlen( word ) ; ctr++ )
        str[ctr] = word[ctr+1];
    
      return( str );
    }
    So far, it seems to work, but it actually outputs some of the permutations more than once. Surprise, surprise, I'm actually struggling to follow my own code!!

    Does anyone have any comments on the method, or can explain the duplicate outputs...

    Thanks

  2. #2
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    If your method succesfully creates a list of permutations, then all you need do, is check all previous permutations for the current one you've just created. If you already output it once, don't do it again.

    There are various ways to do this, maybe using a simple array, or a form of list/tree.

    BTW, you forgot:
    #include <string.h>
    #include <stdlib.h>
    and free() for all those malloc()'s.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. bit level permutation function
    By zxcv in forum C Programming
    Replies: 2
    Last Post: 07-27-2008, 02:26 PM
  2. Problem creating a recursive string permutation function
    By indigo0086 in forum C++ Programming
    Replies: 4
    Last Post: 10-10-2006, 11:09 AM
  3. Permutation algorithm??
    By lris2005 in forum C++ Programming
    Replies: 1
    Last Post: 04-01-2006, 06:51 AM
  4. Permutation Calculation
    By Eric Hansen in forum C++ Programming
    Replies: 21
    Last Post: 06-11-2003, 05:03 PM
  5. INT ARRAY Permutation!
    By arthur5005 in forum C++ Programming
    Replies: 2
    Last Post: 10-21-2002, 06:30 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21