Permutation of string without recurssion

Question

Here is the recursive code.
Can you guys give inputs on how I can implement this using iterative method?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PermAndComb
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = "abcd";
            Permutation(s);
            Console.ReadKey();

        }

        public static void Permutation(string s)
        {
            int len = s.Length;
            char [] inStr  = s.ToCharArray();
            StringBuilder outStr = new StringBuilder();
            bool[] used = new bool[len];

            doPermute(inStr, outStr,used, len, 0);

        }

        public static void doPermute(char[] instr, StringBuilder outStr,bool [] used, int len, int level)
        {
            if (level == len)
            {
                Console.WriteLine(outStr.ToString());
                return;
            }

            for (int i = 0; i < len; i++)
            {
                if (used[i]) continue;
                outStr.Append(instr[i]);
                used[i] = true;
                doPermute(instr, outStr, used, len, level + 1);
                used[i] = false;
                outStr.Length = outStr.Length - 1;

            }

        }
    }
}

Answer 1

This article is rather heavy on the math, but might help out:
http://msdn.microsoft.com/en-us/magazine/cc163513.aspx

In summary, you use factoradics to enumerate the permutation in lexical order. And if that sounds like Greek to you, you're not alone.

Now, that's the correct way to do it (at least until a math PhD figures out something better). But I doubt it's what they're looking for in an interview. More likely, they're looking for an understanding that any recursive problem is also a stack problem that just uses the program's call stack rather than building it's own.

So you can convert any recursive code to iterative by taking a stack, pushing the initial value, then looping while the stack is not empty. Inside the loop you pop the next value, make the same calculation you would have made in your recursive function and push everywhere you would have made a recursive call.

Answer 2

the factoradics approach is less work than you'd be led to expect based on the article. I've had to use similar approach on many a Project Euler problem.

string str = "abcd";

Func<int, int> factorial = n => 
    Enumerable.Range(1, n)
    .Aggregate((i, j) => i * j);
Func<int, int[]> tofactoradic = n =>
    Enumerable.Range(1, n)
    .Reverse()
    .Select(i => { var m = n; n /= i; return m % i; })
    .ToArray();
Func<int[], string, string> Apply = (f, s) => {
    var chars = s.ToList();
    var result = "";
    for (int i = 0; i < s.Length; i++) {
        result += chars[f[i]];
        chars.RemoveAt(f[i]);
    }
    return result;
};

int max = factorial(str.Length);
for (int i = 0; i < max; i++ ) {
    var f = tofactoradic(i);
    Console.WriteLine(Apply(f, str));
}