Text spinning permutations

Question

I want to get the number of permutations of spinning text:

My text:

{abc|{cde|fgh}} aaa {cde|fg}.

Result should be 6 (3x2)

I want to get permutations to unlimited number of nested words.

How can I do that? I tried to flat text to {abc|cde|fgh} {cde|fg} and then just do 3x2, but how I can flat this text, I have problem with this, could anyone can help me?

I want to do this in php or javascript.

For anyone not sure what this is, take a look at: [What is Spintax](http://ultimatemarketingstrategies.net/what-is-spintax). — Xantix, Jul 25 '12 at 05:22
See this : [Method to generate all permuatuons of spinnable strings](http://stackoverflow.com/questions/8331020/how-can-find-all-permutations-of-spinning-text-in-c-sharp) — LeMoussel, Oct 24 '13 at 13:22

Xantix · Answer 1 · 2012-07-25T07:00:41.103

The first solution that comes to mind is to create a recursive method.

Recursive Method

The recursive method takes a string, and returns the number of ways to permute it.

Base Case:

The base case: if there are no '{' and '}' in the string, return the number of '|' symbols in the string plus 1.

Otherwise:

Find the position of the first '{', call it Pos1.

Find the '}' it corresponds with, call it Pos2.

Now form the 3 substrings [0 to Pos1), ( Pos1 to Pos2 ), (Pos2 to End]

Be careful to recognize that the Pos1 and Pos2 aren't included in the substrings, so we lose two braces.

return product/sum of recursing on each of the substrings.

Here's C# code that demonstrates the above algorithm:

static void Main(string[] args)
{

    string test1 ="{abc|{cde|fgh}} aaa {cde|fg}.";

    int numWays = getNumWaysRecursive(test1);

    Console.WriteLine("NumWays: " + numWays);
    Console.ReadLine();
}

private static int getNumWaysRecursive( string s )
{
    if (s == null) return 1;
    if (s == "") return 1;

    int firstBracePos = s.IndexOf('{');

    if (firstBracePos == -1) //Base case, no braces.
    {
        int pipeCount = 0;

        for (int i = 1; i < s.Length - 1; i++)
        {
            if (s[i] == '|')
            {
                if (pipeCount == -1)
                {
                    pipeCount = 0;
                }
                pipeCount++;
            }
        }

        return pipeCount + 1;
    }

    //Non-Base case:
    // find the first Left Brace
    // find the right brace it corresponds with

    int numOfNests = 0;
    int pos = firstBracePos + 1;

    while (pos < s.Length)
    {
        if (s[pos] == '}')
        {
            numOfNests--;
            if (numOfNests == -1)
            {
                break;
            }
        }

        else if (s[pos] == '{')
        {
            numOfNests++;
        }

        pos++;
    }

    //Get rid of those braces, and recurse on the three parts:
    // 1. the part before the braces.
    // 2. the part between the braces.
    // 3. the part after the braces.

    string firstPart; 
    if (firstBracePos == 0)
    {
        firstPart = "";
    }
    else
    {
        firstPart = s.Substring(0, firstBracePos);
    }

    string secondPart = s.Substring(firstBracePos + 1, pos - firstBracePos - 1);
    string lastPart = s.Substring(pos + 1 );

    int sum1 = getNumWaysRecursive(firstPart); 
    int sum2 = getNumWaysRecursive(secondPart);
    int sum3 = getNumWaysRecursive(lastPart);

    bool strng1HasPipes = (firstPart.IndexOf('|') != -1);

    int sum = 1;

    if ( strng1HasPipes )
    {
        sum += sum1 - 1;
        sum += sum2;
    }
    else
    {
        sum *= sum2;
    }

    if (sum3 == 0)
    {
        ;
    }
    else
    {
        sum *= sum3;
    }

    return sum;
}

Unfortunately, this doesn't quite capture the whole situation.

it fails on strings like "{abc|{cde|fgh}} aaa {cde|fg} eee | {abc | bbb }."

since it doesn't quite understand the nesting position of that second-to-last pipe symbol since it isn't nested within any braces.

so you should do an initial scan of the string and break it into substrings based on '|' symbols that are not within braces, then add the subtotals together of those substrings.

Text spinning permutations

1 Answers1

Recursive Method