search

scheinerman / Permutations.jl

Permutations class for Julia.
Other
51 stars 14 forks source link

Avoid stack overflow #18

Closed cscherrer closed 3 years ago

cscherrer commented 3 years ago

I ran into this problem:

julia> π = RandomPermutation(100)
(1,99,3,80,33,97,41,63,83,57,70,6,75,56,44,66,25,20,100,35,74,73,59,91,28,19,31,84,43,67,98,94,86,26,27,78,69,17,93,96,64,48,38,36,55,60,71,89,72,88,76,51,14,42,82)(2,90,62,53,21,46,12,58,30,50,39,34,4,40,47,13,8,65,68,5,92,18,87,49,9,95,79,61,52,16,77,7,85)(10,54)(11,29)(15)(22,24,32,45,23,37)(81)

julia> CoxeterDecomposition(π)
ERROR: StackOverflowError:
Stacktrace:
 [1] _coxeter_reduce!(terms::Vector{Int64}) (repeats 79984 times)
   @ Permutations ~/.julia/packages/Permutations/LXStU/src/Permutations.jl:374

The problem is that _coxeter_reduce! is recursive, and the recursion can be very deep for longer permutations. The algorithm mutates the terms vector in-place, so there's really no need for recursion here. To change this without needing to restructure too much, I used a @label and @goto. This can be changed into something more elegant, but I'd think addressing the stack overflow problem should be a high priority.

scheinerman commented 3 years ago

@cscherrer : Thanks for the suggestion. I'll look at this more closely when I have some time. I'm thinking that, perhaps, the Coxeter decomposition stuff should not be part of the module, but a separate file that a user can add if that function is desired. Thoughts?

cscherrer commented 3 years ago

This decomposition seems like a natural thing to be interested in for permutations. Can you help me understand the disadvantage of having it easily available?

BTW my interest in this is in the Kendall tau distance, which is the length of the terms vector in the Coxeter representation. This has connections with Kendall's tau rank correlation, which is important in statistical applications.

scheinerman commented 3 years ago

OK. Thanks. New version pulled and registered as v0.4.1.