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.
Last time on FAIC I described a simple recursive algorithm for generating all permutations of the first n whole numbers: if you have all the permutations of the first n-1 whole numbers, you just insert the nth whole number at each of n positions in each permutation. So if we had all the permutations of {0, 1, 2} and we wanted all the permutations of {0, 1, 2, 3}, we just start listing permutations of {0, 1, 2} with the 3 stuck in each of 4 places:
{3, 0, 1, 2},
{0, 3, 1, 2},
{0, 1, 3, 2},
{0, 1, 2, 3}, That does it for {0, 1, 2}...
{3, 0, 2, 1},
{0, 3, 2, 1},
{0, 2, 3, 1},
{0, 2, 1, 3}, That does it for {0, 2, 1}...
and continue to get the 24 permutations.
One of my more popular articles from 2010 was my post on how to produce the Cartesian product of arbitrarily many sequences of the same type. That is, we have some sequences, say {10, 20, 30} and {200, 300, 400}, and we wish to produce the sequence of all possible combinations:
{
{10, 200}, {10, 300}, {10, 400},
{20, 200}, {20, 300}, {20, 400},
{30, 200}, {30, 300}, {30, 400}
}
A related question that I did not answer was “how do you produce all possible permutations of a sequence?” That’s the question we’re going to explore for the next few episodes.
As promised last time, a fun-for-Friday rerun from the early days of FAIC. But before we get started, a quick physics refresher.
Force is the ability to change the velocity of an object by a certain amount in a given amount of time. One newton (N) of force is the ability to change the velocity of a one kilogram object by one meter per second, in one second. The earth applies a force of gravity of 9.8N on every 1kg mass near it.
Work is the application of a force to an object as it moves a certain distance. Energy is the ability to do work. One joule (J) of energy is the ability to apply a force of one newton to an object as it moves one meter. [1. Note that the force has to be applied in the direction of the motion for it to count as work; the earth’s gravitational force does no work on a sideways-moving object. This should jibe with your intuitive understanding of work; it is a lot harder to raise an object by 1 meter than it is to slide it 1 meter, where the work is done by the force overcoming friction.]
Power is the rate at which energy is consumed in time. One watt 
of power is the consumption of one joule of energy per second.
Charge is, like mass, a fundamental property of matter. The easiest way to manipulate charge is by manipulating electrons. Charge is measured in coulombs (C). Current is the movement of charge and is measured in amperes (A); one ampere is one coulomb of charge moving past a given point in one second.
Electric potential, better known as voltage, is to charge as gravity is to mass, and is measured in volts. Applying a potential of one volt to one coulomb of moving charge consumes one joule of energy. A better way to think about it though is to divide both sides of that equation by time and get that one volt times one amp is one watt.[2. volts times amps equals watts is one of the funamental equations you have to know in order to wire a house safely. If your house power is providing a potential of 120V and your light bulb is consuming 120W of power then the current on the wire supplying the bulb is 1A. Since lighting circuits typically use wires that are safe for up to 15A, this puts a limitation on how many bulbs you can have on one circuit.]
Resistance is the tendancy of an electric conductor to resist the movement of charge, and is measured in ohms (Ω). If there is a conductor where the difference in voltage between the two ends is one volt, and the resistance is one ohm, then there will be a one amp current in the conductor.
A few years back a bunch of my coworkers and I got to discussing the space program over lunch. Someone asked why it is that we continue to launch devices into orbit by strapping a big old tank full of liquid oxygen to the device and then set it on fire. Why haven’t we developed better technology using magnets or something?
As you probably know, I’ve been re-running some of my fun non-computer posts from the last decade. This Friday I’m going to rerun my post on the impracticalities of large-scale coilguns, and I thought that as a precursor to that I might talk a bit about tabletop coilguns. So, no programming language design this week.
A couple years ago my friend Morgan expressed an interest in learning about electronics so I thought that a homemade coilgun would of course be a perfect gift for a ten year old. Yes, I am that awesome avuncular figure who gets kids pocket knives and drum sets and coilguns for their birthdays. Parents, you’re welcome!
This is a great project to teach kids about circuits because it has all of the basic parts except transistors, and each part has a clear purpose. I’ve deliberately left the voltages, capacitances, resistances and inductances I chose off the circuit diagram above. Better to work them out for yourselves on the basis of what kinds of voltages sources and what capacitors you’ve got available, and what your appetite for destruction is.
Roger Ebert was — is — a hero of mine. I’ve often thought that if I could be one tenth as clear, witty, insightful and kind, I’d consider myself a good writer.
I remember getting a copy of Microsoft Cinemania in the early 1990s, casually browsing the archive of Ebert reviews and realizing that here was someone who really, really knew how to write — and from that point on I was hooked. In the decades since then I don’t think I’ve rented a movie or gone to the theater without checking to see what Ebert had to say about it first. On the few occasions when he wrote something that moved me to respond directly he always answered my emails thoughtfully and kindly. That he took the time at all out of his incredibly busy life to answer fan emails is just one small example of his generosity.
Tonight I’m going to take AV Club reviewer Zack Handlen’s advice and watch Citizen Kane again with Roger’s commentary track. It’ll be good to hear his voice.
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.
Fabulous adventures in coding 