Thread: Need help with logic algorithm...

1. Need help with logic algorithm...

This is an assignment but I'm not stumped by the coding of it. I'm stumped by the logical algorithm I've tried several approaches and none of them are working.

The premise is this allow the user to input a word and then output all permutations of the word in which the first letter stays in it's default position. Also we cannot use string objects only arrays of chars.

i.e. word would output:

word wodr wdor wrod wdro wrdo

The parts of the approach I'm sure are correct are:

Get user input and store in an Array(inputArray).
Store first letter of user input in a variable(firstLetter).
Store initial word in an Array(outputArray).
Remove First Letter of input from inputArray).
Shuffle remaining members of the inputArray
Store firstLetter concatenated with inputArray as a new member of outputArray.

My issue is figuring out how to shuffle the remaining inputArray characters and only arrive at the remaining permutations.

I tried dynamically refering to indexes of characters based on incrementation and the length of inputArray and couldn't get it to work.

I tried simply rotating the position of each letter forward in a loop but this results in only a few of the permutations.

Any advice would be appreciated. Honestly I'm a little over my head here, I've done a lot of scripting(javascript, actionscript, PHP) and some JAVA but no C++ and this is the second half of the introductory class.

2. Hint.. Recursion... (At least I think so)

3. To get all the permutations of a sequence, break it into a head (first symbol) and tail (all the rest). Generate the permutations of the tail. Then iterate through all positions of all the permutations and insert the head in those positions.

A sequence with only one symbol in it has only itself as a permutation.

Example: xyz

Head = x, tail = yz
Generate all permutations of yz:
Head = y, tail = z
Generate all permutations of z --> z
Insert y in all positions: yz zy
Insert x in all position: xyz xzy yxz zxy yzx zyx

4. Thank you all for the responses.
I'm a bit bogged down by work today but on my lunch break I'm going to look in to Recursion.

Brewbuck I think I understand the concept of what your doing, but I'm not entirely sure how to do it dynamically and account for words of any length.

5. Originally Posted by fenixink
Thank you all for the responses.
I'm a bit bogged down by work today but on my lunch break I'm going to look in to Recursion.
I wouldn't worry about a recursive solution right now.

Originally Posted by fenixink
Brewbuck I think I understand the concept of what your doing, but I'm not entirely sure how to do it dynamically and account for words of any length.
Use a std::string for your input and iterate through that.

6. Originally Posted by AndrewHunter
I wouldn't worry about a recursive solution right now.
Won't it be *much* simpler than iterating the inner portion too ?

7. Originally Posted by manasij7479
Won't it be *much* simpler than iterating the inner portion too ?
Define "simpler". For a beginner, I would say no.

8. Originally Posted by fenixink
Also we cannot use string objects only arrays of chars.
I would use string if I could but I can't I was reading up on Recursion and it seems like a viable solution but I'm still not quite sure how to make it work dynamically.

Thank you all again for the input.

9. Originally Posted by fenixink
I would use string if I could but I can't I was reading up on Recursion and it seems like a viable solution but I'm still not quite sure how to make it work dynamically.

Thank you all again for the input.
I hate these BS assignments. Ok, well in that case you need to dynamically allocate a char array to obtain user input - or - and what you are probably suppose to do- is make an input array that is large enough to handle all inputs: say char[100] for instance.

10. Here is what I have so far:

Code:
```#include <iostream>
using namespace std;

int main ()
{char word[100];
cout << "Enter a word: " << endl;
cin >> word
char firstLetter[1] = {word[0]};
cout << "The first letter of the word is " << firstLetter[0]; << endl;
return 0;
}```
Not entirely sure how to get the permutations of the remaining members of word.

11. Well, let's start by making sure your starting point is correct:
Code:
```#include <iostream>

int main(void){

//initialize array
char myword[100]={0};

std::cout<<"Enter word:";
//cin is not safe with char arrays
std::cin.getline(myword,sizeof(myword)-1);
//you don't need an extra char variable here
std::cout<<"first char: "<<myword[0];
return(0);
}```

12. Is there a reason why

std::cin

is better than:

using namespace std;

cin

Just curious I honestly don't know.
I was using the second variable because I intended to pull the first letter out of it into another variable that way myword would only contain the char we wanted permutations of.

13. Did some research and here is my current code:

Code:
```#include <iostream>

int main (void)
{using std::cin; //using declaration for cin
using std::cout; //using declaration for cout
using std::endl; //using declaration for endl

char myword[100]={0}; //initialize array

cout << "Enter word:" << endl;
cin.getline(myword,sizeof(myword)-1);
cout << "first char: " << myword[0] << endl;
return(0)}```

14. Ok, so think about Bewbuck's solution in post #4. Could you describe how to manipulate an array that way using words? Perhaps psuedocode. You are going to need to use loops here.