Last time on FAIC I generated a “random” permutation of a deck of cards and gave you the first five cards, and challenged you to determine what the next five cards were. David Poeschl (of the Roslyn team!) was the first to get a possible order and, with the additional hint that the sixth card was the three of hearts, Joel Rondeau found the correct solution, which is below. Both used brute-force algorithms.
Last time in this series I presented an algorithm for generating a random number, and the time before I presented an algorithm that turns such a number into a permutation, so we can put them together to make an algorithm that returns a random permutation:
static Permutation RandomPermutation(int size, Random random)
{
return Permutation.NthPermutation(size, RandomFactoradic(size, random));
}
Is this actually a correct algorithm for generating a random permutation? Give it some thought.
I’m back from a short but productive trip to beautiful San Francisco only to discover that the May-June issue of Dot Net Curry magazine in my inbox apparently has me on the cover. [1. Fortunately I did know about it ahead of time.]
It’s free, it’s online, but you have to “subscribe” to read it. Check it out!
Next time on FAIC: More on random permutations.
Photo by my colleague Bob.
Last time on FAIC I showed how you could produce the mth permutation of n elements, where m is a number between zero and n!-1 that chooses from the n! possible permutations. There’s a very interesting way to represent numbers that are always less than n! for a given n that I thought I might talk about today.
Last time on FAIC I implemented a short algorithm that produces a sequence containing every permutation of a given size, such that the sequence is a Hamiltonian tour of the vertices of the n-dimensional permutohedron. That is, the shape you get when you make each vertex have the coordinates of a permutation, and an edge connects two permutations that differ only by a swap of adjacent items.
Since we have an algorithm that produces the same order every time, we can number each ordering; it is convenient to do so starting with zero and going to n!-1. What I’d like is an algorithm which given size, the number of items in the permutation, and index, an integer between zero and size!-1, gives back the indexth permutation of length size, without having to calculate all of them.
Last time on FAIC I described an algorithm for producing every permutation of size n such that any two successive permutations differ only by swapping two adjacent items. Today let’s actually write some code to implement this algorithm.
The C# compiler has a /langversion switch that is rarely used; most people do not know what it is for, and if asked to guess, most guess wrong. So let me disabuse you of your wrong guess right away: the purpose of the langversion flag is not to decide what C# language version to use. It is not a “go into compatibility mode” switch or a “use a previous version of the compiler” switch. The only effect of the langversion switch is to put the compiler in a mode in which use of features from a version of the language higher than the given version cause the compiler to emit an error.
Let me illustrate with a hilariously contrived example:
My erstwhile Microsoft colleague and parallelism guru Stephen Toub just did what I did not do last time: he applied the same treatment I gave to the maybe monad and sequence monad to the task comonad. Check out his awesome blog article!
OK, for reals this time, that’s it for the monad series. Next time on FAIC: ever wonder what the langversion switch on the C# compiler is for? Me neither. But next time you’ll find out anyway.
Holy goodness, this series got a lot longer than I expected. I was hoping to get to some actual category theory, but let’s just talk a bit about LINQ and then wrap up. Maybe I’ll do a series on the basics of category theory in the future.
I’ve said several times that SelectMany is the bind operation on the sequence monad, but of course there are several overloads of the SelectMany extension method of IEnumerable<T>. The one that is bind is as we previously discussed: (Error checking removed for clarity.)
public static IEnumerable<R> SelectMany<A, R>(
this IEnumerable<A> items,
Func<A, IEnumerable<R>> function)
{
foreach(A outer in items)
foreach(R inner in function(outer))
yield return inner;
}
Now you might think that when you say
from outer in items from inner in function(outer) select inner
this translates directly into a call to
items.SelectMany(outer=>function(outer))
This is not what actually happens.
I had intended to spend this episode on the history of the relationship between SelectMany and the LINQ query expression syntax, but before I do that I want to briefly address a point raised in the comments of the previous episode.
We know that the key bits of the monad pattern are (1) the ability to construct a monad value that “wraps” an underlying value, and (2) the ability to apply a function from A to M<R> to a value of type M<A>. The first operation is traditionally called unit. The second operation is traditionally called bind, but is called SelectMany in LINQ.
We saw how you could build Select out of only SelectMany and a helper method that effectively just calls unit — and indeed, you can build a Select for any monad because all you need is the unit and bind; this operation is traditionally called fmap.
I also showed how you could build Where — an inefficient Where to be sure — out of SelectMany and a helper method, but reader “Medo” reasonably pointed out that there is no general monadic where because my implementation actually required three operations: unit, bind and make an empty sequence.
This criticism is entirely justified; though every monad has an analog of the sequence monad’s Select and SelectMany, not every monad has an analog of Where.
Fabulous adventures in coding 