Programming Forums
Page 1 of 2 1 2 >
Show 40 post(s) from this thread on one page

Programming Forums (http://www.programmingforums.org/forumindex.php)
-   Java (http://www.programmingforums.org/forum17.html)
-   -   Recursive permutation of string (http://www.programmingforums.org/showthread.php?t=14977)

titaniumdecoy Jan 18th, 2008 10:04 PM
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...

:
  1. public class RecursivePermutation {
  2.  
  3.         public static void main(String[] args) {
  4.  
  5.                 String str = "abc";
  6.                 permute(str);
  7.  
  8.         }
  9.  
  10.         public static void permute(String str) {
  11.                 permute(str.toCharArray(), 0, str.length() - 1);
  12.         }
  13.  
  14.         private static void permute(char[] str, int low, int high) {
  15.                 [b]System.out.println(str);[/b]
  16.                 if (low > high) return; 
  17.                 for (int i = low; i <= high; i++) {
  18.                         char[] x = charArrayWithSwappedChars(str, low, i);
  19.                         permute(x, low + 1, high);
  20.                 }
  21.         }
  22.  
  23.         private static char[] 
  24.         charArrayWithSwappedChars(char[] str, int a, int b) {
  25.                 char[] array = str.clone();
  26.                 char c = array[a];
  27.                 array[a] = array[b];
  28.                 array[b] = c;
  29.                 return array;
  30.         }
  31.  
  32. }

Output:
:
abc
abc
abc
acb
acb
bac
bac
bac
bca
bca
cba
cba
cba
cab
cab

Sane Jan 18th, 2008 10:15 PM
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?

titaniumdecoy Jan 18th, 2008 11:09 PM
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.

Sane Jan 18th, 2008 11:14 PM
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...?

titaniumdecoy Jan 18th, 2008 11:27 PM
Re: Recursive permutation of string
 
Quote:
Originally Posted by Sane (Post 139871)
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
Re: Recursive permutation of string
 
I fixed it:

:
  1. private static void permute(char[] str, int low, int high) {
  2.     if (low == high) {
  3.         System.out.println(str);
  4.     } else {
  5.         for (int i = low; i <= high; i++) {
  6.             char[] x = charArrayWithSwappedChars(str, low, i);
  7.             permute(x, low + 1, high);
  8.         }
  9.     }
  10. }

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
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:

:
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. void permutate(char *s, char *r, int k, int n) {
  6.     int i;
  7.     char *new_s;
  8.     if (k==n) {              // At the end
  9.         r[n] = 0;            // Add a null terminator
  10.         printf("%s\n", r);   // Output result
  11.         return;                                     
  12.     }
  13.     for(i=0;i<n;i++) {
  14.         if (s[i]) {
  15.             new_s = calloc(sizeof(char), n);       
  16.  
  17.             // Use memcpy to ignore the null terminators 
  18.             memcpy(new_s, s, sizeof(char) * (n+1)); 
  19.             new_s[i] = 0;      // Mark used character
  20.             r[k] = s[i];       // Store used character
  21.             permutate(new_s, r, k+1, n); 
  22.             free(new_s);
  23.         }
  24.     }
  25. }
  26.  
  27. int main() {
  28.  
  29.     char str[] = "abc"; 
  30.     char *result_str = calloc(sizeof(char), strlen(str) + 1); 
  31.  
  32.     permutate(str, result_str, 0, strlen(str));
  33.     return 0;
  34. }

titaniumdecoy Jan 19th, 2008 12:17 AM
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?

Sane Jan 19th, 2008 12:23 AM
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.

titaniumdecoy Jan 19th, 2008 12:31 AM
Re: Recursive permutation of string
 
Thanks, Sane. I appreciate your help with this problem.


All times are GMT -5. The time now is 10:04 AM.
Page 1 of 2 1 2 >
Show 40 post(s) from this thread on one page

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC