For a small number of machines (<= 10):

1. Assign IDs to the machines by increasing powers of 2 (machine1 =>1; machine2=>2; machine3=>4;etc)
2. Build a hash keyed by the patch-id, whose value is the sum of the machine-ids who have that patch applied. (for example -- $patchs{$patch_id} += $machine_id;)
3. Sort the hash by value, in descending order, and display in the medium of your choice.
4. The patches at the top of the list are on more machines that those lower down.
5. Sum the machine-id's you assigned in step one (S = 1 + 2 + 4 + ... +2^^n).
6. For each patch-id in the hash whose value is less than S, there is a unique combination of powers of 2 the add up to the difference. Those machines do not have this patch.
7. Apply the patches
8. Repeat this process until there are no patches left to apply. (This is to account for the case which __never__ happens in real life -- PatchA requires Patches B through F, and PatchC wasn't on your original list...)

For more than ten machines, I'd split them up into groups of less than ten each, and run each group separately. And, once I had each group sorted out and patched, I make a final run against a group created by taking one from each of my original groups.

This is not going to be a simple process; and if you have a lot of machines, it will be basically a non-starter. In that case, I throw up my hands, build me a "golden machine" with all of the patches applied and then clone its system disk to all the other machines. Come to think of it, that might be the best policy from the git-go.

Good Luck & Good Hunting