 |
 |
|
|
|
|
If Bush says we hate freedom, let him tell us why we didn't attack Sweden, for example.
Top 10 reasons why Osama Bin Laden didn't attack Sweden:
10. Couldn't tell Sweden from Switzerland.
9. Attackers decided to take extended sick leave at 80% pay instead.
8. Stockholm World Trade Center is only seven stories high, and they couldn't find it.
7. Osama's illness turns out to have been Stockholm Syndrome.
6. Has been reading a lot of Little Green Footballs, thinks Sweden is a Wahhabist theocracy.
5. WMD attack did occur, but Swedes are immune to surstrˆmming bombs.
4. Because everybody knows Sweden has no army.
3. Will never forget the summer of 1982 in Afghanistan and those long warm nights with Lotta Hedman, that hot Swedish backpacker — especially how she would unravel her blond pigtails as they bathed naked in the Amu Darya while the full moon illuminated the Hindu Kush. He still wakes up in a sweat thinking of her. Sometimes he wonders what has become of her.
2. IKEA furniture easy to transport from cave to cave. Especially likes his Lagom™ brown tarpaulin backdrop and Slarvig™ collapsible desk.
1. Still holding out hope for a Nobel.
Annica Tiger has written two interesting posts (with good comment streams) on women bloggers in Sweden, asking in particular why so few are represented on Bloggforum's panelsOm du t‰nker komma till Bloggforum Stockholm 2004, glˆm inte att registrera dig. Och fˆrlÂt, men jag hinner inte ‰n om att skriva om viktiga saker p svenska. Nja, jag skulle kunna gˆra det, men du skulle inte vilja l‰sa det. Ger mig ett Âr till.. If roughly 50% of bloggers are women, why are only two out of 15 participants women? Shouldn't a representative sample of Swedish bloggers have a roughly equal number of men and women?
It should. But Bloggforum is not a representative sample of Swedish bloggers. To explain how this came about, maybe it's best to ask "Why have Bloggforum at all?" The forum (I think) shouldn't try to replicate in the flesh what blogging does best digitally — and blogging can adeptly cover a great many issues, for example the very one we're discussing now. The whole blogging medium is geared towards conversation, so why "blog unplugged" in a forum setting?
Because blogs are somewhat of a closed system in a society that is not yet fully aware of them. Because the conversation about blogging should include those who don't blog. Because many professions are poised to be affected by the rise of personal publishing, and professionals who are already blogging are the best positioned to help with the transition.
Bloggforum participants, then, reflect the rise of "pro-blogging" in Sweden. In the US, pro blogs include such notables as Gawker, Wonkette, Gothamist, Talking Points Memo, Andrew Sullivan, Instapundit, Daily Kos, Crooked Timber, The Volokh Conspiracy, Matthew Yglesias, Juan Cole and James Lileks. One thing they have in common is that they are read by non-bloggers much more widely than other blogs. The other thing they have in common is that they are predominantly authored by men.
Well, at least many genres of pro blog are. Political opinion bloggers are almost to a man, er, male, with the notable exceptions of Virginia Postrel and Ana Marie Cox on either extreme of the seriousness spectrum. (In contrast, the sexes are more balanced on US newspaper opinion pages). Blogger-professionals, like lawyers and journalists, also tend to be male (while again, the sexes are more balanced in the profession at large). Satire and personality-cult blogs, however, seem to be a female bastion (Wonkette again, Eurotrash, Maccers, Belle de Jour), while community blogs like Gothamist are pretty evenly split.
The Swedish blogosphere has now entered its pro-blogging phase, but not uniformly on all fronts. It is the political and media blogs which are leading the charge, and — as in the US — these are predominantly authored by men. It is this kind of blogging that the current Bloggforum focuses on, not because it is inherently more interesting than the more personal strain of blogging (and certainly not because it is dominated by men), but because it is, right now, more relevant to the debate about whether blogging can change the political and media landscape in Sweden. These are the questions most likely to perk the ears of mainstream media, and hence most likely to raise the profile of blogging, which leads to more readers for all.
In the meantime, I can't wait for a Stockholm city events blog, or one that dredges the gossip rags and solicits celeb sightings from readers. Or how about a Stockholm restaurant review blog, by an anonymous foodie with an appetite, an expense account and a snarky palate? A Swedish culture blog? — someone should release into the wild interns with attitude to sniff out the good from the bad from the ugly among Stockholm's gallery and concert offerings. There is already one pioneer, of course: Anna's still unique fashion/shopping blog. Whoever authors these future blogs — men or women — should be on future Bloggfora.
For what it's worth, I have a few theories as to why political and media blogs in particular are predominantly male, even while both sexes populate the field:
1) I am biased, and I don't know it, so I just think there are more men than women authoring these kinds of blogs.
2) Political blogging is by nature an aggressive, competitive sport, prone to combative stances, and men tend to like this environment more than women.
3) Media blogging is by nature all about professional self-promotion, and men are shameless.
4) Women, being mature, don't depend on ego-affirming site statistics for a sense of self-worth.
I'd love to hear why I am completely off the mark in this post. I'm not all that sure about what I've just written.
Politiskt.nu should be the center of political debate in the Swedish blogosphere. It is not. The site is all dolled up with fancy technical solutions, ready for political sparks to fly, but instead is proof that if you build it, they won't come unless you do it right. Politiskt.nu is in dire need of a makeover. I'll oblige:
1. Post! This group blog of six saw three weeks go by between its last two posts. Not surprisingly, the last comment is from Oct 7In fact, because posts published more than two weeks ago have their comments closed automatically, it was impossible to comment at all for a week on politiskt.nu, until tonight, when the first post in three weeks was published.. You have to show some enthusiasm before others will. It's just like dating — you have to like yourself before others will like you.
2. Link generously! Every post on politiskt.nu is just a wall of text, even when it refers to other articles. Blogging is not the same as publishing newspaper articles in reverse chronological order. It takes a different mindset. Your post has to mesh with the web. You should use links instinctively as shorthand for explanations, attributions, sources, proofs, references, punchlines of jokes... They are obligatory.
3. Get personal. Is there a relationship between the bloggers on Politiskt.nu? Do they comment on each other's posts? Do their posts acknowledge each other's presence? Do they even read each other? I couldn't tell. It's as if there are six unconnected blogs here. We want a show — some butting of heads, parries, retreats, comebacks, good points, nice catches, notes of grace in victory... There has to be a logic behind having these bloggers under one roof.
4. Catch the blogging bug. Were the contributors rearing to blog when they were recruited, or did blogging have to be explained to them? Were they ardent readers of and commenters on other blogs before they themselves started? Do they have their finger on the pulse of what's exciting Swedish bloggers right now? Do they get it? It has to be a grassroots effort — a group blog's stable of talent should not have to be cajoled into posting.
5. Ditch registration. If you are going to have commenting, don't turn it into a privilege. Stop forcing people to register — you'll lose 90% of your commenters. Nobody cares enough about your blog to remember yet another password. Even Movable Type's new system, which lets you register one identity valid for a slew of blogs, is not really catching on — and that's because commenters are in a buyer's market; there are plenty of blogs vying for their input, and if you put up barriers, these other blogs are but a click away. If you build dams, the critical mass will stay on the other side.
if you're concerned about spam, there are some good technical solutions out there. Ever since I added an extra question to my blog commenting form which humans find easy to answer but machines not, I get around 2 manually submitted spam comments a month — down from around 100 automated ones a dayIt now works withMT 3.11's new templates too, thanks to Strang's efforts.. It's an easy solution to implement as well, one which any content management system worth its salt should manage. Finally, if you have a blog with comments, you have to resign yourself to regular weeding — you can't legislate away abuse.
6. Focus on the essentials. Simpify your site so it becomes more amenable to the daily quick fix visit. Nobody uses the calendar to navigate blogs, so ditch itThe one thing a calendar does do spectacularly well is show a dearth of posts. And how useful is one of these on the first of the month?. Instead, give more space to your most recent comments. Don't put your blogroll in a drop-down menu. Don't put your bloggers' names in a drop-down menu — these names are your main draw, and should be visible as soon as you visit the site, without having to mouse over pictures or click on menus. RSS is good, but just put up the link — it's not your job to explain it. In fact, nothing in your horizontal menu bar is essential, on the grounds that it is better to do it than to talk about it. Give and accept trackbacks. And, pardon me, but I HATE not being able to see the URL of where I am in the browser's address bar. That is so 1998.
Of all these, tips 5 and 6 are the easiest to do. Tip number 4 is the hardest, but if you get that right, numbers 3,2 and 1 will follow effortlessly.
Pardon the tone, it was for effect. Politiskt.nu is a good enough idea to attempt salvaging.
Finally a good excuse for guilt-free metablogging during the next three weeks: Bloggforum Stockholm 2004, on November 15. More here soon, but in the meantime, suggestions are welcome.
I had a pear today at work.
Every Monday, a fruit basket arrives on our floor. The bananas always go first, followed by the grapes, apples and mandarins. By Thursday, only the pears and oranges are left. I can understand why oranges remain — their strength lies in their pressing — but pears?
Is it the complexion of their skin — always a bit mottled? Or is it their colors, an autumnal range, reminiscent of decay? Is it the shape, not round or pert but, well, pear-shaped — an adjective most often modified with "horribly" by the British? Apples look less like human anatomies past their sell-by date. Are pears apple's ugly friend?
Apples often do boast bright young colors and taut puncture-me skin, but how much of this glamor comes through articifial enhancement? Pears, on the other hand, seem never to have benefited from science's tonics. They have to rely on more subtle inducements.
When is the last time you bought pears at the supermarket? I have certainly gone a year or more without tasting one. But this morning, on an empty stomach, I trawled the bottom of that basket and bit into my first pear in a while.
Inside, the texture looks glassy, but the flesh is smooth and giving, pliant even, as if flattered by the unaccustomed attention. Pears are easy on the taste buds too, not as tart as apples, and wetter, though the juice is silky like soft water, and prone to run down the chin.
Does this make them harder to eat in polite company? Is this why they are shunned by the corporate snacking community? Do get reacquainted with a pear one of these days — they're the mature fruit.
Commenting on my earlier post on Stockholm door code sequences, a reader writes (well, OK, it's Geoff):
Can you do the same thing with the rings and the sequences and the words=numbers=objects in a list, and tell me just how long it would take for the proverbial monkey to type up a copy of Hamlet by randomly banging away at a typewriter?
Seriously.
Geoff, you're right, that monkey is indeed proverbial. Wikipedia has a very interesting article about him and the various guises in which he and his infinite siblings have been bashing away at typewriters for nearly 100 years now, ever since he was evoked by French mathematician …mile Borel to illustrate an otherwise not-too accessible law of mathematics.
I think the reason our typing monkey has entered popular consciousness to the extent he has is that he straddles two of our fascinations: Our obsessive habit as a species to seek out patterns in nature; and infinity, around which we just never manage to wrap our minds, try as we might.
The reason for the first of these two fascinations, I think, is that we humans are really just finely honed cause-and-effect detectors, hoping to use this skill to avoid harm long enough to procreate. When our detectors misfire — when we generate false positives — we notice coincidences. How we deal with coincidences depends on our ability to intuit the odds of unlikely juxtapositions occurring randomly (and they do occur). Most of us are terrible at such estimations, so we end up turning coincidences into meaningful events, letting them fuel our superstitious beliefs.
We're suddenly in the middle of a digression here, I know, but there is an interesting corollary example of this: People who buy lottery tickets of the PowerBall variety avoid choosing a sequence like 1,2,3,4,5 and 6; it just doesn't look random enough to win. In fact, if that were the only option available, I suspect many habitual players would not be willing to pay for it, even though the chance of that sequence winning is exactly the same as their preferred "random" sequence, of which "type" there are far more.
Because the number of sequences in which the average lottery player can detect a pattern is far lower than the total number of possible sequences, as a group "sequences in which I see a pattern" wins less often than "sequences in which I can't see a pattern." This much is true. The mistake comes in thinking that membership of the larger group increases a specific sequence's chances of being selected at random.
An exploration of this fallacy propels Inflexible Logic by Russell Maloney, a wonderful short story from The New Yorker circa 1940. In it, the protagonist decides to test empirically whether six chimpanzees eventually do end up writing all the works in the British Museum — with remarkable results.
And one of my favorite writers, Jorge Luis Borges, wrote The Library of BabelBoth these short stories are worth copying and pasting into a word processing document, printing out and reading, if you have a spare half hour., a short story which explores the futility of deriving meaning from patterns found in sequences if all possible sequences exist. Who else but Borges would think to use that as a plot device!?
This brings us back to the problem at hand. Although our typing monkey has had much coverage on the web, I have not found an actual calculation of the probability he would type out a copy of Hamlet in any given sitting. So, Geoff, I will oblige you:
The calculation is very simple. Take this copy of Hamlet. It contains 32,197 words made from 194,270 characters. The "alphabet" of possible characters includes both lowercase and uppercase letters, punctuation marks and spaces — let's say 64 characters in total. The chance that a monkey randomly types out Hamlet in a given sitting, then, is one in 64194,270. According to Mathematica, that equals one in 3.833 x 10350,886 — a staggeringly small chance.
Another way to conduct this experiment would be to find and then line up 194,270 monkeys and put a typewriter in front of each of them. We let all of them hit a single key each at a time, and string together the result. If we manage to train them to type one character per second, we get a potential Hamlet text every second. There have been 441,504,000,000,000,000, or 4.415 x 1017 seconds since the Big Bang, approximately, so if our monkeys had started typing soon after the birth of the universe, the probability that they'd have something for us by now is 1-(1-1/(3.833 x 10350,886))4.415 x 1017Unfortunately, even Mathematica gets an overflow error trying to calculate that. Methodology: First you calculate the probability of a copy of Hamlet not being typed at a given sitting (1-1/(3.833 x 10350,886)), then you raise that to the power of the number of sittings, in our case the number of seconds since the Big Bang, 4.415 x 1017. This gives us the probability of Hamlet not having been written after all these seconds; to find the probability that it has, just subtract that number from 1..
That's a vanishingly small chance. According to our French mathematician Borel, who actually thought a great deal about this, the class of events with probabilities of less than one in 1050 of occurring are negligible on a cosmic scale. The probability our monkeys will type Hamlet is certainly in that class. However, Borel also came up with a class of events with probabilities that are negligible on a "supercosmic" scale — probabilities of less than one in 101010, or 1010,000,000,000— something exceedingly unlikely to happen even if given an inordinate number of universes to play with. We'd definitely have a text of Hamlet before long on this scale, according to our calculations.
But Borel gave an example of an event with a negligible chance of occurring even at the supercosmic scale: the chance that a container holding a mixture of a fair number of oxygen atoms and nitrogen atoms would spontaneously have all the oxygen atoms jump to one side and the nitrogen atoms to the other side, thus organizing itself, decreasing the system's entropy and breaking the Second Law of Thermodynamics.
We can therefore state with confidence that monkeys will type Hamlet long before the Second Law of Thermodynamics breaks.
The website of the government of Sweden has a linking policy which states: "Specify the link to www.sweden.gov.se and www.regeringen.se in a neutral manner." (My italics.) It's funny, but it's also stupid. Imagine enforcing that linking policy among bloggers. Or on company websites — It would be a PR fiasco. Why can governments get away with it?Jag tycker inte om dumma îterms of useî policy. Jag tycker inte heller om l‰nkningspolicy (och Boing boing inte heller).
Regeringens nya webbplats har en L‰nkningspolicy. Det bˆrjar sÂ:
L‰nka g‰rna till www.regeringen.se och www.sweden.gov.se, men t‰nk p att:
- Ange l‰nken till www.regeringen.se och www.sweden.gov.se p ett neutralt s‰tt.
Jag tycker att det ‰r j‰ttedumt. FÂr man verkligen inte kritisera webbplatsen n‰r man gˆr en l‰nk till den? Kan du inbilla dig om bloggar anv‰nde samma l‰nkningspolicyn?
Well, they found me. The knock on the door came barely a month after having moved. I actually thought it was the landlord come to fix a light and so I bounded to the door, only to find an extremely sorry-looking man with droopy eyelids who began to inform me in resigned Swedish that maybe I was not paying for a TV license. I let him talk for a while, then feigned ignorance of Swedish and let him start again in English. He spoke rather excellent English, I must say. In fact, I suspect he was British. He reminded me of Hitler, but without the mustache or charisma.
My TV was turned off and around the corner, and so I could have lied to him, but he looked so sad and dishevelled and obviously much verbally abused and routinely lied to, and probably bullied in the playground growing up, that I just couldn't bring myself to contribute further to his evident self-loathing. In fact, I had all the body language of a liar even when I admitted that yes, I have a TV the landlord lent me, and how much would it be, oh that much a month, and if I get rid of the TV do I just call... what is your service called, Radiotj‰nst? Emboldened by my less than hostile reception, Radiotj‰nst guy even made a brave attempt at explaining his purpose in life, pointing out that they guarantee the existence of public broadcasting free of advertising and political meddling.
What annoyed me most is that since I was pretending never to have heard about Radiotj‰nst, I couldn't retort with evident knowledge that while there is nothing wrong with publicly funded broadcasting, there is everything wrong with poll tax collectors for televisionsA paradox... Here are three facts: 1) I have yet to meet a a Swede who approves of Radiotj‰nst. 2) Sweden is a democracy. 3) Radiotj‰nst continues to exist. How can these three things all exist simultaneously?.
Now that I think about it, I bet his look was a foil. Radiotj‰nst jobs are probably some of the most coveted ones around for actors, who see this as the ultimate test of their method-acting skills. Become Radiotj‰nst guy, the teacher intones to his charges as he sends them off to collect licenses. And whoever comes back with the fewest gets booted from the course. My guy is probably already back at central casting, where they are removing the make-up along with the artificial bags under his eyes. Soon, he'll be at home sipping a claret as he learns his lines for an upcoming starring role in Death of a Salesman. No wonder he spoke such good English. I really think I have seen him on TV — now wouldn't that be ironic?
Instead of doormen, Stockholm apartment buildings have a little keypad at the front door, into which you key a 4-digit code to gain access to the lobby. The code is known to residents, and is liberally shared with acquaintances, workmen, postmen, and no doubt sold to an underworld of snail-mail spammers and worseI'd love to see a database of Stockholm door codes, though, if only to gain a little humint on what are the most popular 4-digit combinations..
The keypad is unusual in that there is no enter key. Instead, it remembers the last 4 digits you have pressed, and compares those to the code which unlocks the door. In other words, if you key in the sequence 123456, you'll have tried codes 1234, 2345 and 3456. If the correct code is 2345, you'll have opened the door after keying in the first 5 digits in the above sequence.
This is different from how a bank machine keypad operates, where you need to key in four digits (and then enter) for every PIN code number you try. If you were to forget your code, you'd have to go through a maximum of 40,000 key punches (not counting the mathematically boring enter key): 10,000 combinations of 4 keys each (0000, 0001 ... 9998, 9999).
On a door-code keypad, however, it's clear that you can cycle through every combination in far fewer than 40,000 key punches: If I key in just the sequence 1234567890, for example, I have already tried 7 different 4-digit combinations with just 10 key punches. On a bank machine keypad, it would have taken me 28 key punches to try 7 different 4-digit combinations.
This is interesting information for all those of us who think it within the bounds of possibility they might one day find themselves standing somewhat stupefied in the snow outside their Stockholm apartment at 3am on a Sunday in January, with the mercury all shrivelled up, not a soul in sight and not a code in mind. Deciding beforehand on the right contingency strategy for such a situation could shave hours off the frigid poking at that dumb but durable little keypad which would then have to follow.
A rundown of the options, then:
The rest of this post concerns itself with exploring the possibility of making this third option a viable one for Stockholmers. To that end, I have been wondering: (1) What is the minimum amount of door-code keypad punches needed to try every possible combination? (2) Is it possible to run through every possible combination without being forced to repeat any combination? (3) Is there a unique such solution? (4) If not, how many solutions are there? And finally, (5) How likely am I to spontaneously generate the shortest possible sequence if I pursue the second, random strategy described above?
If the answer to (2) is yes, it's easy to see that the answer to (1) is 10,003. That's because after three punches, every subsequent key I press adds a new 4-digit combination to the sequence, and there are 10,000 combinations to go through. In this best-case scenario, at 2 presses per second, we'd go through every combination in under 84 minutes.
As I started looking into this, it felt like the answer to (2) should be yes, but I lacked the mathematical tools to back up my hunch. So I decided to try to simplify the problem and then apply brute force. Instead of looking for the shortest sequence that contains all possible 4-digit combinations without repetitions, I decided to try to find one that contains all 2-digit combinations without repetitions — the shortest sequence that would unlock a door-code keypad with a 2-digit code.
I printed out a 10x10 grid with all 100 combinations (00, 01 ... 98, 99) and headed for a café in Kungsholmen. After a café latte's worth of trying to connect the numbers, I'd found a sequence 101 digits long that contained all the combinations exactly once — showing that (2) is true, at least for 2 digits:
00112131415161718191022324252627282920334353637383930445464748494055657585950667686960778797088980990
I can't help it, but I happen to feel that that's a pretty cool sequence — it feels so dense, so efficient. Just from inspection, some other things become clear:
...0011213141516171819102232425262728292033435363738393044546474849405565758595066768696077879708898099...
It felt like these observations should apply by extension to shortest sequences for combinations of any length, but I still could not demonstrate to my satisfaction that the shortest circular sequence containing all combinations of x digits had to be of length 10x — in the case of our door-code keypad problem, a loop of 10,000 digits. Also, I was nowhere near being able to count the number of such shortest sequences.
I thought I'd simplify the problem further, then — by reducing the base from 10 to 2. We can do that, because we've really just been using digits as stand-ins for distinct objects, and combinations as ordered collections of these objects. For that matter, you could think of our 4-digit codes as being equivalent to 4-letter words, made from an alphabet comprised of 10 letters. In base 2, there are only two letters, if you will: I and O.
In base 2, then, what do the shortest circular sequences containing all 2-letter words"codes" / "combinations" / "words" / "cyphers" / "strings" / "stretches" / "ordered collections"... — it's all the exact same thing. look like?
...0011...
That's it, actually (1001, 1100 and 0110 are all shifted versions of the same circular sequence)For completeness's sake, the shortest circular sequence containing all 1-letter words in base 2 is ...01..., and it's unique, obviously.. Notice that the length is 4, or 22. How about the shortest sequences containing all eight 3-letter words, in base 2?
...00010111... = ...00011101...
There are two, though they are each other's mirror image; proceeding clockwise on the first is equivalent to proceeding counterclockwise on the second. Length: 23 = 8.
Shortest sequences containing all 16 4-letter words, base 2?
...0000100110101111... = ...0000111101011001... ...0000100111101011... = ...0000110101111001... ...0000101001101111... = ...0000111101100101... ...0000101001111011... = ...0000110111100101... ...0000101100111101... = ...0000101111001101... ...0000101101001111... = ...0000111100101101... ...0000101111010011... = ...0000110010111101... ...0000110100101111... = ...0000111101001011...
That's 16 sequences of 16 letters each, including mirror images.
To find these sequences, I had to resort to drawing crude graphs, with all the possible words connected by arrows indicating which word could lead to which as we create a sequence (think "continue punching away at the keypad"). For example, both 1010 and 0010 can be followed by 0100 or 0101, in the exact same way that on the door-code keypad, the codes 1001, 2001, ... 9001 and 0001 can be followed by 0011, 0012, ... 0019 or 0010, depending on which key you choose to punch next.
The trick is to visit each word only once by following the arrows. Here, for example, is a graph with all possible 2-letter words in base 2 as nodes:
![dBG[2,2].gif](http://www.stefangeens.com/dBG[2,2].gif)
This is a much prettier version, made later, after I got some help online. Notice how there is only one way of cycling through all the nodes once.
Here is a graph with all possible 3-letter words in base 2 as nodes, again made much prettier after the fact:
![dBG[2,3].gif](http://www.stefangeens.com/dBG[2,3].gif)
In all these graphs, I've also labelled the arrows, because they represent a unique relationship between two words. For example, the arrow from node 011 to 110 is labelled 0110, because that is the 4-letter word created when these 3-letter words follow one another in our sequence.
This hints at a very profound relationship between these graphs: Every arrow on the smaller graph corresponds to a node on the larger graph. Therefore, trying to find a path that cycles through every arrow on the smaller graph is the same as finding a path that cycles through every node on the larger graph. And visually, at least, it is a lot easier to find all the ways to cycle through every arrow on the smaller graph than it is to find all the ways to cycle through every node on the larger graph. Hence I never needed to draw a graph with all 4-letter words as nodes in order to find the 16 shortest circular sequences containing all 4-letter words listed earlier — instead, I just found all the ways to cycle through all the arrows on the larger graph above.
This is as far as I got on my own. It began to feel like I was trying to reinvent the wheel, badly, so I decided to seek professional help. After rummaging about on Mathworld for a while, I hit paydirt: It turns out a loop sequence of letters or digits is called a necklace. The shortest possible such sequence containing all possible words of a certain length is called a de Bruijn sequence. The graph associated with a de Bruijn sequence is called a de Bruijn graph. The path along such a graph that uses every arrow (edge) exactly once is called a Eulerian circuit (and all graphs that allow such a circuit are called Eulerian graphs, making de Bruijn graphs a subset of Eulerian graphs). The path that uses every node (vertex) exactly once is called a Hamiltonian circuit (and you can guess what a Hamiltonian graph is).
It turns out that Leonard Euler provided us with the crucial link that shows why the answer to question (2), "Is it possible to run through every possible combination without being forced to repeat any combination?" is always yes, regardless of alphabet or word size. According to the Mathworld page on Eulerian graphs,
"Euler showed (without proofI don't know if someone has supplied a proof of this, in the meantime. Something to look up.) that a connected graph is Eulerian if and only if it has no graph vertices of odd degree. [...] A directed graph is Eulerian if and only if every graph vertex has equal indegree and outdegree."
In other words, if on a graph connected by arrows every node has as many arrows coming in as arrows going out, you will always be able to make at least one Eulerian circuit — you will always be able to find a way to cycle through all the arrows without ever getting stuck at a node. This makes sense, intuitively: Take the larger graph above, the de Bruijn graph for base 2, order 3 (which means the nodes represent 3-letter words): every node has an equal number of arrows going out, because the alphabet (base) from which to choose the next letter as you proceed along your circuit is the same at every node. The same goes for arrows coming in, which represent the letter being dropped as we progress along our circuit — it too has to be a member of the same alphabet.
But what about generating a bona fide de Bruijn sequence for our door-code keypad? Well, Mathworld is linked to the math program Mathematica (the brainchild of Stephen Wolfram), and the page on de Bruijn sequences mentions that Mathematica has an algorithm for generating such sequences for any given alphabet and word length. Although Mathematica is perhaps one of the most impressive applications ever made, it also costs 25,000kr., and hence I've never managed to justify buying it. Fortunately, there is a 15-day free trial, so I hurriedly downloaded it, and got to work. Here is a trial run, a de Bruijn sequence for 3-digit combinations in base 10:
...9798787770760750740730720710980970960950940930920910108908708608508408308208889998988081009909008007006005004003002000190180170160150140130120119118117116115114113112912812712612512412312213913813713613513413313214914814714614514414314215915815715615515415315216916816716616516416316217917817717617517417317218918818718618518418318219919819719619519419319212111029028027026025024023022922822722622522422392382372362352342332492482472462452442432592582572562552542532692682672662652642632792782772762752742732892882872862852842832992982972962952942932322202103903803703603503403393383373363353349348347346345344359358357356355354369368367366365364379378377376375374389388387386385384399398397396395394343330320310490480470460450449448447446445945845745645546946846746646547947847747647548948848748648549949849749649545444043042041059058057056055955855755695685675665795785775765895885875865995985975965655505405305205106906806706696686679678677689688687699698697676660650640630620610790780779778978879...
Again, I love the density of these sequences. When it came to generating a de Bruijn sequence for 4 digits in base 10, though, Mathematica took its time — 2 hours and 45 minutes, to be exact. By then I had grown restless and had been googling "de Bruijn sequence", only to find a most surprising page among the results: A Swedish blogger! Hakan Kjellerstrand has a page up with a much faster algorithm for generating de Bruijn sequences. He even singles out the specific solution for Stockholm door-code keypads. So click on that link, print out the result and keep it handy whenever you have a door-code keypad blocking your way.
But two of the five original questions remained unanswered: First, how many such sequences are there? Hakan and Mathematica both provide one sample de Bruijn sequence, not a counting function for de Bruijn sequences for a given alphabet and word length.
It turns out the answer wasn't even known for sure until 2002, when Vladimir Rosenfeld at the University of Haifa published a proof for the general formula in a paper titled "Enumerating de Bruijn Sequences." It's not online, as far as I can tell, but he does talk about his results in another paper of his, Enumerating Kautz Sequences (original link).
According to Rosenfeld, in 1946 Dutch mathematician N.G. De Bruijn proved a formula for counting the number of shortest circular sequences containing all q-letter words using a 2-letter alphabet (base 2). Here it is:
total number = 22(q-1)-q
Indeed, for q = 3 the result is 2 and for q = 4 the result is 16, as shown earlier. This made him famous, and led to this entire class of sequences being named after him, though it doesn't seem like he proved a generalized formula for any given alphabet size (base). In 2002, Rosenfeld did just that, apparently. For an alphabet size s and word length size q, the number of circular de Bruijn sequences of length sqis! means factorial. 4! = 4x3x2x1:
(s!)s(q-1)s-q
Making s=10 and q=4 gives us 10!1000/10000, or 5.79x106555Update 2004-10-09: Well, you can't trust the internet for anything, can you? The paper by Rosenfeld misprints the formula for the number of circular de Bruijn sequences (I've corrected the main text now). The relationship between the number of circular de Bruijn sequences and the number of linear de Bruijn sequences didn't look right when I read the paper — I thought the difference between these two formulas should be a factor of s^q, because every circular de Bruijn sequence seemed to me to contain that many starting points for linear de Bruijn sequences. But hey, I didn't prove the results, and my blog doesn't have "expert anonymous reviewers," so what would I know? Today, though, I found a different formula for the number of circular de Bruijn sequences in Stephen Wolfram's New Kind of Science and this one confirms my hunch. And so far, Wolfram has never failed me. (The formula for the linear de Bruijn sequence remains the same, though.)
Update 2004-10-21:Vladimir sent me his original paper, Enumerating de Bruijn sequences [PDF] and indeed there the formula is correct. And an interesting read., sequences. If we want to tally up the more real-world situation, where you need to key in 10,003 digits into the door-code keypad, then the formula is slightly modified:
(s!)s(q-1)
which gives 10!1000 or 5.79x106559 linear de Bruijn sequences. That's our answer for question (4).
Which leaves us only question (5): "How likely am I to spontaneously generate the shortest possible sequence if I pursue the second, random strategy described above?" To answer this, all we need is to divide the total number of linear de Bruijn sequences (which we just counted) into the total number of sequences that are 10,003 digits long (which is just 1010,003). The answer: 1 in 5.79x103444 times. Given that the number of stars in the universe is about 7x1022, it's a safe bet to say that every pig will need to fly before anyone ever achieves this feat.
Postscript: De Bruijn sequences are actually useful, and crop up in several seemingly unrelated fields. They provide the mathematical underpinning for DNA manipulation tools — DNA being nothing but sequences of words composed of the letters G, A, T and C. Rosenfeld's paper, too, aimed to provide mathematical tools for understanding "minimal generating sequences" in DNA, that is, "the sequence of minimal length that produces all possible amino acids." Also, de Bruijn sequences seem to get mentioned a lot in connection with cryptography, especially by Stephen Wolfram in the footnotes to A New Kind of Science, though how or why is something I think I need to look into next.
Another week, another libertarian/classical liberal blogger joins the Swedish blogosphere. It's an unmistakable trend that both JKL Blog and Media Culpa [English] pick up on today. We now have, in no particular order, Johan Norberg [mainly in English], Johnny Munkhammar [Some English], Henrik Alexandersson, PJ Anders Linder, Dick ErixonPer Gudmundson is a part-time participant., The group blog Smorgasbord [in English] and Tobias Henriksson all blogging from an ideological pole near the Timbro Institute, a Swedish think tank in favor of free markets or else a right wing capitalist cabal, depending on your sensibilities.
Those on the left drawn to conspiracy theories might wonder whether the Ludwig von Mises Institute hasn't been issuing marching orders; but if the left has such thoughts, they have nowhere to blog it. That's because the one thing more remarkable than the advent of liberal blogging in Sweden is the near-complete absence of credible socialist/social democrat bloggers pushing back.
What these liberal blogs have in common is that they all stay focused, stay on message, and collectively guarantee that no left-wing political shenanigans go unpunished, at least in the Swedish blogosphere. And sometimes, blogging critically about Sweden's left-wing is less like shooting fish in a barrel than shooting a barrelful of fishIf I have a gripe, it's that with the exception of the last two on the above list, Sweden's liberal bloggers don't allow commenting, which is lame. It's not as if any of them are Andrew Sullivan yet. But even if they were, that's is no reason to turn comments off; look at Kos. Oh, and get RSS feeds..
Why no groundswell of left-wing or even just social democrat blogs? My hunch is that in a society where one political perspective has the hegemony, blogging acts as an assymetric weapon in the war of ideas. Blogging is essentially free, scalable, competitive yet freely associative — right up Liberalism's alley, in fact. Meanwhile, social democrats and the left are sticking to those big old media guns that got them to the top of the pile in the first place. They have yet to adapt.
But the lack of intelligent social democratic countervetting makes the Swedish blogosphere poorer for it. I have yet to read (or find a link to) a good critique of Catherine Hakim's new book and its reasons for the marked differences between men and women's salaries in Scandinavian countries (and I can think of some responses, but this is not my battle, and I'd like to read the book first); and where is the serious response to Johan Norberg's survey of Swedish libraries showing bias in the purchasing of political booksTo be honest, I don't think a credible retort is possible in the case of library bias.?
In other cases, incisive left critique would do liberal blogs some good, lest they get all flabby and incestuous. For example, Norberg today approvingly quotes a (still permalinkless) Munkhammar post listing a litany of statistics pointing out how Sweden will effectively cease to exist in 2033I'm sure he's kidding about the 2033 date, but does that mean we are supposed to take all the other data with a grain of salt?. First off, the post is completely unlinked and unsourced, leaving us fact checkers to do all the hard work; second, some of the quoted statistics are old news and have already been parsed to death elsewhere; third, the one new piece of information to me — "In 1999, Sweden was no 4 in the international investment league, in 2002 it had fallen to no 27" — is tendentiously presented. UNCTAD's week-old 2002 foreign direct investment (FDI) league tables for this notoriously volatile indicator places Sweden 23rd out of 140 nations, far ahead of the EU norm and handily outperforming that Hayekian paradise – the US, in 92nd place – if these things matter to youWhen it comes to outward investment, Sweden came 8th. Belgium is first globally in both tables, but I'm not taking credit for that..
Furthermore, statistics can prove any point. For example, did you know Sweden is actually one of the world's best places to do business? The World Bank's month-old report ìDoing Business in 2005 ñ Removing Obstacles to Growth,î ranks Sweden ninth, globally, for ease of doing business. Only two EU members make it into the top ten: Sweden and the United Kingdom. How so? Among EU members, Sweden, together with Finland, has the lowest number of required procedures to start up a business ó three. It has among the EU's lowest start-up costs, at 0.7% of per capita income (only Denmark is lower). Registering property takes one procedure and two days ó easily making it the EU's top performer. Sweden is also the cheapest place in the EU to enforce contracts, at 5.9% of the value of the debt (vs. an EU mean of 12.1%). I'll leave out the fact that payroll costs are at the EU norm, just to heighten the effect. No wonder Sweden ranks so high in terms of FDIAnd I'll spare you the stellar results Sweden had in the World Economic Forum's 2003-2004 Global Competitiveness Report.
Update 2004-10-13: Rankings for 2004-2005..
But I shouldn't be doing this work — a left-leaning patriotic Swede should, because, basically, I agree with the liberals. It's just that it takes two sides for political blogging to get truly fun.
Must. Stay. Awake. For. The. Debate. This effort is very much being helped along by Marc in Berlin who insisted I read over his article on tropical rainforests in zeppelin hangarsHere is the article. when he finished writing it, but who then instead proceeded to procrastinate over on MemeFirst. I did manage to get a gift certificate for iTunes out of it, however, and this soon led to the purchase of a maddeningly boppy song, "I'd rather dance with you" by Bergen's own Kings of Convenience.
Check out the whole video on iTunes — I am finding it hard to resist the urge to join in with the silly steps, and since the alternative is catatonic sleep, I am grateful.
But the song doesn't just work at the gut level. The lyrics wink at you as they seduce:
I'd rather dance with you than talk with you
So why don't we just move into the other room
There's space for us to shake, and hey, I like this tune
Even if I could hear what you said
I doubt my reply would be interesting for you to hear
Because I haven't read a single book all year
And the only film I saw, I didn't like it at all
...
The music's too loud and the noise from the crowd
Increases the chance of misinterpretation
So let your hips do the talking
I'll make you laugh by acting like the guy who sings
And you'll make me smile by really getting into the swing
See, because even though he's saying how he'd rather not talk, he is talking; and even though he denies being interesting, she doubts it; and though he pretends to describe, he is actually telling her what to do. Somehow, at 3am, that comes across as profound.