Losing values from list when leaving method

Question

I'm having trouble's with 2 List's in the following code :

internal class Program
{
    private static readonly List<char[]> permutations = new List<char[]>();

    private static void Main()
    {
        string str = "0123456789";
        char[] arr = str.ToCharArray();
        GetPer(arr);
        //2. here we have lost all the values
        Console.ReadKey();
    }

    private static void Swap(ref char a, ref char b)
    {
        if (a == b) return;
        a ^= b;
        b ^= a;
        a ^= b;
    }

    public static void GetPer(char[] list)
    {
        int x = list.Length - 1;
        GetPer(list, 0, x);
    }

    private static void GetPer(char[] list, int k, int m)
    {
        if (k == m)
        {
            permutations.Add(list); //1. here we add value to the list
        }
        else
            for (int i = k; i <= m; i++)
            {
                Swap(ref list[k], ref list[i]);
                GetPer(list, k + 1, m);
                Swap(ref list[k], ref list[i]);
            }
    }
}

There are 2 comments the first one is in the void GetPer where we add values to the list. The second comment is in the void Main where we have lost all the previous values. The code is mostly copy pasted from here Listing all permutations of a string/integer if any explanation is needed. How can I avoid this reference type problem ?

Answer 1

You are adding a reference to the same list over and over again. The method you copied swaps two values, recursively runs another permutation, and swaps them back. Eventually after you run through all of the permutations, the list is back to where it started.

The original program just wrote the permutation to the console, so it didn't matter that the change was being unwound after each permutation. If you make a clone of the list when adding it to the result you should see all permutations:

private static void GetPer(char[] list, int k, int m)
{
    if (k == m)
    {
        permutations.Add((char[])(list.Clone())); //1. here we add a clone of the value to the list
    }
    else
        for (int i = k; i <= m; i++)
        {
            Swap(ref list[k], ref list[i]);
            GetPer(list, k + 1, m);
            Swap(ref list[k], ref list[i]);
        }
}

I would note that I discovered this not be reading "your" code, but by debugging it. Strategically placed breakpoints and watches make problems like this easier to solve. Debugging is an invaluable skill for understanding problems in code, especially code you didn't write.