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 ?

You're adding multiple references to the same array(you only have one) to your List (assuming permutations is a list). — Mark Peters, Apr 06 '16 at 20:44
Your list is defined as readonly. Forgive if I am wrong, but doesn't readonly mean it can only be read, not modified. Probably why it can't be modified. Just a thought — JSON, Apr 06 '16 at 20:52
@JSON `List` is a reference type so it means the _reference_ is read-only. The contents can be modified but the field cannot be set to reference a _new_ list, for example. — D Stanley, Apr 06 '16 at 20:59
@JSON Readonly means the reference to the list _itself_ cannot be modified outside of it's declaration or the class constructor but readonly places no such restrictions on the _contents_ of the list. — Stainy, Apr 06 '16 at 21:00
@JSON -- You can use `List.AsReadOnly()` to return a `ReadOnlyCollection`. Very handy. — rory.ap, Apr 06 '16 at 23:00

score 3 · Accepted Answer · answered Apr 06 '16 at 20:47

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.

score 0 · Answer 2 · edited May 23 '17 at 12:31

As you can learn from this answer, all the array are reference types.

This means, that when you are adding the array to the list of arrays in this line of code:

permutations.Add(list);

You are actually adding the same array over and over again. Since each time, you swap the values in that array back and forth, you get a list of the references to the same exact array.

If I understand correctly, you want to make a list of all possible orders of chars in the first array you create.

For that, you need to clone you array, and not use the same reference.

Bottom line:

You should change your add to collection line to this:

permutations.Add((char[])list.Clone());

This way, you are not adding the same reference, but a clone of it, and you final list will be full of different array.

Losing values from list when leaving method

2 Answers2

Bottom line: