Results 1 to 3 of 3
  1. #1
    Jack_Tauson_Sr is offline Senior Member
    Join Date
    Nov 2011
    Posts
    114
    Rep Power
    0

    Default Permutation of String ( Problem in understandin Code )

    Please consider the following code for finding the permutation of a string:


    Java Code:
    public static ArrayList<String> permutations(String str) {	
    		ArrayList<String> result = new ArrayList<String>();
    		
    		int length = str.length();
    		switch(length) {
    		case 0:
    			break;
    		case 1:
    			result.add(str);
    			break;
    		case 2:
    			result.add(str);
    			String rstr = new StringBuffer(str).reverse().toString();
    			result.add(rstr);
    			break;
    		default:
    			for (int i = 0; i < length; i++) {
    				String remaining = new StringBuffer(str).deleteCharAt(i).toString();
    				for (String sub_permutation : permutations(remaining)) {
    					String s = str.charAt(i) + sub_permutation;
    					result.add(s);
    				}
    			}
    			break;
    		}
    		
    		return result;
    	}
    MY QUESTION:

    If we consider the case where str = abc. Then I can understand that since the length is 3, the program control will go
    to default setting where , String variable "remaining" will hold "bc" part of String "abc" after the initial character is removed.

    If we consider the line "
    Java Code:
    for (String sub_permutation : permutations(remaining))
    ", since after removing one character
    from the string abc, the case 2 condition will be matched (because
    Java Code:
    permutation(bc)
    will be called), then I'm wondering, it would break after the line
    Java Code:
    result.add(rstr)
    and the final result will be just bc which is not desired.

    Can anyone explain me what I'm not understanding in the code?

  2. #2
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,614
    Rep Power
    5

    Default Re: Permutation of String ( Problem in understandin Code )

    Your analysis of what is going on seems correct to me. Therefore, I am not understanding what it is you are looking for. Did you write this yourself or are you just trying to understand someone else's algorithm?

    Regards,
    Jim
    Last edited by jim829; 03-17-2013 at 02:56 AM. Reason: follow-up question
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  3. #3
    SJF
    SJF is offline Senior Member
    Join Date
    Oct 2012
    Posts
    108
    Rep Power
    0

    Default Re: Permutation of String ( Problem in understandin Code )

    Java Code:
         for (String sub_permutation : permutations(remaining))   // Reads: FOR EACH String sub_permutation IN permutations(remaining) DO
    So for the abc example String s = "a" + "bc" once then "a" + "cb" once.

    as the result of permutations("bc") is the ArrayList<String> containing "bc" and "cb"

Similar Threads

  1. Replies: 5
    Last Post: 01-22-2013, 07:13 PM
  2. random array permutation
    By jwl in forum New To Java
    Replies: 1
    Last Post: 11-15-2012, 08:01 PM
  3. Need a help in two dimentaional permutation
    By venk123 in forum New To Java
    Replies: 7
    Last Post: 08-06-2011, 01:28 AM
  4. Permutation
    By Claymz in forum New To Java
    Replies: 4
    Last Post: 06-01-2011, 02:27 PM
  5. Replies: 3
    Last Post: 08-24-2009, 07:39 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •