Posting this here because blogger's sucky comment system won't let me post formatted code in a comment on this post. This is an implementation of Smalltalk's become() in python. It will not work on strings, int etc. but otherwise is identical
Friday, July 31, 2009
Wednesday, July 29, 2009
I take Nicole's comment to mean she gives up, although Nicole, it turns out that your comment has a deep relation to this problem and raises a new question.
To find out on average how many items are left unmoved by a random permutation, you can consider every permutation and how many are left unmoved by each, add them all up and divide by the total number of permutations. To avoid mathsy notations I'm going to write a tiny program that calculates this total.
You can also get to this answer by drawing a grid with all the permutations across the top and all the items down the side. You put a tick in a cell in the grid if the permutation on the top leaves the item on the left unmoved. Now count the ticks. Doing it column by column is hard but doing it row by row is easy because there will be (N-1)! ticks in each row.
So the conclusion is that if you do a perfect shuffle of a deck of cards, on average 1 card will end up in the same places as before.
So where does Nicole's comment come in? I knew it was Ralph Wiggum who said it but I couldn't remember the context turns out. I found it here. It's
Lisa: Hey Ralph, want to come with me and Alison to play "Anagrams"? Alison: We take proper names and rearrange the letters to form a description of that person. Ralph: My cat's breath smells like cat food.and what we've just shown is that given a random anagram, you'd expect 1 letter on average to end up in the same place - well kind of, that's only true if there are no repeated letters. I hadn't thought of this in terms of anagrams before and that adds a nice twist in terms of repeated letters. Thanks Nicole!
So the new puzzle is - given a string written in scrabble tiles (it can have repeated letters), if you mess up the tiles and make a new string at random, how many letters do you expect to be in the same place as before?
Sunday, July 26, 2009
Saturday, July 25, 2009
In his letter to the Indo calling for a "yes" to Lisbon, Pat defends our membership of the Euro. I think there are upsides and downsides to it but for Pat even the downsides are upsides. He happily points out that
The eurozone has ensured that billions of euro have been made available to Irish banks via the operation of the European Central Bank.and that
As a member of the eurozone, Ireland has benefited from very low interest rates, notwithstanding the very difficult economic situation that faces us.
Surely he must know that these 2 things are the root cause of our massive bubble. The IMF and even Brian Lenihan have said as much. So if he knows this, then to list them as upsides of eurozone membership is basically swearing that black is white and up is down. There is of course that odd "notwithstanding the very difficult economic situation that faces us" which seems to be an attempt to cover all angles - as if to say "yes I know this is what fucked up the country but still it was great craic at the time."
Of course maybe he truly disagrees with me and thinks that the oversupply of cheap credit was an entirely positive thing and we should be thankful for it. This would certainly be compatible with FF's policy over the last decade, right up the point where the shit hit the fan.
Thursday, July 16, 2009
I guess they're fun because I figured them out! If there's anyone actually reading this, post your solutions in the comments. If I get any responses I'll post solutions and if I don't, I might not.
- On average, given a random permutation of N items, how many elements do we expect to stay put? E.g. if N=3 there are only 6 perumtations, 1 leaves all 3 in place, 3 leave 1 in place and 2 shift all of them (left or right). So that's (1*3 + 3*1) / 6 = 1.
- On average, given a random function from 1..N->1..N which may or may not be injective or surjective (that is there may be X and Y such that f(X) = F(Y) and there maybe be a Z such that f(X) != Z for any X), how many elements do we expect to stay put - f(X)=X? E.g. if N=2 there are 4 possible functions, f(X) = X, f(X) = 1, f(X) = 2 and f(X) = 3-X. These fix 2, 1, 1 and 0 elements respectively. So on average that's (2+1+1)/4 = 1 but what about larger N?