Permutation

[hinduengg]

Hello once again . My teacher has given us the assignment to enter a string a maximum of 7 charecters and permute it.
Then print all of possible permutations . Like if the inputted word is
JAY so Output would be
JAY
AJY
AYJ
JYA
YAJ
YJA

I do not seem to understand how to go about it. Please help.
I wish to know about some initial logic before developing the right code.

Thank you in advance.
hinduengg

There's a few examples in the code snippets, some recursive some not.

There is also a function in the STL.

[Lerner]

Since this is probably a learning experience in how to manipulate data rather than scrounging the archives of the Standard Template Library, I would suggest you consider this:

Using the JAY example if you did this:

JAY
JYA
AJY
AYJ
YJA
YAJ

and note that you can get all permutations by taking each element of the original and combining it with each of the remaining elements in order. Each element could be an element of an array and then you could loop through the array starting each loop with a new element and using other loops to get the rest of the elements in order. This process lends itself quite nicely to the concept of nested loops, which I have little doubt was the subject of one of your classes, although as iamthwee indicates there are other ways of doing this.

[hinduengg]

Could you advice the link . I am not allowed to use stl strings its the char array that I need to use and functions related to it.
What I need is just the starting logic should I use for loops.

>should I use for loops

whatever works...

[ndeniche]

if you show us how far you have gone, it will be easier for us to help you

[hinduengg]

if you show us how far you have gone, it will be easier for us to help you

the concept is still in infancy development , I need your help:
this is so far I have developed the code:

