# Duplicate-free results of permutations + constant list

Given a constant list const, e.g.

const = {-(15/2), -(13/2), -(17/2), -(15/2), -(13/2), -(11/2)}


of length n, I want to find all permutations perm of Range[n] such that

res = perm + const


is duplicate free. I can do

Pick[#, UnsameQ @@@ (# + ConstantArray[const, n!])] & [Permutations[Range[n]]]


which is pretty fast, especially when I can make const a packed array, but I need to do this inside a loop over lots of different const vectors, and I seem to typically discard close to 80% of the permutations. So I am looking for a better alternative, hopefully one where I don't need to first generate all permutations and then pick valid ones.

I had a similar problem earlier, but wasn't concerned with duplicates then, so I don't know how or if the solution can be modified to my new problem.

The following is slower than your code, but much more efficient memory-wise. For example for const10 = {3, 1, 2, 3, 1, 1, 1, 2, 3, 1}; it is 25% slower, but while your solution eats up 610MB, this one takes almost nothing. So, it depends on what is more important to you.

findN1[currList_, const_] := Module[{n = Length@const, newlists},
newlists = Append[currList, #] & /@ Complement[Range@n, currList];
Pick[newlists, Unequal @@@ (# + const[[;; Length@First@newlists]] & /@ newlists)]
]

f[const_] := Module[{n = Length@const},
Flatten[Nest[Flatten[findN1[#, const] &/@ #, 1]&, {#}, n - 1] & /@ List /@ Range@n,1]
]

f[const] == Select[Permutations[Range[6]], DuplicateFreeQ[# + const] &]
(* True *)


Ps:I'm trying to compile it and see if I can get any benefit

• Thanks for the answer! I also found yours to be slower, but I will probably need the RAM sooner rather than later as I scale the system, so +1. Jan 27, 2016 at 13:24
• @MariusLadegårdMeyer I found that compiling my function isn't straightforward, Perhaps you may want to try it :( Jan 27, 2016 at 14:38