I'm not as into this as Tye seems to be, but I'm wondering if Memoize might not make your life easier. If there's some natural way you're thinking about the problem, but you're worried about repeated resulting permutations, maybe you could use the natural way of permuting and let Memoize prevent you from taking the performance hit.

It's just a brainstorm; you know your context better, so you'd have to decide for yourself