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.