permute string program

Discussion in 'Programmer's Corner' started by nanobyte, Feb 23, 2014.

  1. nanobyte

    Thread Starter Senior Member

    May 26, 2004
    118
    1
    I'm trying to create a function with c++ that will show the permutes of a string of 3 chars. If I input a string with 3 unique chars the output is right for the first 3 permutes, but the last 3 are permutes that don't have all 3 chars. Instead the last 3 permutes are strings where one of the chars is repeated like below:

    Enter a string: cat
    cat
    act
    atc
    att
    att
    tat

    The code of the function is below. Could someone point me in the right direction?

    Code ( (Unknown Language)):
    1. void permute_string(){
    2.     char swap1;
    3.     char swap2;
    4.     int a=0;    //Points to 1st char being swapped
    5.     int b=1;    //Points to 2nd char being swapped
    6.     int n=3;
    7.     int swap_count=0;    //keeps tracks position changes a char in has done
    8.     int char_count=0;    //keeps tracks of char in the original string is being used
    9.     char givenchars[3];
    10.     char acopy[3];   // a duplicate of the original user input
    11.  
    12.     cout<<"Enter a string: ";
    13.     for(int i=0; i<3; i++){
    14.         cin>>givenchars[i]; //Store original string input into array.
    15.         acopy[i] = givenchars[i]; //copies original string input into a backup
    16.  
    17.     }
    18.  
    19.     while(char_count<3){
    20.             cout<<givenchars[0]<<givenchars[1]<<givenchars[2]<<endl;
    21.  
    22.             swap1=givenchars[a];
    23.             swap2=givenchars[b];
    24.  
    25.             //switch order
    26.             givenchars[a]=swap2;
    27.             givenchars[b]=swap1;
    28.  
    29.  
    30.             if(swap_count<n){
    31.                 swap_count++;
    32.                 a++;
    33.                 b++;
    34.             }
    35.             else{
    36.                    n--;
    37.                 a=0;
    38.                 b=1;
    39.                 char_count++;
    40.             }
    41.  
    42.     }
    43.  
    44.  
    45.  
    46. }[/b][/b][/i][/i][/i]
     
  2. MrChips

    Moderator

    Oct 2, 2009
    12,431
    3,360
    Your code attempts to switch characters at index a and b.
    1st time a = 0, b = 1.
    2nd time a = 1, b = 2.
    3rd time a = 2, b = 3.
    But the character at b = 3 has not been defined.
     
  3. WBahn

    Moderator

    Mar 31, 2012
    17,720
    4,788
    One of the most effective ways to debug code is to pretend that you are the processor and execute the program as it is written. Take a piece of paper and list the variables on it and keep track of the values in each variable at each step. Just be sure to do exactly what the instructions say and not what you wanted them to say.
     
  4. nanobyte

    Thread Starter Senior Member

    May 26, 2004
    118
    1
    The permutation of n is n! Where permutations of n = n(n-1)(n-2).... For a string 2 or 3 chars long the function works fine. When the string is > 3 the function doesn't give all the permutations, only the product of the first two integers. An example output is below. To avoid confusion the last output is the number of permutations displayed, not a permutation itself.

    Enter a string: 1234
    1234
    2134
    2314
    2341
    3241
    3421
    3412
    4312
    4132
    4123
    1423
    1243
    12

    It giving 4x3=12, not the correct 4!=4x3x2x1=24. Any suggestions? Current code is:

    Code ( (Unknown Language)):
    1. void permute_string(int string_size){
    2.     char swap1;
    3.     char swap2;
    4.     int a=0;    //Points to 1st char being swapped
    5.     int b=1;    //Points to 2nd char being swapped
    6.     int n=string_size-1;    //The last element of the array
    7.  
    8.     int char_count=0;    //keeps tracks of char in the original string is being used
    9.     int permutes=0;    //Counts how many permutations have been displayed for the string
    10.     //int swaps=string_size;    //Keeps track of how times a char has been switched place with other chars in the string
    11.     char givenchars[string_size];
    12.     char acopy[string_size];   //a duplicate of the original user input
    13.  
    14.     cout<<"Enter a string: ";
    15.     for(int i=0; i<string_size; i++){
    16.         cin>>givenchars[i]; //Store original string input into array.
    17.         acopy[i] = givenchars[i]; //copies original string input into a backup array
    18.  
    19.     }
    20.  
    21.     while(char_count<string_size){
    22.         for(int i=0; i<string_size; i++){
    23.             cout<<givenchars[i];
    24.         }
    25.         cout<<endl;
    26.  
    27.         permutes++;
    28.  
    29.             swap1=givenchars[a];
    30.             swap2=givenchars[b];
    31.  
    32.             //switch order
    33.             givenchars[a]=swap2;
    34.             givenchars[b]=swap1;
    35.  
    36.             if(b<n){
    37.                 a++;
    38.                 b++;
    39.             }
    40.             else{
    41.                 a=0;
    42.                 b=1;
    43.                 char_count++;
    44.             }
    45.  
    46.     }
    47.     cout<<permutes;
    48. }[/b][/b][/i][/i][/i][/i]
     
Loading...