List reset on every recursion when attempting to permute

Question

I am attempting to generate all the permutations of a list but every time I recurse the list I pass in gets reset back to its original state, what's up with that?

public static void PermuteAndSolve(List<City> cities, int recursionLevel, int Length)
    {
        if (recursionLevel == Length)
        {
            foreach (City city in cities)
            {
                Console.Write(city.name);
            }
            Console.WriteLine("");
        }
        else
        {
            for (int i = recursionLevel; i <= Length; i++)
            {
                swap(cities, recursionLevel, Length);
                PermuteAndSolve(cities, recursionLevel + 1, Length);
                swap(cities, recursionLevel, Length);


            }
        }
    }

I know swap works correctly.

Ignore the fact that it's called PermuteAndSolve and doesn't do any solving atm — Awia, May 04 '15 at 00:21
swap literally swaps the 2 values specified in the list and by reset I mean that it changes back to the original list passed into the function — Awia, May 04 '15 at 00:24
What are you trying to do here? Maybe there is a less confusing way to do it? — Asad Saeeduddin, May 04 '15 at 00:25
permutation without recursion is a bit of a ball ache but if you can think of a simpler way to do it please tell me — Awia, May 04 '15 at 00:27

score 0 · Answer 1 · answered May 04 '15 at 00:52

0

I don't pretend to understand exactly what this code is doing, but surely you can achieve what you are trying to do without the mind-bending recurssion? Something like this (CAUTION: untested):

public static void PermuteAndSolve(List<City> cities, int Length)
{
    int recursionLevel = 0;
    while(recursionLevel < Length)
    {
        for (int i = recursionLevel; i <= Length; i++) {
            swap(cities, recursionLevel, Length);
        }
        recursionLevel++;
    }

    foreach(City city in cities)
    {
        Console.Write(city.name);
    }
    Console.WriteLine("");
}

May not be correct, but hopefully you get my point.

answered May 04 '15 at 00:52

garryp

5,508
1
29
41

It's supposed to create and print all the permutations of a list, which it does if I step through with the debugger but doesn't when it actually prints them. Your code doesn't permute it just swaps things about a bit as far as I can tell. – Awia May 04 '15 at 01:00
Permutations without recursion is just kinda annoying to do, I managed it in Haskell easy enough, it's just weirding me out that I'm finding it harder to achieve in C# than in bloody Haskell – Awia May 04 '15 at 01:02
Have a look at this post: http://stackoverflow.com/questions/11208446/generating-permutations-of-a-set-most-efficiently – garryp May 04 '15 at 01:05

score 0 · Accepted Answer · answered May 04 '15 at 01:05

Turns out I'm an idiot and I added the extra swap after the recursion by accident. Real code should read:

public static void PermuteAndSolve(List<City> cities, int recursionLevel, int Length)
    {
        if (recursionLevel == Length)
        {
            foreach (City city in cities)
            {
                Console.Write(city.name);
            }
            Console.WriteLine("");
        }
        else
        {
            for (int i = recursionLevel; i <= Length; i++)
            {
                swap(cities, recursionLevel, Length);
                PermuteAndSolve(cities, recursionLevel + 1, Length);                    
            }
        }
    }

List reset on every recursion when attempting to permute

2 Answers2