[Octave-bug-tracker] [bug #50426] perms() sort order different than Matlab

[anonymous]

Follow-up Comment #13, bug #50426 (project octave):

Compared to my previous post, I hope to have made the function conform to the
coding conventions, I added tests (also to test for the behaviour that was the
cause of this bug report), I made a small modification to make it work with
strings, and I made it more efficient for small arguments by hardcoding the
cases for length(v)<=3.

To address the questions in this thread: Originally, I took the perms.m from
Octave 3.6.4 installed at my machine, and as it displayed the bug, I started
to work on it. So in my previous post, when I was talking about the "original
algorithm", that meant 3.6.4. In this implementation, the resulting
permutation of v with length n was computed conceptually recursively, where
the permutation of v(2:end) is taken and v(1) inserted first before the first
column, then between first and second, and so on. This is effective,
particularly if v has a small data type, but I did not quickly find a way to
make this display the desired ordering of the output. Therefore, I developed
another algorithm, where a permutation of indices is computed, and only at the
end v is expanded. Now I see that this idea of permutation of indices (but
with the old ordering) was implemented by Jordi in 2012 to make perms work
with strings. 

In testing this implementation I found out that indexing is much faster when
done with standard double matrices than with integer datatypes, which
surprised me, as this can only mean that in Octave integer datatypes are first
cast to double and then back to integer to give the memory addresses.
Therefore, I stayed with doubles. This was what provoked my comment that,
should direct integer addressing one day be implemented, one should change the
index datatype here, which would make the algorithm more efficient. However, I
now see that Arun Giridha in 2013 did change the indexing to uint8 to decrease
memory usage (but according to my testing this did incur performance loss). In
my implementation, this is not an issue, as I do the conceptually recursive
index permutation only up to n-1, and construct the final returned matrix out
of v in n steps. For large n, this is both more efficient in terms of time and
takes less memory even with double indexing. 

So the answers: compared to the current implementation, my implementation
should (I hope) be faster, as it uses double indexing, while using less memory
(with uint8-indexing the memory usage could be decrease by an insignificant
part, but with the above-mentioned hit in performance). 

One last point came to me: in the matlab documentation of perms they give the
example of [true false true false] as input vector (but they do not give the
expected result). Octave says in the documentation "generate all permutations
of V", which I would understand to be only six in this case, as "all
permutations" to me seems to imply "all different permutations". However, this
is at odds with "the result has size factorial (N)...", and with the behaviour
of my code (and it seems all octave-perms before). How does matlab do this,
and should we make the documentation more precise?

(file #39897)
    _______________________________________________________

Additional Item Attachment:

File name: perms_new2.m                   Size:3 KB


    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?50426>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/