9
$\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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
2
  • $\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$ Commented Jan 27, 2016 at 13:24
  • $\begingroup$ @MariusLadegårdMeyer I found that compiling my function isn't straightforward, Perhaps you may want to try it :( $\endgroup$ Commented Jan 27, 2016 at 14:38

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.