Results 1 to 6 of 6

Thread: Soft Coding.

  1. #1
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default 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;
        }
    }
    Okay, this code makes a random char array of length 4, and prints all 24(4!) possible strings with those 4 characters.

    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.

  2. #2
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    I was thinking recursion, but my head has been spinning trying to come with an exact implementation.

  3. #3
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    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]
    Recursion is not a bad idea here. The idea of recursion is
    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 one-character (or zero-character) 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]        }
    Now let's think about a concrete example to make the next part more understandable. Let's say we start with the String "ABCD". Our list of permutations will have some Strings that start with "A", followed by each permutation of "BCD", then Strings that start with "B", followed by each permutation of "ACD", then Strings that start with "C", followed by each permutation of "ABD", then finally Strings that start with "D", followed by each permutation of "ABC". So that means we want to loop through our original String, and for each character, get the permutations of the remaining String and prepend our character to each of them. (We're removing one character from our String, so we know eventually the input String will have a length of 1.)


    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;
            }
    That's it. The funny thing about writing recursive methods is that you're usually done before you think you're done. :)

    -Gary-

  4. #4
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,355
    Blog Entries
    7
    Rep Power
    20

    Default

    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,

    Jos
    Last edited by JosAH; 06-13-2010 at 09:25 AM.

  5. #5
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    Thanks guys,

    too tired to really try/understand it at the moment, but i will later lol.

  6. #6
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    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

  1. Coding help
    By Java_Fanatic in forum New To Java
    Replies: 7
    Last Post: 10-15-2009, 04:37 AM
  2. coding help
    By accies76 in forum New To Java
    Replies: 5
    Last Post: 11-12-2008, 08:15 PM
  3. rii-soft Arcade - for game players/ developers
    By rii in forum Reviews / Advertising
    Replies: 0
    Last Post: 08-18-2008, 04:13 PM
  4. Soft HashMap
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-12-2008, 08:45 PM
  5. Soft References
    By rickcharles_b in forum Advanced Java
    Replies: 0
    Last Post: 06-20-2007, 08:27 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
  •