Find all permutation and return result as List<string>

Question

I have following code written in c#.In which I am printing permutation of string.

void Main()
{
    RecPermute("", "abc");

}



void RecPermute(string soFar, string rest) {
    if (rest == "") {
        soFar.Dump();
    } else {
        for(int i=0; i<rest.Length; i++) {
            string next = soFar + rest[i];
            string remaining = rest.Substring(0, i) + rest.Substring(i+1);
            RecPermute(next, remaining);
    }
    }
}

Now I change the signature of method as below.

List<string> RecPermute(string soFar, string rest)

and change the code

List<string> RecPermute(string soFar, string rest) {
List<string> result=new List<string>();
    if (rest == "") {
        //soFar.Dump();
        result.Add(soFar);
    } else {
        for(int i=0; i<rest.Length; i++) {
            string next = soFar + rest[i];
            string remaining = rest.Substring(0, i) + rest.Substring(i+1);
            RecPermute(next, remaining);
    }
    }
    return result;
}

The problem is that I am not getting any result.

Aleksei Poliakov · Accepted Answer · 2013-12-02 09:23:19Z

1

You have List<string> result=new List<string>(); as local variable. This is what you want

List<string> result=new List<string>(); // NOT LOCAL!!!
List<string> RecPermute(string soFar, string rest) {

    if (rest == "") {
        //soFar.Dump();
        result.Add(soFar);
    } else {
        for(int i=0; i<rest.Length; i++) {
            string next = soFar + rest[i];
            string remaining = rest.Substring(0, i) + rest.Substring(i+1);
            RecPermute(next, remaining);
    }
    }
    return result;
}

Please, not that using a class level variable to store the result is most likely a bad idea. I used this only as an example to point out that when result is local - it does not get populated with data.

Read the comments for this answer - there are different solutions for this problem, my personal favorite is to use a parameter:

    private List<string> RecPermute(string soFar, string rest, List<string> tmp = null)
    {
        if (tmp == null) tmp = new List<string>();
        if (rest == "")
        {
            //soFar.Dump();
            tmp.Add(soFar);
        }
        else
        {
            for (int i = 0; i < rest.Length; i++)
            {
                string next = soFar + rest[i];
                string remaining = rest.Substring(0, i) + rest.Substring(i + 1);
                RecPermute(next, remaining, tmp);
            }
        }
        return tmp;
    }

edited Dec 2, 2013 at 9:23

answered Dec 2, 2013 at 7:37

Aleksei Poliakov

1,3322 gold badges14 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

Grundy Over a year ago

or change to result.AddRange(RecPermute(next, remaining));

Aleksei Poliakov Over a year ago

@Grundy Your solution also works (dotnetfiddle.net/w0AqFN), but in this case a lot of temporary lists are created. If this is supposed to be static implementation - a new parameter can be added - this is still cheaper in terms of memory than creating several lists (like this - dotnetfiddle.net/IaEfse)

FreeNickname Over a year ago

Using a global variable as a temporary variable for a function result is bad. This function should be rewritten to be recursive. So we should return something from the else block too. Then we won't need a global variable. I wanted to do it, but I couldn't do it right away, and unfortunately, I don't have time for it now :(

Aleksei Poliakov Over a year ago

@FreeNickname Why? If you have an class with the logic and getting permutations is only one step of the algorithm - getting a private field to contain the result is exactly what you need to do! This will remove the pressure from passing parameters to all the methods that implement algorithm's steps.

user2893534 Over a year ago

@DarkWalker:After making changes code is working fine.I have one question what is general rule for handling this thing in recursion

|

Collectives™ on Stack Overflow

Find all permutation and return result as List<string>

1 Answer 1

11 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

11 Comments

Your Answer

Sign up or log in

Post as a guest

Related