Programming Forums > Application Development > Java

titaniumdecoy · Jan 18th, 2008, 10:04 PM

This is not homework. It is an exercise out of a textbook I used last year which I am reviewing. I am trying to write a recursive algorithm to reverse a character array. I wrote the code below which works, except that it prints out each permutation multiple times, and I can't figure out how to prevent that from happening. Please advise...

 Java Syntax (Toggle Plain Text) 
public class RecursivePermutation {
 
	public static void main(String[] args) {
 
		String str = "abc";
		permute(str);
 
	}
 
	public static void permute(String str) {
		permute(str.toCharArray(), 0, str.length() - 1);
	}
 
	private static void permute(char[] str, int low, int high) {
		[b]System.out.println(str);[/b]
		if (low > high) return; 
		for (int i = low; i <= high; i++) {
			char[] x = charArrayWithSwappedChars(str, low, i);
			permute(x, low + 1, high);
		}
	}
 
	private static char[] 
	charArrayWithSwappedChars(char[] str, int a, int b) {
		char[] array = str.clone();
		char c = array[a];
		array[a] = array[b];
		array[b] = c;
		return array;
	}
 
}
public class RecursivePermutation {
	
	public static void main(String[] args) {
		
		String str = "abc";
		permute(str);
		
	}
	
	public static void permute(String str) {
		permute(str.toCharArray(), 0, str.length() - 1);
	}
	
	private static void permute(char[] str, int low, int high) {
		[b]System.out.println(str);[/b]
		if (low > high) return; 
		for (int i = low; i <= high; i++) {
			char[] x = charArrayWithSwappedChars(str, low, i);
			permute(x, low + 1, high);
		}
	}
	
	private static char[] 
	charArrayWithSwappedChars(char[] str, int a, int b) {
		char[] array = str.clone();
		char c = array[a];
		array[a] = array[b];
		array[b] = c;
		return array;
	}

}

Output:

(Toggle Plain Text)

abc
abc
abc
acb
acb
bac
bac
bac
bca
bca
cba
cba
cba
cab
cab

Sane · Jan 18th, 2008, 10:15 PM

To prevent multiple occurrences of the same value, you have several weapons at your disposal. The main methods are:

Use "chalk" (in the form of a list, or hash table) to mark visited nodes. Then check the chalk each time you propose a visitation to another node.
Look more closesly at the structure of the tree to see exactly what makes each leaf unique. Use this in determining what values must change each permutation/recurse.

The first one is a a thoughtless and powerful fix. It's also generally applicable to many similar situations. And the hash table has an amortized cost of $O(1)$ , so it's not inefficient. However, it's not the most elegant solution for this problem.

The second one is more "proper", but I don't understand the problem enough to recommend anything less broad. It seems perfectly possible, and more along the lines of what you're asking for an answer. Could you explain the question further?

titaniumdecoy · Jan 18th, 2008, 11:09 PM

I believe there is a fairly straightforward way to prevent each permutation from being multiple times; e.g., the "second way." That is what I am looking for.

Also, you will notice that in each loop within the method I make a copy of the array (via the charArrayWithSwappedChars method). I spent a long time thinking about it but I don't believe there is any way to accomplish this task without making copies. If there is, I would certainly be interested to hear it.

Sane · Jan 18th, 2008, 11:14 PM

Well could you explain the question? I'm trying to figure it out from your output, but it seems random how the 2nd letter is shifted to the 3rd, then to the 1st. And it continues on in this seemingly arbitrary pattern. Problem statement?

You're not just trying to permutate a string, right...?

titaniumdecoy · Jan 18th, 2008, 11:27 PM

Quote:

Originally Posted by Sane

You're not just trying to permutate a string, right...?

Actually, yes, I am

My approach makes sense to me, logically anyway. I take the string, swap each character into the low index, and repeat on the next piece of the string for each of these (low+1). I can see why each permutation gets printed multiple times but can't think of how to prevent this.

I'm just looking for a suggestion on how to get it working.

EDIT: I just looked at my first post and it says "reverse a character array" rather than "permute a character array".

titaniumdecoy · Jan 18th, 2008, 11:42 PM