#include<iostream>
int main()
{
  int c,y,m=0;
   int z,fact;
    char a[100];  
 for(y=0;a[y]!='\0';y++)
      c++;
     cout<<"the length"<<c<<endl;
    for(x=1;x<=c;x++)
     {
     fact=1;
     fact=fact*c;
     }
     cout<<"no of permutations"<<fact<<endl;
     for(int w=1;w<=fact;w++)
      for(int y=0;a[y]!='\0';y++)
      {
         m=y+1;
         cout<<a[m];
         }

I am unable to understand what to do to print permutations
and address index of the previous value of the string.

If you know what a flow chart is you better start drawing one.

#include <iostream>
int main()
{
   int c, y, m = 0;
   int z, fact;
   char a[100];
   for ( y = 0; a[y] != '\0'; y++ )
      c++;
   cout << "the length" << c << endl;
   for ( x = 1; x <= c; x++ )
   {
      fact = 1;
      fact = fact * c;
   }
   cout << "no of permutations" << fact << endl;
   for ( int w = 1; w <= fact; w++ )
      for ( int y = 0; a[y] != '\0'; y++ )
      {
         m = y + 1;
         cout << a[m];
      }
}

Address the parts in red...

[hinduengg]

this is the code that I actually got while browsing through code snippets

#include<iostream>
#include<cstring>

using namespace std;

void char_permutation(char str[],char append[])
{
  int length = strlen(str);
  if (length)
  {
    for(int i=0;i<length;++i)
    {
      char* str1 = new char[length+1];
      int cnt;
      int cnt2;
      for(cnt=0,cnt2=0; cnt<length; ++cnt,++cnt2)
      {
        if (cnt == i)
        {
          str1[cnt] = str[++cnt2];
          continue; 
        }
        else
          str1[cnt] = str[cnt2];
      }  
      str1[cnt] = '\0';
      
      int alength = strlen(append);
      char* append1 = new char [alength+2];// why adding 2 here
      strncpy(append1,append,alength);
      append1[alength] = str[i];
      append1[alength+1] = '\0';
      
      char_permutation(str1,append1);
      
      delete []str1;
      delete []append1; 
    } 
  }
  else
  {
    cout << append << endl; 
  }  
}


int main()
{
  char str[] = "BUSH";  // shows a little humor
  char append[] = "\0";  

  cout << "Original = " << str << endl;  
  char_permutation(str,append);
    cout << "Done ........" << endl;
    
    cin.get();  // wait
  return 0;
}

Please devote some of your precious time in making me understand this.:( My question is in the code comments , please,please tell the reason for that. Varunthai had understood it but he did not write any grain of logic for me to understand!:(

Till now I have understood that there are 2 strings on which permutation is working but the process of cnt cnt2 ,and statements like - char* append1 = new char [alength+2]; confuse me then.
please help:(

I would appreciate your help greatly

hinduengg

[darkscript]

The idea here is to make each character in the string exist in every position, for example:

string is "JOY"

so taking J:-
1st pass: "JOY"
2nd pass: "OJY"
3rd pass: "OYJ"

taking O:-
1st pass: "OJY"
2nd pass: "JOY"
3rd pass: "JYO"

taking Y:-
1st pass: "YOJ"
2nd pass: "JYO"
3rd pass: "JOY"

then remove the repeated results, and you'll get all the combinations for that string

[Killer_Typo]

The idea here is to make each character in the string exist in every position, for example:

string is "JOY"

so taking J:-
1st pass: "JOY"
2nd pass: "OJY"
3rd pass: "OYJ"

taking O:-
1st pass: "OJY"
2nd pass: "JOY"
3rd pass: "JYO"

taking Y:-
1st pass: "YOJ"
2nd pass: "JYO"
3rd pass: "JOY"

then remove the repeated results, and you'll get all the combinations for that string

great post.

actually gave me some ideas on how i would personally tackle this problem.

[Aia]

!!!!! WARNING YOUR COMPUTER MAY BE INFECTED WITH SPYWARE!!!! PAY AN OVER PRICED AMMOUNT TO HAVE SOMTHING FIXED WE PLACED THERE IN THE FIRST PLACE!!!!!!!!!

sound familiar, know how to block yourself and keep yourself clean.

I know how to keep myself clean since the time when my mother taught me how to do it. However I am not quite sure I ever learned how to block myself.

[WaltP]

The idea here is to make each character in the string exist in every position, for example:

string is "JOY"

so taking J:-
1st pass: "JOY"
2nd pass: "OJY"
3rd pass: "OYJ"

taking O:-
1st pass: "OJY"
2nd pass: "JOY"
3rd pass: "JYO"

taking Y:-
1st pass: "YOJ"
2nd pass: "JYO"
3rd pass: "JOY"

then remove the repeated results, and you'll get all the combinations for that string

But you missed YJO, so your algorithm is flawed. :icon_wink:

[hinduengg]

Thank you for the wonderful aid. Now I have got a new direction in the seemingly complicated logic . I would now try once again with the technique although I was thinking the same but could not figure it out clearly . I have been worked up with this for just 2 days . But with the guiding lights I would be able to make it to my goal soon.

Thank you a lot to everyone- WaltP, Killer typo, darkscript,Lerner , Iamwithwee .

[darkscript]

Thanks WaltP for pointing out the flaw, I got it to work by doing the algorithm on the string, then on the reversed string.

one more thing, the results for a string of length n, are n!, so for JOY, there should be 6 combinations.

[hinduengg]

I am unable to implement the logic suuceesfully .:sad:
I have put in my best efforts but no result ! I can not develop the code and you cannot say that I have not tried. I spent a lot of time using lot of for loops for getting the charecters fitted to the rotating positions. So please gift a little code to end this problem. I tried and if you would ask me "where is my effort?" , I would say that wasting 3 days on this is enough proof plus the codes one which i tried to develop and the other of Vegeseat, which was a little complex.

I attempted the problem several times but could not achieve it.
Besides on the net they use mostly recursion methods which is not taught to us.

So please help !! I really need it.:confused:
Hinduengg

You tried your best. When you fail this it will give you incentive to do better next time. It's all part of the learning game. Good luck.

[JRM]

I am unable to implement the logic suuceesfully .:sad:
So please help !! I really need it.:confused:
Hinduengg

Ok, one code neophyte to another...
write the example word JOY on the left side of a sheet:
then think of pointing to another "scratch" array.
You want the scratch array to have the first letter whever is is NOT in the original.
the first array is the "refernce" and does not change. ref(0) assigns to scratch(1)
J (0) Scratch 0
O (1) scratch 1
Y (2) scratch 2
Once you have "ticked "thru the first letter J putting it wherever it was not before and swapping the displaced letter to the J position, copy the unaffected letter(s) to the same postions as the original move on to the next, etc...

I think this is the "cleanest" solution, sice ther will be no duplications to clean up.
I hope this visualization will help you get through it.

[ndeniche]

have you tried it in the compiler? show us the logic you've used...

[Lerner]

This algorhythm might work for you. I've not taken it
beyond this level of coding, that's up to you. Without
seeing your actual code I won't assist anything further.

It's probably best to get itworking for MAX of 3 and 
then extending it to 7 later.
 
Start out declaring 2 char arrays:
const INT MAX = 3; //maximum number of alphabetical char
char input[MAX + 1];  //input string, allow for null char
char permu[MAX + 1];  //a given permutation of input

int len = strlen(input);  //determine actual length of input

declare a boolean flag to skip a loop completely if necessary:
bool addToPermu = true; //default it to true

int loopNumber = 1; //to keep track of which loop you are in.

assign a null char to permu[0] to make it an empty string

Now envision a series of nested loops to keep track of what 
to do when:


loop 1 will control permu[0]
{
  loop 2 will control permu[1]
  {
     loop 3 will control permu[2]
     {  
        .
        .
        .
        extend on to loop 7 in eventual program, since that's
        max value of len by definition in instruction set
     }
  }
}

Each element of input can be used only once in each version
of permu so:

1) Declare an int variable in each loop to act as an index,
call them index0, index1, index2, etc. 
2) The index of each loop can range from 0 to len - 1.
3) If a given indexX has the same value of any previous indexes, 
then don't use it. Otherwise, if adddToPermu is true, then assign 
input[indexX] to permu[0] or permu[1] or permu[2], whatever, 
depending on which loop you are in. 

You shouldn't add another element to permu, except a null 
char, if the next element of input is the null char, which
is true if loopNumber equals len, so:
1) After assigning current input[indexX] to permu in any given
   loop check if loopNumber equals len:
   A) If loopNumber equals len then: 
    a) add a null char to the end of the current version of 
        permu to make permu a string
    b) and change addToPermu to false; 
   B) Otherwise increment loopNumber by 1

