Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: Need help with finding a differnt algorithm

  1. #1
    Member
    Join Date
    Mar 2011
    Location
    Earth!
    Posts
    77
    Thanks
    2
    Thanked 1 Time in 1 Post

    Default Need help with finding a differnt algorithm

    Hi all.

    I have this problem with an algorithm. To put things simple, I have a method that creates a string to a collection of strings. I am using it in a small mini-language (it seems to primitive to be called a scripting language) I have been working on for fun. It has one type, collections of strings, and you can create new ones by combining old ones, and I am doing it through the method I mentioned. For example, if I have a variable $number containing the strings "1", "2" and "3" and then parse this line:
    hello$number
    you get a new collection with the following strings:
    hello1
    hello2
    hello3

    A more advanced example, where $numbers contaings the strings "1" and "2" and $words contains "sun", "moon" and "donkey":
    $numbers and $words
    You will get a new collection containg the following strings if you parse it:
    1 and sun
    1 and moon
    1 and donkey
    2 and sun
    2 and moon
    2 and donkey

    Basically the string kind of works like a template for creating new collections, using variables (variables are identified with the dollar sign, btw). The current algorithm has an issue, though. It causes stack overflow rather easy, if there is a lot of different combinations to create. Think it is because it is recursive. So I guess I would have to find an iterative solution to the problem. But I am not sure where to begin. For some reason I have some real trouble figuring out the proper iterative algorithm. Could anyone help me?

    And here is the current code, if it helps. It is not very optimized, quite frankly I feel a bit embarrast about it (and about my own failure at spelling ), but this is how it looks atm.
    public class Utilities {
        /**
         * Returns a list of all permutations of the given string
         * 
         * @param str the string that may or may not contain variable references
         * @param vtable the map of variables
         * @return a collection containing all permutations of the given string
         */
        public static Collection<String> getPermutations(String str, Map<String, Collection<String>> vtable) {
            // Check if the string contains variables or not (the $ sign)
            if (str.contains(Lang.VAR_ID)) {
                // Check if the variable starts at the first index or not
                int index = str.indexOf(Lang.VAR_ID);
                if (index > 0) {
                    // If the variable did not start at the first index separate the parts with and
                    // without the variables
                    String withVars = str.substring(index);
                    str = str.substring(0, index);
     
                    // Combine the string with whatever was in the variables
                    return combine(Arrays.asList(str), createPermutations(withVars, vtable));
                }
                return createPermutations(str, vtable);
            }
            // If no variables existed, return a collection containing the given string
            return Arrays.asList(str);
        }
     
        /**
         * Basically, what this method does is to generate a collection of strings containing all possible permutations,
         * or combinations if you prefer, of the variables in them
         * 
         * @param str the string to parse
         * @param vtable the map containing the variables
         */
        private static Collection<String> createPermutations(String str, Map<String, Collection<String>> vtable) {
            // Get the smallest valid index of an array
            int index = minIndex(str.indexOf(Lang.VAR_ID, 1),
                                 str.indexOf(Lang.SPACE));
     
            // If the returned index is not -1 then get the variable and combine with the result from a recursive call
            // to getPermutations
            if (index > -1) {
                String next = str.substring(index);
                str = str.substring(0, index);
                return combine(vtable.get(str), getPermutations(next, vtable));
            }
            else {
                // If the index was -1 then the entire string van be assumed to be a variable name
                return vtable.get(str);
            }
        }
     
        // NOTE: Dont worry about the methods bellow this point, I just included them to make it clear where they come from since they are used by the relevant methods
     
        /**
         * Returns the smallest valid index for a string or -1, if none of
         * them where valid
         * 
         * @param a one index
         * @param b another index
         * @return the smallest valid index or -1 if no index was valid
         */
        public static int minIndex(int a, int b) {
            if (a < 0)
                return (b < 0) ? -1 : b;
            else if (b < 0)
                return (a < 0) ? -1 : a;
            return Math.min(a, b);
        }
     
        /**
         * Combines the left and right collections by adding each string in the right collection to each and every
         * string in the left collection
         * 
         * @param left a collection of strings
         * @param right a collection of strings
         * @return the collection that resulted from the combination
         */
        private static Collection<String> combine(Collection<String> left, Collection<String> right) {
            Collection<String> combined = new ArrayList<>(left.size() + right.size());
            for (String ls : left) {
                for (String rs : right) {
                    combined.add(ls + rs);
                }
            }
            return combined;
        }
    }
    Have tried to comment it as best as I can, but, well, I am terrible at figuring out good comments :p. And as I already said, the code is not optimized at all, I just realized the issue of stack overflow before I had a chance to clean up in it. The method getPermutations is the one i talked about above. It will make a call to createPermutations which in turn will call getPermutations. If you want I can try and describe more in detail how they work but since I am after a different algorithm I dont really know if I need to.

    So, can anyone help me figure out the right algorithm? What would the best problem be to solve this problem? Thinking of an algorithm that does not cause a stack overflow when there are too may different combinations that will be generated (which means it probably has to be iterative). Sorry if I could not describe my problem in a good way, I am not good with describing things :p.

    Take care,
    Kerr.

    EDIT: There are two methods in the code, minIndex and combine, they work as they should. So dont worry about them (just included them so it would be clear where they came from).
    Last edited by Kerr; November 25th, 2011 at 06:43 PM.


  2. #2
    Member
    Join Date
    Mar 2011
    Location
    Earth!
    Posts
    77
    Thanks
    2
    Thanked 1 Time in 1 Post

    Default Re: Need help with finding a differnt algorithm

    Anyone know? Will try and explain myself again, lol.

    What I want, now that I think of it, is a algorithm that works this, but in an iterative manner (the one I have does it recursively).
    First combination: aehl
    [a] [e] [h] [l]
    b f i m
    c g j n
    d k

    Second combination: aehm
    [a] [e] [h] l
    b f i [m]
    c g j n
    d k

    Third combination: aehn
    [a] [e] [h] l
    b f i m
    c g j [n]
    d k

    Forth combination: aeil
    [a] [e] h [l]
    b f [i] m
    c g j n
    d k

    Fifth combination: aeim
    [a] [e] h l
    b f [i] [m]
    c g j n
    d k

    Seventh combination: aein
    [a] [e] h l
    b f [i] m
    c g j [n]
    d k

    Eighth combination: aejl
    [a] [e] h [l]
    b f i m
    c g [j] n
    d k

    And so on... And yes, I am horrible at describing things :p.

Similar Threads

  1. Finding Chromatic Number w/ Brute Force Algorithm
    By thecrazytaco in forum Algorithms & Recursion
    Replies: 2
    Last Post: November 16th, 2011, 07:35 AM
  2. Finding Chromatic Number of a Simple Graph w/ Brute Force Algorithm
    By thecrazytaco in forum What's Wrong With My Code?
    Replies: 3
    Last Post: November 15th, 2011, 09:27 PM
  3. calling objects in a differnt class
    By jack_nutt in forum Object Oriented Programming
    Replies: 12
    Last Post: July 8th, 2011, 02:57 PM
  4. finding the end of ram
    By timmin in forum What's Wrong With My Code?
    Replies: 1
    Last Post: April 3rd, 2011, 10:42 AM
  5. finding pi
    By gonfreecks in forum File I/O & Other I/O Streams
    Replies: 4
    Last Post: November 2nd, 2010, 06:15 PM