I read somewhere about the incompatible pairs problem where you have a list of things, and a list of pairs that are incompatible (ie you can't pick both from a pair). You have to pick a certain number from the list w/out violating any of the incompatible pairs. It said solving with brute force (construct all possible answer lists ignoring the pairs, then go through and test them all) takes too much computing resources to be feasible (except with very small list and pair list). If you have to pick x things from n options with p incompatible pairs, brute force would take n! / ( x! * (n-x)! ) to get our lists and then *2px for worst case (our lists are size x and we gotta check p pairs and the simplest way is to scan list to find one half the of the pair, then scan for the other half ... not efficient but whatever). anyway, the important thing is that n!. factorial is evil and owns all the other numbers.

Anyway, I can do it using 2^p lists in the worst case, which is loads better usually (big n and not-insanely-big p), but still exponential resources use. my technique reminds me of MWI ^^ ok, start with 2 copies of the list of items. now take the first incompatible pair (1, 2) for any 1 and 2, and scratch 1 off one list, and scratch 2 off the other list, so they become differentiated. next up, take another pair, and for each list we have, differentiate it into 2 and mark off 1 on one list and 2 on the other. if a list has 1 or 2 missing, you don't have to split it this step, so we're not actually gonna use the full 2^p lists. not sure how to approximate how many we really will use. anyway, after you go through all the pairs, you'll have lots of lists with various amounts of items remaining. take all the ones with enough items, and for the ones with extra, use some combinatorics to get all the possible ways to pick x things out of them if you want. another way to save resources is if a list ever gets too small just delete it and never split it again.

anyway, anyone know a better way or another cool problem?

oh, umm, an example of an incompatible pairs problem: you have an apartment complex with space for x people and you want it full, a list of n applicants, and a list of p pairs of applicants who fight and thus you can't have both.

Feels like I have't linked IMAO enough.

Andrew Sullivan writes: One reason I find some of the grand-standing over WMDs increasingly preposterous is that it comes from people who really want to avoid the obvious: more and more it's clear that the liberation of Iraq was a moral obligation under any circumstances. People say to this argument that if we depose one dictator for these kinds of abuses, where will we stop? But the truth is: very few dictators have resorted to imprisonment or mass killing of children. Saddam's evil was on a world-historical scale. Ending it was one of the most prgressive things the United States and Britain and their allies have ever done.

Not that he's wrong, per se, but there's a better answer to when we will stop removing evil dictators from power: we won't! This isn't a slippery slope to something bad, it's a slippery slope to no more evil dictators. The only thing stopping us is what we *can* do, not what we'd like to.

Reading an article on blogging I ran into the phrase, "the thrill of teaching a child to spell." That ought to be the thrill of a child learning to spell, and parents ought not try to take the credit.

The TCS Blog (new)

omfg (anti-Americanism)

I took a quiz ^^


-Perfect- You're the perfect girlfriend. Which
means you're rare or that you cheated :P You're
the kind of chick that can hang out with your
boyfriend's friends and be silly. You don't
care about presents or about going to fancy
places. Hell, just hang out. You're just happy
being around your boyfriend.


What Kind of Girlfriend Are You?
brought to you by Quizilla

To start, I think the Mercurial mark on the pic is a bit scary. The perfect gf is moody!? I'll translate loving to caring so it's fine, and wait on tomboyish.

It's also scary that the description isn't pretty normal. Many people (more than half for sure) ought to be able to hang out with their SO's (significant other's) friends, at least a fair bit, because most people have similar tastes to SO. Getting all hung up on presents, fancy places ..... can we say annoying hangups? Happy being around SO .... well that better be true!

WRT tomboyish, I have a theory that the stereotypes boys are supposed to follow are better (morally) than the ones for girls. Not all of them, and not in all spheres, but yeah...... I'm not going to defend this right now. I think I'll go look for online journals.

I wrote a comment in this thread on The World. Actually several, but I mean the one at the bottom (right now, hopefully not forever) on the fungibility of human copies.