I fixed it:

 Java Syntax (Toggle Plain Text) 
private static void permute(char[] str, int low, int high) {
    if (low == high) {
        System.out.println(str);
    } else {
        for (int i = low; i <= high; i++) {
            char[] x = charArrayWithSwappedChars(str, low, i);
            permute(x, low + 1, high);
        }
    }
}
private static void permute(char[] str, int low, int high) {
    if (low == high) {
        System.out.println(str);
    } else {
        for (int i = low; i <= high; i++) {
            char[] x = charArrayWithSwappedChars(str, low, i);
            permute(x, low + 1, high);
        }
    }
}

Is there a way to do this without making a copy of the char array each loop iteration?

Sane · Jan 19th, 2008, 12:04 AM

I was very much confused, because you said "reverse" instead of "recurse" in your initial post at one point. So I was assuming there was some complicated problem statement missing. Okay.

The key is to keep track of what you haven't added. See how the tree stems apart, and what data you want to keep track of. This algorithm can be proven qualitatively by drawing the trees. It can be proven mathematically by subproblems and dynamic programming. I'll leave that excercise up to you.

Edit: In reference to your question about doing it without copying new strings: I do not believe so. This is due to the nature of dynamic programming and subproblems. If you look at the tree the reason becomes obvious. But there might be some fancy ways. Such as brute forcing it iteratively, and checking for invalid entries. So I doubt any other solutions would be efficient in any case. But I am not sure.

Here it is in C:

 C Syntax (Toggle Plain Text) 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void permutate(char *s, char *r, int k, int n) {
    int i;
    char *new_s;
    if (k==n) {              // At the end
        r[n] = 0;            // Add a null terminator
        printf("%s\n", r);   // Output result
        return;                                     
    }
    for(i=0;i<n;i++) {
        if (s[i]) {
            new_s = calloc(sizeof(char), n);       
 
            // Use memcpy to ignore the null terminators 
            memcpy(new_s, s, sizeof(char) * (n+1)); 
            new_s[i] = 0;      // Mark used character
            r[k] = s[i];       // Store used character
            permutate(new_s, r, k+1, n); 
            free(new_s);
        }
    }
}
 
