Category Archives: Mathematics

Producing permutations, part two

Posted on by
10

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.

Continue reading →

Producing permutations, part one

Posted on by
20

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.

Continue reading →

Guid guide, part three

Posted on by
Reply

Let’s recap: a GUID is a 128 bit integer that is used as a globally unique identifier. GUIDs are not a security system; they do not guarantee uniqueness in a world where hostile parties are deliberately attempting to cause collisions; rather, they provide a cheap and easy way for mutually benign parties to generate identifiers without collisions. One mechanism for ensuring global uniqueness is to generate the GUID so that its bits describe a unique position in spacetime: a machine with a specific network card at a specific time. The downside of this mechanism is that code artifacts with GUIDs embedded in them contain easily-decoded information about the machine used to generate the GUID. This naturally raises a privacy concern.

Continue reading →

Guid guide, part two

Posted on by
5

So how is it that a GUID can be guaranteed to be unique without some sort of central authority that ensures uniqueness, a la the ISBN system?

Well, first off, notice that the number of possible GUIDs is vastly larger than the number of possible ISBNs. Because the last of the thirteen digits is a checksum, there are only 1012 possible ISBNs. That is about a hundred unique ISBNs for every person on earth. That’s almost exactly 240, so you could represent an ISBN by a 40 bit number (again, ignoring the checksum). There are 2128 possible GUIDs; that’s about 40 billion billion billion unique GUIDs for every person on earth. This alone gives us the intuition that it ought to be pretty easy to ensure that two of them never collide; there are a lot of GUIDs to choose from!

Continue reading →

Generating random non-uniform data in C#

Posted on by
10

UPDATE: I’ve posted a related article here.

When building simulations of real-world phenomena, or when generating test data for algorithms that will be consuming information from the real world, it is often highly desirable to produce pseudo-random data that conform to some non-uniform probability distribution.

But perhaps I have already lost some readers who do not remember STATS 101 all those years ago. I sure don’t. Let’s take a step back. Continue reading →

Looking inside a double

Posted on by
Reply

Occasionally when I’m debugging the compiler or responding to a user question I’ll need to quickly take apart the bits of a double-precision floating point number. Doing so is a bit of a pain, so I’ve whipped up some quick code that takes a double and tells you all the salient facts about it. I present it here, should you have any use for it yourself.[1. Note that this code was built for comfort, not speed; it is more than fast enough for my purposes so I’ve spent zero time optimizing it.]

Continue reading →

Socks, birthdays and hash collisions

Posted on by
3

Suppose you’ve got a huge mixed-up pile of white, black, green and red socks, with roughly equal numbers of each. You randomly choose two of them. What is the probability that they are a matched pair?

There are sixteen ways of choosing a pair of socks: WW, WB, WG, WR, BW, BB, … Of those sixteen pairs, four of them are matched pairs. So chances are 25% that you get a matched pair.

Suppose you choose three of them. What is the probability that amongst the socks you chose, there exists at least one matched pair?
Continue reading →