The Power of Yield

Generating all the permutations of a set is a little bit dry and academic but it illustrates some of the power that yield gives us.


To start here is the code which will ask for all the permutations and print them out.

///////////

        static void Main(string[] args)
        {
            foreach (List permutation in permutations(9))
            {
                string result = string.Empty;
                foreach (int number in permutation)
                {
                    result += number.ToString();
                }
                Console.WriteLine(result);                         
            }
            Console.ReadLine();
        }

///////////

If you use the refactor tools of Visual Studio it will generate the shell of the following function.
For the body, recursively call the permutations(int) function, then place the current item in all positions of resulting permutations. Of course the recursions have to stop somewhere so on the smallest set, a set of one, just return the list with one item.

///////////

        private static IEnumerable permutations(int size)
        {
            if (size == 1)
            {
                List list = new List();
                list.Add(1);
                yield return list;
            }
            else
            {
                foreach (List permutation in permutations(size - 1))
                {
                    for (int i = 0; i <> list = new List(permutation);                         list.Insert(i, size);                         yield return list;                     }                 }             }         } 

///////////

If you run this code, it generates all permutations as expected.

What is surprising is some of the performance aspects of this code.
Even though there is recursion involved here the recursion is only invoked 'n' times.
At the same time the memory being used is also a constant times 'n' squared.
And an additional kicker the number of cycles of execution is a constant (I think between 3 and 4) times 'n' factorial.
(The last is actually pretty good. If you had a really long program that hardcoded each permutation it would take 'n' factorial lines of code.)

If you study your Knuth you could probably unearth some code that performs better on one or more of these aspects. But the readability of such code is a bit obtuse and slight changes result in disasterous results where the errors are not obvious.

Compare this to how natural it was to write this code. The code reads as a description of how to generate permutations.

The performance comes from the strange nature of yield. It converts the method into a Generator instead of a Subroutine.

permalink