Devil's Sunrise Wrote:Then swap and move as you suggested. However, when do you prove it's not possible to set the list?
I'm not quite sure...
If you test up to half the elements in 1 set, switched with from 1 to all the elements in the other, you cover everything. But I'd guess that's more than you need to actually check.
I'm just not sure where that can be decreased, or how to get to it most efficiently.
I mean if you're (for example) only 3 away from equal piles, you'd need a trade that adjusts the difference to become lower.
So if one set to trade is {23, 3}=26 and the other is {7, 13}=20 and you want the first set to be 3 smaller than the second, you would only have a limited range to hit (27-31), thus adding (7 to 11) into the 2nd set, and then you'd try a new set. So if the remaining items in set B don't have any < 12, you could step back (ie. remove 13 from the set) and try {7, 16} from the 2nd set, or whatever is next.
If you have the items in set B in a specific order (eg. 7, 13, 16, 28) then you only have to test combos involving items further along. So from {7} you would add 13, 16, or 18. Then from {13} you can add 16 or 18. etc. Looking for a minimum value is easier if they're in increasing order (since you only have to check the next element, if B(i+1) > 12 then B(i+2),...B(n) are all > 12