BUG DESCRIPTION:
----------------
perms() needs major improvements: memory check, unduplicating.
A) Memory check
------------
Now that the stacksize limit has disappeared, it is trivial to freeze the whole computer even with a short vector of entries.
The only solution being to unplug switch it off by hand.
perms() must check the available memory, assess the required one, compare both, and yield an error in case of predictable overflow.
B) Management of duplicate entries
-------------------------------
When the input vector x has duplicated elements, the number of their distinct permutations is smaller than n!, with n = size(x,"*").
Yet, perms() is presently unable to avoid building duplicates.
This can often prevent computing the result, due to a unstandable memory overflow.
Examples:
1) [1 0 0 0 0 0 0 0 0 0 0 0 0 0 0] has only 15 possible distinct permutations,
while perms() will try to built 15! = 1.308D+12 rows of result!
This completely disables the function. Applying unique(,"r") AFTER perms()
is not possible, since perms() kills the session and even the computer.
2) [1 1 0 0 0 0 0 0 0 0] has only (10*9)/2 = 45 distinct permutations,
while perms() will yield 10! = 3628800 rows!
3) [0 0 1 1 2 2 3 3] has 2520 distinct permutations,
while perms will (try to) yield 8! = 40320.
So, perms()'s algorithm should be able to yield the set of unique permutations,
without duplicates, and then allow to compute sets that presently freeze the session.
This algorithm could be used when a "unique" optional flag is provided.
--> perms([1 0 0 0]) // Current implementation
ans =
0. 0. 0. 1.
0. 0. 1. 0.
0. 0. 0. 1.
0. 0. 1. 0.
0. 1. 0. 0.
0. 1. 0. 0.
0. 0. 0. 1.
0. 0. 1. 0.
0. 0. 0. 1.
0. 0. 1. 0.
0. 1. 0. 0.
0. 1. 0. 0.
0. 0. 0. 1.
0. 0. 1. 0.
0. 0. 0. 1.
0. 0. 1. 0.
0. 1. 0. 0.
0. 1. 0. 0.
1. 0. 0. 0.
1. 0. 0. 0.
1. 0. 0. 0.
1. 0. 0. 0.
1. 0. 0. 0.
1. 0. 0. 0.
--> perms([1 0 0 0], "unique") // Wished option
ans =
1. 0. 0. 0.
0. 1. 0. 0.
0. 0. 1. 0.
0. 0. 0. 1.
C) Order of permutations
---------------------
Scilab's order of rows is reversed wrt Octave's one (so Matlab one, i assume):
>> perms([1 0 0]) % Octave
ans =
1 0 0
1 0 0
0 1 0
0 0 1
0 1 0
0 0 1
--> perms([1 0 0]) // Scilab
ans =
0. 0. 1.
0. 1. 0.
0. 0. 1.
0. 1. 0.
1. 0. 0.
1. 0. 0.
This is not so disturbing, but do we leave it as is?
D) "unique" and "nocheckmem"
------------------------
In case of duplicate entries, the expected number of permutations is (very much) less than factorial(n).
There is presently no function in Scilab to compute this number. Yet this is required
to assess the required memory to store the result, and cancel the computation in case of
predictable memory overflow.
We propose by default to check against the memory every time.
If this extra computation proves to be too slow in some cases, a "nocheckmem" option
could be added later, at the user risks.
ERROR LOG:
----------
// Don't try a 12-element long vector, unless you are ready to switch off your computer by hand.
HOW TO REPRODUCE THE BUG:
-------------------------
// perm([1 0 0 0 0 0 0 0 0 0 0 0]); // 46 GB required, without unduplicating.
p = perms([1 0 0])
unique(p, "r")