Thread: 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).