Comment made by: nathan
Thinking about #1, for anything but size-1 combinations, the behavior wouldn't be any less pure than it is now. It would also have the exact same purity as seq, vec, map or any other order-preserving function. (map inc some-set) has the same caveat for order. Since the issue of equality on order-hiding data-structures and order-preserving (revealing?) functions is a lot bigger than combinatorics functions, a suitable equality-warning really belongs with order-hiding objects themselves.
Thinking about the discussion on the mailing list, one of the reasons people use sets is to deliberately ignore order. I think the best advice would be to convert sequences back to sets before testing. (set (map inc some-set))
I think if we wouldn't leave map broken on sets, it's worth fixing here.