8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Marius Ladegård Meyer Jan 27 '16 at 13:24
  • $\begingroup$ @MariusLadegårdMeyer I found that compiling my function isn't straightforward, Perhaps you may want to try it :( $\endgroup$ – Dr. belisarius Jan 27 '16 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.