Results 1 to 6 of 6
Thread: Soft Coding.
 06122010, 09:49 PM #1Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
Soft Coding.
Java Code:import java.util.Random; public class StringPossibilities { static char[] letters = new char [4]; static Random gen = new Random (); public static void main (String[] args) { for (int i = 0 ; i < 4 ; i++) letters [i] = ((char) ((gen.nextInt (26) + 97))); for (int i = 0 ; i < 4 ; i++) { for (int j = 0 ; j < 4 ; j++) { for (int k = 0 ; k < 4 ; k++) { for (int l = 0 ; l < 4 ; l++) { if (!duplicates (new int[] {i, j, k, l})) { System.out.println (stringOrder (letters, new int[]{i, j, k, l})); } } } } } } static public String stringOrder (char[] chars, int[] order) { if (chars.length == order.length) { char[] newChars = new char [chars.length]; for (int i = 0 ; i < newChars.length ; i++) { newChars [i] = chars [order [i]]; } return new String (newChars); } else { return "unacceptable parameters"; } } static public boolean duplicates (int[] array) { for (int i = 0 ; i < array.length ; i++) { for (int j = i+1 ; j < array.length ; j++) { if (array [i] == array [j]) { return true; } } } return false; } }
This is good for my assignment, this is all that is asked, however I have never been satisfied with just completeing enough for this class.
So how could i softcode this to work with any length of char array?
Thanks.
 06122010, 09:54 PM #2Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
I was thinking recursion, but my head has been spinning trying to come with an exact implementation.
 06122010, 10:43 PM #3Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 6
OK, you want to generate a list of permutations, so let's start with a method signature that returns a list:
Java Code:[B] public List<String> listPermutations(String input) { } [/B]
1. Identify a base case from which we know that no more recursion is needed, and return a simple result.
2. For all other cases, do the simple part, and let the next recursive call do the hard part.
3. Make sure that the modifications we make to our parameters will tend toward the base case, so that we'll reach termination at some point.
When generating permutations of a String, the base case is a onecharacter (or zerocharacter) String, that has only one permutation.
Java Code:public List<String> listPermutations(String input) { [B] List<String> results = new ArrayList<String>(); if (input.length() <= 1) { results.add(input); } return results; [/B] }
Java Code:public List<String> listPermutations(String input) { List<String> results = new ArrayList<String>(); if (input.length() <= 1) { results.add(input); [B] } else { for (int i = 0; i < input.length(); i++) { char c = input.charAt(i); String remainder = input.substring(0, i) + input.substring(i + 1); for (String s : listPermutations(remainder)) { results.add(c + s); } } [/B] } return results; }
Gary
 06132010, 09:21 AM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,943
 Blog Entries
 7
 Rep Power
 22
If you want to generate permutations in lexicographical order you don't need recursion at all. There is a simple iterative algorithm that also works if there are duplicates in your 'set'; here's how it works:
given a set p_1, p_2, p_3 ... p_n that is marked as the 'current' permutation;
1) find the rightmost i such that p_i < p_(i+1);
2) if no such i can be found there is no 'next' permutation given the 'current' one;
3) find the rightmost j > i such that p_j > p_i; note that such j always exists;
4) swap the elements p_i and p_j;
5) reverse the elements p_(i+1) ... p_n.
after these five steps have completed succesfully you have found a next permutation; repeat those steps until step 2) fails.
Here's a small example: given the permutation ACDEB; step 1) says that p_i == D (D < E); and step 3) says that p_j == E (E > D); step 4) results in: ACEDB and step 5) results in ACEBD which is the next permutation for ACDEB in lexicographical order. If you start with ABCDE, apply the above algorithm ad nauseam you'll find all the permutations of ABCDE.
kind regards,
JosLast edited by JosAH; 06132010 at 09:25 AM.
 06132010, 03:29 PM #5Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
Thanks guys,
too tired to really try/understand it at the moment, but i will later lol.
 06132010, 09:56 PM #6Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 6
My version will generate duplicates. To eliminate them, you could use a HashSet<String> instead of an ArrayList<String>.
The big advantage of JosAH's approach is that there is no need to keep a list of existing permutations in memory, which the recursive approach requires. You can do everything with the one char array, printing out the permutations (or writing them to a file, if you prefer) as you go. This means you can permute much longer Strings.
Gary
Similar Threads

Coding help
By Java_Fanatic in forum New To JavaReplies: 7Last Post: 10152009, 04:37 AM 
coding help
By accies76 in forum New To JavaReplies: 5Last Post: 11122008, 09:15 PM 
riisoft Arcade  for game players/ developers
By rii in forum Reviews / AdvertisingReplies: 0Last Post: 08182008, 04:13 PM 
Soft HashMap
By Java Tip in forum java.langReplies: 0Last Post: 04122008, 08:45 PM 
Soft References
By rickcharles_b in forum Advanced JavaReplies: 0Last Post: 06202007, 08:27 PM
Bookmarks