Knuth mixing bits
April 10, 2014 3:51 PM   Subscribe

Which page of The Art of Computer Programming is the problem mentioned here? Does that problem ("find all ways to mix 3 zeroes with 3 ones") have a name?
posted by phrontist to Science & Nature (7 answers total) 1 user marked this as a favorite
 
From a combinatorics perspective, I'd still call it "finding permutations" even though the 0s and 1s aren't distinct.

I'm guessing it's in volume 3, if only because that's the volume combinatorics people seem to look at.
posted by hoyland at 3:55 PM on April 10, 2014


Page 22 of volume 3, permutations of a multiset, would explain why there are 20 such. (6 choose 3). He says that getting them all without repetition by swapping the first with one of the others is "open". Obviously not for this given finite problem, so I assume he means in general.
posted by Obscure Reference at 4:30 PM on April 10, 2014


I didn't watch the video, but "find all ways to mix 3 zeroes with 3 ones" sounds like the question of enumerating all bit strings of length 6 with exactly three zeroes.

the answer: there are six slots and you want to choose three of them to put the zeroes in, which you can do in 6 choose 3 ways.

Counting bit strings is a nice framework for lots of combinatorial problems. My favorite proof of the identity

n choose 0 + n choose 1 + ... + n choose n = 2^n

is by counting bit strings: the LHS counts all bit strings by counting the number with k zeroes, as k goes from 0 to n, and the RHS counts all bit strings by saying you've got 2 choices for each slot and n slots (and order matters).

posted by leahwrenn at 8:34 PM on April 10, 2014


Permutations of a multiset, I'm too long out of college to follow the reasoning at the moment but 6!/(3! x 3!)
posted by epo at 1:56 AM on April 11, 2014 [1 favorite]


The logic for permutations of a multiset is as follows. Suppose we can tell our 0s apart (call them A, B, C) and our 1s apart (call them a,b,c). There are 6! ways to permute A,B,C,a,b,c. But this overcounts what we're interested in--if I have bACaBc, that's 100101, but so is bABaCc. Given a permutation, all rearrangements of A,B,C give me the same sequence of 0s and 1s, so I need to divide by the number of permutations of A,B,C, i.e. 3!. The same is true of rearrangements of a,b,c, so I need to divide by 3! again.

leahwrenn gives another explanation which also generalises to more than two types of object--pick slots for object As, then pick slots for object Bs from what's left, then pick slots for object Cs and so on. If you write out the binomial coefficients as n!/(k!(n-k)!) and simplify, you'll get the definition of the multinomial coefficient given in the wikipedia article.
posted by hoyland at 6:18 AM on April 11, 2014 [1 favorite]


Response by poster: As mentioned in the video, the problem I was asking about is an open one (or was at the time the video was shot.
posted by phrontist at 4:04 PM on April 13, 2014


Best answer: He's not terribly clear, but I think the open problem has to be "find an algorithm that enumerates all permutations of a multiset (or maybe just permutations of n 0s and n 1s) without repeating a permutation" or equivalently if you're just interested in equal numbers of 0s and 1s "enumerate all n element subsets of a 1,...,2n with repeating a subset".

If it's discussed somewhere in AOCP and it's not at the start of Volume 3, it'll be in Volume 4 (a draft version is available as PDF here). I skimmed 2B on generating permutations quickly and didn't spot it (it's most about generating permutations of 1,...,n or a subset thereof), but it might be there, especially if it's discussed in an exercise.
posted by hoyland at 4:26 PM on April 13, 2014


« Older Hardware downsides to a touchscreen?   |   Detailed third-person description of a chaotic... Newer »
This thread is closed to new comments.