Duplicate-free results of permutations + constant list

Question

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.

Answer 1

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