0

I have the following code which uses recursion to create a list of all permutations of an input string. I'm struggling to understand how it works. The idea of the algorithm is that the first char is taken, then it is added to each place of all permutations of the remaining characters. I don't understand how the recursion is working. If you can explain this succinctly I'd be very appreciative. This is not a duplicate question as I am looking for how this algorithm is working *not * how to get permutations of a string. I've tried stepping through and if you F11 this and follow the local variable changes, it is most confusing.

public static List<string> GetPermutations(string s)
    {
        var permutations = new List<string>();
        if (s == null)
        {
            // error case
            return null;
        }
        if (s.Length == 0)
        {
            // base case
            permutations.Add("");
            return permutations;
        }

        char first = s[0]; // get the first character
        string remainder = s.Substring(1); // remove the first character
        List<string> words = GetPermutations(remainder);
        foreach (string word in words)
        {
            for (int j = 0; j <= word.Length; j++)
            {
                permutations.Add(insertCharAt(word, first, j));
            }
        }
        return permutations;
    }

    public static string insertCharAt(string word, char c, int i)
    {
        string start = word.Substring(0, i);
        string end = word.Substring(i);
        return start + c + end;
    }
}
Simon Ryan
  • 212
  • 1
  • 9
  • 1
    How many of the dozens of duplicates of this question did you read before deciding to post yet another one? – Ken White Nov 29 '13 at 14:44
  • 1
    Suggestion - grab a pen and paper and write out what happens, or debug the code. – Bernhard Barker Nov 29 '13 at 14:51
  • Though I do think this question is off topic, I don't think some of the commenters read the questions. The OP isn't asking for the algorithm, he's asking for an ***explanation*** of the algorithm. – James Webster Nov 29 '13 at 14:52
  • Probably belongs on [programmers.se] – James Webster Nov 29 '13 at 14:56
  • @JamesWebster Are you sure? I don't think it will be taken well on there (either). – Bernhard Barker Nov 29 '13 at 15:01
  • @Dukeling, No, I'm not certain. I'm not really an active member on programmers so not sure on what questions are off topic there. I'm quite certain it's off topic here though. – James Webster Nov 29 '13 at 15:04
  • I've stepped through the code, I've tried to understand, I've sat with a colleague who also doesn't understand. This post is due to exhausting all other possibilities. Please, useful comments only... – Simon Ryan Nov 29 '13 at 15:05
  • it's a simple implementation of the recursive algorithm for permutations. it's the same algorithm you'll find described anywhere. take the first character off. then a perumtation is a permutation of the rest, plus the first crharacter added at each possible position. – andrew cooke Nov 29 '13 at 15:05
  • If it's so simple @andrewcooke it won't take you long to describe it please :) – Simon Ryan Nov 29 '13 at 15:08
  • 1
    There's a good explanation here: http://stackoverflow.com/q/7537791/56778 – Jim Mischel Nov 29 '13 at 15:08
  • actually, i don't think jim's link describes the same algorithm (so apparently it's not the same you find everywhere...). – andrew cooke Nov 29 '13 at 15:11
  • I have indicated that I understand the concept of the algorithm. I do not understand how the recursion achieves this. Thanks @JimMischel for the link I'll see if that helps. – Simon Ryan Nov 29 '13 at 15:14
  • the recursion achieves it by doing exactly what the algorithm says. it provides the permutation of the rest. by following the algorithm. each time the recursion happens, the string is shorter, because another initial character has been stripped off. eventually there are no characters and the only permutation is "" (empty string). then things start to return and start inserting their letters... – andrew cooke Nov 29 '13 at 15:46
  • Thanks @andrewcooke, it's the 'then things start to return' bit that I don't understand. Return from where? None of the values created in the recursive loop are stored anywhere and when debugging, the variables are always reset on each call. Maybe I'm just not understanding how recursion works although all the simpler examples I've seen make perfect sense – Simon Ryan Nov 29 '13 at 15:51
  • the list "permutations" is returned and used as "words", which creates a new perumtations, which is returned and used as words, which creates.... it's a bit messy and creates a new list one each return as the stack unwinds. – andrew cooke Nov 29 '13 at 15:55
  • when you return then the variables that were in at that point are "still there". each call gets a new set, but the old set re-appear when you return. maye that is what you are missing? – andrew cooke Nov 29 '13 at 16:01
  • @andrewcooke that is indeed what I'm missing. Thank you – Simon Ryan Nov 29 '13 at 16:40
  • no problem. it's just experience. if you have the time / inclination to learn a functional programming language you'll soon wonder how you could ever not have understood something like this. it becomes very familiar and easy with practice. – andrew cooke Nov 29 '13 at 16:43

0 Answers0