After completing loopNumber equals MAX and before going back 
to loop 1:
1) print out this version of permu,
2) reset addToPermu to true
3) reset loopNumber to 1
4) advance to next line of the output destination

The concept of nested loops is quite powerful, so really try
to understand what's going on.

If you didn't have an upperlimit to the size of input, then
you would need to userecursion or dynamic programming or some
other protocol.

[JRM]

have you tried it in the compiler? show us the logic you've used...

NAw, it's not MY homework. I'm just trying to get Hinduegg to the solution by herself.
I wrote the logic out verbally which should give a good outline on how to approach this problem. Do you think it's flawed in any way?

Otherwise, if I post a working program, I want the A for the homework and the university credit for the coarse. Any takers?

I think she already has a working program. Her problem is understanding the algo, or rather convincing her instructor she has understood it?

[ndeniche]

it's not that hard anyways... all you need are two arrays, and shift the character positions between them... it should go something like this:

#include<iostream>
#include<cstdlib>

using namespace std;

int main(){
    int i=0,j=0;
    char string[100],permut[100],temp;
    gets(string);
    strcpy(permut,string);
    puts(permut);
    i=0;
    getchar();
    while (string[i]!='\0'){
         while (permut[j]!='\0'){
             temp=permut[j];
             permut[j]=permut[i];
             permut[i]=temp;
             puts(permut);
             j++;
         }i++;
    }getchar();
    _exit(0);
    return 0;
}

i think it's enough for a lead start... it doesn't show all the permutations, but the logic you need to use is somewhat like that...

[hinduengg]

Thanks for taking pains . The code below gives me 5 permutations
-"old" remains.

#include<iostream.h>
#include<string.h>
#include<conio.h>
#include<stdio.h>
int main()
{
char a[100];
char per[100];
char temp;
cout<<"enter the word"<<endl;
gets(a);

strcpy(per,a);
puts(per);
getchar();

for(int y=0;a[y]!='\0';y++)
{
  for(int x=0;per[x]!='\0';x++)
  {   temp=per[x];
   per[x]=per[y];
   per[y]=temp;  //swapping positions
   cout<<per<<endl;
   }
  }
 getch();
return 0;
}

