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.