int main() {
 
    char str[] = "abc"; 
    char *result_str = calloc(sizeof(char), strlen(str) + 1); 
 
    permutate(str, result_str, 0, strlen(str));
    return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void permutate(char *s, char *r, int k, int n) {
    int i;
    char *new_s;
    if (k==n) {              // At the end
        r[n] = 0;            // Add a null terminator
        printf("%s\n", r);   // Output result
        return;                                     
    }
    for(i=0;i<n;i++) {
        if (s[i]) {
            new_s = calloc(sizeof(char), n);       

            // Use memcpy to ignore the null terminators 
            memcpy(new_s, s, sizeof(char) * (n+1)); 
            new_s[i] = 0;      // Mark used character
            r[k] = s[i];       // Store used character
            permutate(new_s, r, k+1, n); 
            free(new_s);
        }
    }
}
    
int main() {
    
    char str[] = "abc"; 
    char *result_str = calloc(sizeof(char), strlen(str) + 1); 
    
    permutate(str, result_str, 0, strlen(str));
    return 0;
}

titaniumdecoy · Jan 19th, 2008, 12:17 AM

I am having trouble understanding how your code works but I will figure it out eventually. How does its runtime compare to mine? (Thanks, by the way.)

I really should have specified this in the beginning, but the (Java) method signature is supposed to be

void permute(char[] str, int low, int high).

Is it possible to accomplish this without copying the string on each iteration of the loop?

Sane · Jan 19th, 2008, 12:23 AM

Does it work perfectly with your revision? If it does, then ours would both perform the same. It looks like we did the same thing except you swap characters in the array, rather than marking and deleting them as I did.

About the string copying each iteration, I added an edit to my previous post.

Heading to bed. Good luck.

titaniumdecoy · Jan 19th, 2008, 12:31 AM

Thanks, Sane. I appreciate your help with this problem.

Jan 18th, 2008, 10:04 PM	#1
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 837 Rep Power: 3	Recursive permutation of string This is not homework. It is an exercise out of a textbook I used last year which I am reviewing. I am trying to write a recursive algorithm to reverse a character array. I wrote the code below which works, except that it prints out each permutation multiple times, and I can't figure out how to prevent that from happening. Please advise... Java Syntax (Toggle Plain Text) public class RecursivePermutation { public static void main(String[] args) { String str = "abc"; permute(str); } public static void permute(String str) { permute(str.toCharArray(), 0, str.length() - 1); } private static void permute(char[] str, int low, int high) { [b]System.out.println(str);[/b] if (low > high) return; for (int i = low; i <= high; i++) { char[] x = charArrayWithSwappedChars(str, low, i); permute(x, low + 1, high); } } private static char[] charArrayWithSwappedChars(char[] str, int a, int b) { char[] array = str.clone(); char c = array[a]; array[a] = array[b]; array[b] = c; return array; } } public class RecursivePermutation { public static void main(String[] args) { String str = "abc"; permute(str); } public static void permute(String str) { permute(str.toCharArray(), 0, str.length() - 1); } private static void permute(char[] str, int low, int high) { [b]System.out.println(str);[/b] if (low > high) return; for (int i = low; i <= high; i++) { char[] x = charArrayWithSwappedChars(str, low, i); permute(x, low + 1, high); } } private static char[] charArrayWithSwappedChars(char[] str, int a, int b) { char[] array = str.clone(); char c = array[a]; array[a] = array[b]; array[b] = c; return array; } } Output: (Toggle Plain Text) abc abc abc acb acb bac bac bac bca bca cba cba cba cab cab abc abc abc acb acb bac bac bac bca bca cba cba cba cab cab

Jan 18th, 2008, 10:15 PM	#2
Sane Programming Guru Join Date: Apr 2005 Posts: 1,799 Rep Power: 5	Re: Recursive permutation of string To prevent multiple occurrences of the same value, you have several weapons at your disposal. The main methods are: Use "chalk" (in the form of a list, or hash table) to mark visited nodes. Then check the chalk each time you propose a visitation to another node. Look more closesly at the structure of the tree to see exactly what makes each leaf unique. Use this in determining what values must change each permutation/recurse. The first one is a a thoughtless and powerful fix. It's also generally applicable to many similar situations. And the hash table has an amortized cost of $O(1)$ , so it's not inefficient. However, it's not the most elegant solution for this problem. The second one is more "proper", but I don't understand the problem enough to recommend anything less broad. It seems perfectly possible, and more along the lines of what you're asking for an answer. Could you explain the question further? Last edited by Sane; Jan 18th, 2008 at 10:33 PM.

Jan 18th, 2008, 11:09 PM	#3
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 837 Rep Power: 3	Re: Recursive permutation of string I believe there is a fairly straightforward way to prevent each permutation from being multiple times; e.g., the "second way." That is what I am looking for. Also, you will notice that in each loop within the method I make a copy of the array (via the charArrayWithSwappedChars method). I spent a long time thinking about it but I don't believe there is any way to accomplish this task without making copies. If there is, I would certainly be interested to hear it.

Jan 18th, 2008, 11:14 PM	#4
Sane Programming Guru Join Date: Apr 2005 Posts: 1,799 Rep Power: 5	Re: Recursive permutation of string Well could you explain the question? I'm trying to figure it out from your output, but it seems random how the 2nd letter is shifted to the 3rd, then to the 1st. And it continues on in this seemingly arbitrary pattern. Problem statement? You're not just trying to permutate a string, right...?

Jan 18th, 2008, 11:42 PM	#6
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 837 Rep Power: 3	Re: Recursive permutation of string I fixed it: Java Syntax (Toggle Plain Text) private static void permute(char[] str, int low, int high) { if (low == high) { System.out.println(str); } else { for (int i = low; i <= high; i++) { char[] x = charArrayWithSwappedChars(str, low, i); permute(x, low + 1, high); } } } private static void permute(char[] str, int low, int high) { if (low == high) { System.out.println(str); } else { for (int i = low; i <= high; i++) { char[] x = charArrayWithSwappedChars(str, low, i); permute(x, low + 1, high); } } } Is there a way to do this without making a copy of the char array each loop iteration? Last edited by titaniumdecoy; Jan 18th, 2008 at 11:55 PM.

Jan 19th, 2008, 12:04 AM	#7
Sane Programming Guru Join Date: Apr 2005 Posts: 1,799 Rep Power: 5	Re: Recursive permutation of string I was very much confused, because you said "reverse" instead of "recurse" in your initial post at one point. So I was assuming there was some complicated problem statement missing. Okay. The key is to keep track of what you haven't added. See how the tree stems apart, and what data you want to keep track of. This algorithm can be proven qualitatively by drawing the trees. It can be proven mathematically by subproblems and dynamic programming. I'll leave that excercise up to you. Edit: In reference to your question about doing it without copying new strings: I do not believe so. This is due to the nature of dynamic programming and subproblems. If you look at the tree the reason becomes obvious. But there might be some fancy ways. Such as brute forcing it iteratively, and checking for invalid entries. So I doubt any other solutions would be efficient in any case. But I am not sure. Here it is in C: C Syntax (Toggle Plain Text) #include <stdio.h> #include <stdlib.h> #include <string.h> void permutate(char s, char r, int k, int n) { int i; char new_s; if (k==n) { // At the end r[n] = 0; // Add a null terminator printf("%s\n", r); // Output result return; } for(i=0;i<n;i++) { if (s[i]) { new_s = calloc(sizeof(char), n); // Use memcpy to ignore the null terminators memcpy(new_s, s, sizeof(char) (n+1)); new_s[i] = 0; // Mark used character r[k] = s[i]; // Store used character permutate(new_s, r, k+1, n); free(new_s); } } } int main() { char str[] = "abc"; char result_str = calloc(sizeof(char), strlen(str) + 1); permutate(str, result_str, 0, strlen(str)); return 0; } #include <stdio.h> #include <stdlib.h> #include <string.h> void permutate(char s, char r, int k, int n) { int i; char new_s; if (k==n) { // At the end r[n] = 0; // Add a null terminator printf("%s\n", r); // Output result return; } for(i=0;i<n;i++) { if (s[i]) { new_s = calloc(sizeof(char), n); // Use memcpy to ignore the null terminators memcpy(new_s, s, sizeof(char) * (n+1)); new_s[i] = 0; // Mark used character r[k] = s[i]; // Store used character permutate(new_s, r, k+1, n); free(new_s); } } } int main() { char str[] = "abc"; char result_str = calloc(sizeof(char), strlen(str) + 1); permutate(str, result_str, 0, strlen(str)); return 0; } Last edited by Sane; Jan 19th, 2008 at 12:17 AM.*

Jan 19th, 2008, 12:17 AM	#8
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 837 Rep Power: 3	Re: Recursive permutation of string I am having trouble understanding how your code works but I will figure it out eventually. How does its runtime compare to mine? (Thanks, by the way.) I really should have specified this in the beginning, but the (Java) method signature is supposed to be `void permute(char[] str, int low, int high)`. Is it possible to accomplish this without copying the string on each iteration of the loop?

Jan 19th, 2008, 12:23 AM	#9
Sane Programming Guru Join Date: Apr 2005 Posts: 1,799 Rep Power: 5	Re: Recursive permutation of string Does it work perfectly with your revision? If it does, then ours would both perform the same. It looks like we did the same thing except you swap characters in the array, rather than marking and deleting them as I did. About the string copying each iteration, I added an edit to my previous post. Heading to bed. Good luck.

Jan 19th, 2008, 12:31 AM	#10
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 837 Rep Power: 3	Re: Recursive permutation of string Thanks, Sane. I appreciate your help with this problem.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
An Attempt at a DBMS	grimpirate	PHP	8	Apr 17th, 2007 1:01 PM
Throwing an exception when using string constructor	csrocker101	C#	3	Apr 8th, 2007 2:04 PM
Help with breaking apart a string	csrocker101	C#	6	Apr 6th, 2007 7:50 AM
Permutation	Mcoy	C++	5	Mar 15th, 2006 3:22 AM
Recursive Permutation	lhk_mgtf2008	Visual Basic	2	Jul 6th, 2005 11:18 PM

Programming Forums > Application Development > Java

Recursive permutation of string