How to generate all possibilities of a string with X tokens and Y values for each token

Question

So, I have a template string with X amount of tokens in it. Hypothetically it could look like this:

template = "render=@layer0@-@layer1@-@layer2@-@layer3@-@layer4@"

The tokens, obviously, take the form of @tokenname@. In this hypothetical case it has five tokens. Each token has a different set of possible values. For example:

token0Values = ['t0value1'];
token1Values = ['t1value1','t1value2'];
token2Values = ['t2value1','t2value2','t2value3'];
token3Values = ['t3value1','t3value2'];
token4Values = ['t4value1','t4value2','t4value3','t4value4'];

My question then is, how do I generate every possible permutation of the string given the template and the possible values for each token?

Answer 1

I'll take a stab at it in sorta php/AS

tokens is a two dimensional array of possible values

{ [0] = "apple","banana","pear" [1] = "carrot","pea" [2] = "potato", "celery", "butter","gravy" }

function getPermutations(tokens){

       var perms = array();

       //exit condition : there's only one token; 
       //total permutations = values array
       //so just return it

       if (tokens.length == 1)
           return tokens[0];

       //otherwise  
       //strip 1st element of the array as your "prefix"   

       prefices= tokens.shift();

       //get the permuations of the children

       childPermutations = getPermutations(tokens);

       //loop through the possible values, or "prefices"

       foreach (prefices as prefix){

            //concatenate to each of the child permutations

            foreach(childPermutations as perm)
                perms[]=prefix + perm;
       }

       //return the glob
       return perms;
}

that might work, or something similar