Multiple Recursion,it doesnt make sense to me,how do i create this code?

[VOLTS100]

Algorithm PuzzleSolve(k,S,U):
Input: An integer k, sequence S, and set U
Output: An enumeration of all k-length extensions to S using elements in U without repetitions

for
each e in U do Remove e from U {e is now being used}
Add e to the end of S

if
k = 1 then Test whether S is a configuration that solves the puzzle

if
S solves the puzzle then return “Solution found: ” S

else
PuzzleSolve(k−1,S,U)
Add e back to U {e is now unused}
Remove e from the end of S

[Handy Andy]

Hello VOLTS100,

The specs refer to a function called "PuzzleSolver", but with knowing what the program is about and what input and output would look like it is difficult to know how to write the program.

What is the purpose of the program?
What should the program do, i.e., an explain not in terms of code.
What and where does the input come from and look like?
What should the output look like?

Answering these will help you get started.

From the specs we know that "k" is an int and that "S" and "U" are most likely strings. "e" has me perplexed at the moment.

I would start the program with getting input for "k", if needed, and "S"and "U", so you at least have something to start with. The rest of the program can come later.

For me knowing what the input and output looks like I can make a program to fit. Otherwise you are just guessing.

Hope that helps,

Andy

[VOLTS100]

Hi Andy

Thank you for your help i appreciate it. I kind of understand how the program should work but the problem is im having a hard time implementing it this is how far i got but it doesnt give me the output i want

#include <iostream>
#include <string>

using namespace std;

char PuzzleSolve(int k, char* S, char* U); //prototype


int main()
{
	//test run
	int k = 5;
	char S[5];
	char U[5] = { 'a','b','c','d','e' };

	//to see that S = U
	cout << PuzzleSolve(k, S, U) << endl;


	system("pause");
	return 0;
}

char PuzzleSolve(int k, char* S, char* U)
{
	//this is how i see the program but i dont think its right
	//this put element to S from U, it arrange the element like how prompt of the program
	for (int i = 0, j = k; i <= k, j >= 0; i++, j--)
	{
		S[j] = U[i];
		U[i] = ' ';
	}

	//this return the S if it equals to U
	if (k == 1)
	{
		for (int i = 0; i <= k; i++)
		{
			S[i] = U[i];
			if (S[i] = U[i])
				return S[i]; //i dont think this is right?
		}

	}

	//recursion to put back the element to U
	else
		PuzzleSolve(k - 1, S, U);
		for (int i = 0, j = k; i <= k, j >= 0; i++, j--)
		{
			U[i] = S[j];
			S[j] = ' ';
		}
}

[Handy Andy]

Hello VOLTS100,

Starting at the top you include the header fie "string", but never use it. You can access a "string" with a subscript just like you do the character arrays.

Line 4: I would avoid using this because it will give you problems in the future when your programs get more complicated. Do a search here on "using namespace std" and read what you find.

int k = 5;
char S[5];
char U[5] = { 'a','b','c','d','e' };

Line 1: you are limiting yourself here. Any time "k" is changed you will have to recompile the program.

Lines 2 and 3 would work better as "std::string" and "S" should be larger than 5 because as you said in your OP "Add e to the end of S". As it is you have no room to add to "S". As a std::string it is much easier to compare this way:if (S = U). It saves using a for loop for checking unless there is a need to check each individual element of the string. As a std::string the size of the string can change without you having to do any special work. It is all automatic. Then there is the point that "S" is never given a value before "PuzleSolve" is called. So, the function will receive garbage for the vale of "S".

In the function "PuzzleSolve" the first for loop is wrong. Given the middle section of i <= k, j >= 0. Only the "j >= 0"will be used because of the comma operator. What might work better here is i <= k && j >= 0. Even that may not be the est way to go about it. Then in the for loop I do not understand why you change the value if "U" as you do.

Line 41: you are correct It is not right or better put it is not the right place for a return. With the return inside the for loop it will execute only once before you return from the function.

In the else block you will cal "PuzzleSolve" until k = 1 and the if block is executed only to execute the fore loop once before the return leaves the function never reaching the for loop of the else block.

Earlier I asked fur questions. Answering them for your self will help you get started. Answering them here helps me understand what the program should do. Seeing the code you posted I have a better idea of what you are trying to achieve, but still have questions.

There is still a lot of guess work for me, but I will see what I can come up with.

Hope that helps,

Andy

[Handy Andy]

Hello VOLTS100,

I loaded your program and found that "ProblemSolve" does not work the way you might be thinking.I discovered that the first for loop is trying to set "A" to "U" and it is not working and what does work sets "S" in the reverse order of "U" .Not what you want and "S" should have a value before you reach "ProblemSolve".

The idea of "ProblemSolve" is to compare the two strings. The for loop should compare not set something like:

bool PuzzleSolve(int k, char* S, char* U)
{
	bool equal{ false };
	
	for (int lc = 0; lc < 5; lc++)
	{

		if (S[lc] == U[lc])
			equal = true;
		else
			equal = false;
	}

	return equal;
}

Since the idea here is to compare you could use "strcmp(S, U);". Requires the header file "cstring" or "string.h". I would use "cstring". Not only does it do the same work it will tell you which string is less. This does require that "S" have a value to work right.

Acording to what the program needs "Input: An integer k, sequence S, and set U". This tells me that the program should start with:

int k{ 0 };
std::string S{ "" };
std::string U{ "" };

You could use a C style character array if you need to. I would make the size of each 50, so you have enough room to store what is entered.

Something that occurred to me this morning. You define "S" and "U" as having a size of five, e.g., char U[5] = { 'a','b','c','d','e' };, but you are giving the array five characters in positions 0 - 4 which leaves no room for the terminating null character of the string. If you want to store five characters then the size needs to be six to leave room for the "\0" at the end.

When you call "ProblemSolve" the first for loop starts with int i = 0, j = k, so when "k" = five you are starting outside the boundaries of the array and will get unpredictable results.

The specs of the program are good if you know how the game is played and what it is about. You might want to start with a function that displays the instructions of how to play. Also a known sample input and output would go along way to figure out the program. Right now I am making guesses that do not seem to work.

Questions. Where did this come from? A homework assignment? Something from a web sight? Is there a web address where I might be able to look at?

Right now I am stuck trying to figure out how this program should work.

Andy