• Status: Solved
• Priority: Medium
• Security: Public
• Views: 562

# recursive permutation method

i try to solve this method but i couldn't reach to anything . this is the Question :

You have an index card with the letter C written on one side, and S on the other. You want to see ALL of the possible ways the card will land if you drop it n times. Write a recursive method that prints each session of dropping the cards with C's and S's. For example of you drop it 4 times in a given session, all possible ways to drop it are as follows:
CCCC
CCCS
CCSC
CCSS
CSCC
CSCS
CSSC
CSSS
SCCC
SCCS
SCSC
SCSS
SSCC
SSCS
SSSC
SSSS
*Note: The possible ways would have to print in this specific order.

AND this is my solve but it's wrong  :

static void permute(int n)
{
int j;
char a []={'C','S'};
int i = n ;

if (i == 0)
System.out.println("Nothing to print");
else
{
for (j = i; j <= n; j++)
{
System.out.println(a);

permute(n-1);

String u = a[j] * a[j];

}
}

}
0
Nossa4ever
• 3
• 2
1 Solution

Commented:
Somehow, recursion or not, I believe you'd need to keep track of the perms. you'd previously created.
0

Commented:
public class Permute {
static int positions = 4;
static char[] sides = {'C', 'S'};
static char[] item = new char[positions];
static long number = 0;

public static void permute(int i) {
if (i == 0) {
number++;
System.out.print(number + " : ");
for (int k = 0; k < item.length; k++) {
System.out.print(item[item.length - k - 1]);
}
System.out.println();
return;
}

for (char c : sides) {
item[i - 1] = c;
permute(i - 1);
}
}

public static void main(String[] args) {
permute(positions);
}

}

// ---------------- end of code -------------------------------

The following class does what you want. The key lines are:
for (char c : sides) {
item[i - 1] = c;
permute(i - 1);
}

In order to have minimal memory consumption you have to have an array that keeps the current values. When recursion reaches "the bottom" the array that keeps current values is just dumped and the function ends.
"the bottom" is reached when "i" reaches 0.
0

Software engineerCommented:
Let permute(1) return a list of the Strings "C" and "S"

Then you can write permute(n) as
* Take the result of permute(n-1)
* for each String element in the result of permute(n-1)
prefix it with "C" and add it to your result list
for each String element in the result of permute(n-1)
prefix it with "S" and add it to your result list
return your result list

Now you can get your desired output by writing:

for (String each : permute(4)) {
System.out.println(each);
}
0

Software engineerCommented:
@Valeri: don't post ready-out-of-the-box code for homework questions!
0

Commented:
@zzynx:
I agree! Probably you are right and this is homework...?! I don't know...?!
Anyway, understanding recursion, if the author of the question is student, is difficult... that's way I thing that "ready" code will be useful for him and will help him to solve next recursion tasks by himself...
0

Software engineerCommented:
Probably you are right and this is homework...?! I don't know...?!
I think there's no doubt at all that this is a homework/school question.

... understanding recursion (...) is difficult
Difficulty is never a good alibi for posting full blown code in the case of a homework question.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

## Featured Post

• 3
• 2
Tackle projects and never again get stuck behind a technical roadblock.