If the given input is-"dol"
then output is :
dol
odl
ldo
dlo
dlo
lod
ldo
ldo

In the above output i have- dol,odl,dlo,ldo,lod but old is missing .
The problem that after 1st loop run the y=1 then when x loop is run
we get - swapped positions of "dlo" then when 2nd time loop of y is run in which y=2 then we would be getting permutations of word-"ldo".

How can I catch "old" permutation and if I am not wrong that puts and cout perform in same manner!:-/

Thank you ,
hinduengg

[JRM]

How does line 24 work?
Also the permutation is n! = 6. You have 8 with omissions and duplicates.

Think of moving each letter through every postion while evry other letter remains in the same position EXCEPT the swap letter.

BTW, Nichito was mixing C++ and C with that "\0" business in the string. If using C++ string, one can simply use per.size() to return the size of the input string. C++ <string> and a c string are different animals. The c string animal is more likely to bite...

Did you compile your "modified" version of Nichito's program?

Do you have to write this in c?

[Lerner]

Use 1 loop for each desired char in the permutation.

char input[4] = "dol";
char permu[4];
permu[3] = '/0';

loop 1 ----controls permu[0], range 0-2
{
  loop 2---controls permu[1], range 0-2
  {
    loop 3-controls permu[2], range 0-2
    {
    }
  }
}

Without restrictions this will provide the following pattern:
Try 1
loop 1 gives d
loop 2 gives d
loop 3 gives d
Try 2
loop 1 gives d
loop 2 gives d
loop 3 gives o
Try 3
loop 1 gives d
loop 2 gives d
loop 3 gives l
Try 4
loop 1 gives d
loop 2 gives o
loop 3 gives d
Try 5
loop 1 gives d
loop 2 gives o
loop 3 gives o
Try 6
loop 1 gives d
loop 2 gives o
loop 3 gives l
.
.
.
etc

This gives all "permutations" of all positions irrespective
of duplicate letters. If that's what you want, fine.
To use each element in input just once in permu you need
to restrict available indexes from the range as I previously
discussed.

Try 1
loop 1 gives d, use index 0
loop 2 gives o, use index 1
loop 3 gives l, use index 2
Try 2
loop 1 gives d, use index 0
loop 2 gives l, use index 2
loop 3 gives o, use index 1
Try 3
loop 1 gives o, use index 1
loop 2 gives d, use index 0
loop 3 gives l, use index 2
Try 4
loop 1 gives o, use index 1
loop 2 gives l, use index 2
loop 3 gives d, use index 0
Try 5
loop 1 gives l, use index 2
loop 2 gives d, use index 0
loop 3 gives o, use index 1
Try 6
loop 1 gives l, use index 2
loop 2 gives o, use index 1
loop 3 gives d, use index 0

[hinduengg]

I did not understand the first part of your post , I am aiming the second part . why do you use permu[3] then put a null charecter
at position 3?

[hinduengg]

and I have to design for seven character containing string then sholud I use 7 loops? I am unable to understand. Please give advice. The code is in C++ and I tried Nichito's program my way it gave me the above o/p in my previous post.

Thank you,
hinduengg

[Lerner]

if permu is to printed as a string then it needs to be a null terminated char array. In the post with input being dol, post #26 abobve, we know that the input is only three char long and that the loops will develop each char in each permutation and that there will always need to be a null char at permu[3], so I just put it there before doing the loops.

If I were doing the project I'd do it in three stages.

First, I'd get a working program that will get three nested loops printing out every char combination (part 1 of post #26) and understand how the nested loop system worked.

Second, I'd use the 3 nested loop system to handle a 3 char input (like the "dol" string above), where the loops will be restricted to generate permutations with each element in input is used once in permu.

Once I got that working, I'd extend the nested loop system to 7 nested loops, expanding the restrictions as necessary for 7 vs 3 loops, and finally putting in code to handle the situation where in the input could be anywhere from an empty string, to a single char string, to a 7 char string or anywhere in between.

My original post contains what I think is the necessary logic to handle the full program, but I'd develop the program in a stepwise fashion and not try to handle every situation at once in my coding, even if I can think of them in my logic.

[hinduengg]

To JRM,
line 26 prints the string with alterations automatically regarding that and that s why have a question too with thinking sign!