Solved

recursive  permutation method

Posted on 2013-12-15
7
553 Views
Last Modified: 2013-12-17
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
Comment
Question by:Nossa4ever
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
7 Comments
 
LVL 16

Expert Comment

by:krakatoa
ID: 39720450
Somehow, recursion or not, I believe you'd need to keep track of the perms. you'd previously created.
0
 
LVL 16

Accepted Solution

by:
Valeri earned 500 total points
ID: 39721236
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
 
LVL 37

Expert Comment

by:zzynx
ID: 39721239
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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 37

Expert Comment

by:zzynx
ID: 39721241
@Valeri: don't post ready-out-of-the-box code for homework questions!
0
 
LVL 16

Expert Comment

by:Valeri
ID: 39721267
@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
 
LVL 37

Expert Comment

by:zzynx
ID: 39721300
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

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
web application structure 18 135
servlet and mdb, jms error 1 81
Need Help! Getting a syntax error and don't understand why 3 55
Session in java desktop 5 37
Java contains several comparison operators (e.g., <, <=, >, >=, ==, !=) that allow you to compare primitive values. However, these operators cannot be used to compare the contents of objects. Interface Comparable is used to allow objects of a cl…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
Suggested Courses

734 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question