bugGNU Octave - Bugs: bug #50426, perms() sort order different than...

 
 

bug #50426: perms() sort order different than Matlab

Submitter:  Armin Müller <arm_in>
Submitted:  Wed 01 Mar 2017 10:28:26 AM UTC
   
 
Category:  Octave Function Severity:  2 - Minor
Priority:  3 - Low Item Group:  Matlab Compatibility
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * dev Operating System:  * Any
Fixed Release:  9.1.0 Planned Release:  9.1.0
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Wed 18 Oct 2023 08:10:06 PM UTC, comment #28: 

capping off this discussion to note that with matlab 2023b they added an explicit statement to their docs that the reverse lexicographical ordering based on position and ignoring element value, with the example:


P = perms(v) returns the same output as:

P = [v(3) v(2) v(1);
     v(3) v(1) v(2);
     v(2) v(3) v(1);
     v(2) v(1) v(3);
     v(1) v(3) v(2);
     v(1) v(2) v(3)]


Nicholas Jankowski <nrjank>
Group Member
Wed 12 Apr 2023 08:48:55 PM UTC, comment #27: 

yes, they all look good, and no other complaints in a couple weeks. closing report as fixed.

Nicholas Jankowski <nrjank>
Group Member
Wed 12 Apr 2023 08:44:50 PM UTC, comment #26: 

Is this bug report OK to close?  Seems like there was just a bit of a mixup with the tests for patched/unpatched versions but that has now been resolved.

Rik <rik5>
Group administrator
Sat 01 Apr 2023 02:15:03 AM UTC, comment #25: 

you are absolutely correct. I'm not sure why I pulled the changes but was still looking at the tests for the unpatched version.  all the tests look good in this version.

Nicholas Jankowski <nrjank>
Group Member
Sat 01 Apr 2023 12:19:52 AM UTC, comment #24: 

With the patched version, the results are exactly what you listed:

octave:4> perms(1:5)(end-10:end,:)
ans =
   1   3   5   2   4
   1   3   4   5   2
   1   3   4   2   5
   1   3   2   5   4
   1   3   2   4   5
   1   2   5   4   3
   1   2   5   3   4
   1   2   4   5   3
   1   2   4   3   5
   1   2   3   5   4
   1   2   3   4   5

octave:5> perms([2 5 4 1 3])(end-10:end,:)
ans =
   2   4   3   5   1
   2   4   1   3   5
   2   4   1   5   3
   2   4   5   3   1
   2   4   5   1   3
   2   5   3   1   4
   2   5   3   4   1
   2   5   1   3   4
   2   5   1   4   3
   2   5   4   3   1
   2   5   4   1   3

octave:6> perms ([pi e])
ans =
   2.7183   3.1416
   3.1416   2.7183

octave:7> ver
----------------------------------------------------------------------
GNU Octave Version: 9.0.0 (hg id: 423996c799a6)


Arun Giridhar <arungiridhar>
Group Member
Fri 31 Mar 2023 08:06:18 PM UTC, comment #23: 

still recompiling to test, but looking through the BISTs for the new perms, some don't seem to be matching the compatible ordering.

lexicographical ordering basically results in the sorted number increasing at each step. so the reverse of that has the lowest number at the bottom, highest at the top.

e.g.,


>> perms([1 2])
ans =

     2     1
     1     2

>> perms([1 2 3])
ans =

     3     2     1
     3     1     2
     2     3     1
     2     1     3
     1     3     2
     1     2     3


the new behavior means that pattern should be matched based on input order, not input values. e.g.:

%!assert (perms ([pi, e]), [pi, e; e, pi])

should be changed to:

%!assert (perms ([pi, e]), [e, pi; pi, e])

similarly, the point of the reopened report is that

perms(1:5) and perms ([2 5 4 1 3]) shouldn't give the same result, so %!assert (perms (1:5), perms ([2 5 4 1 3]'))

should no longer pass. what they should produce:


>> a = perms(1:5);
>> a(end-10:end,:)

ans =

     1     3     5     2     4
     1     3     4     5     2
     1     3     4     2     5
     1     3     2     5     4
     1     3     2     4     5
     1     2     5     4     3
     1     2     5     3     4
     1     2     4     5     3
     1     2     4     3     5
     1     2     3     5     4
     1     2     3     4     5

>> a = perms([2 5 4 1 3]);
>> a(end-10:end,:)

ans =

     2     4     3     5     1
     2     4     1     3     5
     2     4     1     5     3
     2     4     5     3     1
     2     4     5     1     3
     2     5     3     1     4
     2     5     3     4     1
     2     5     1     3     4
     2     5     1     4     3
     2     5     4     3     1
     2     5     4     1     3


Nicholas Jankowski <nrjank>
Group Member
Fri 31 Mar 2023 06:41:55 PM UTC, comment #22: 

Pushed this change to perms.cc on default: https://hg.savannah.gnu.org/hgweb/octave/rev/1dba35103327 based on Hendrik's comment here: https://savannah.gnu.org/bugs/index.php?63962#comment18

Marking as ready for test.

I have not touched perms.m on stable since that file will be removed at the end of Octave 8 anyway.

Arun Giridhar <arungiridhar>
Group Member
Fri 31 Mar 2023 03:01:03 AM UTC, comment #21: 

confirmed via a Mathworks bug report that the current matlab behavior is as expected and they will look into clarifying the documentation to be more explicit about the sorting.

so for compatibility it appears that octave should mimic the comment #17 output.

as mentioned in comment #20, this should now be a rather straightforward fix. recommend we make a patch for that change and include some ordering BISTs.

reopening this report pending that change, and cc'ing the relevant people from bug #63962.

Nicholas Jankowski <nrjank>
Group Member
Tue 28 Mar 2023 07:50:00 AM UTC, comment #20: 

I think perms in octave always sorts numerical values but excludes logicals where the result mirrors MATLAB using the reverse order of the input.

The c++ implementation of https://savannah.gnu.org/bugs/?63962 supports both ways (value based reversed ordering via previous sort and matlab position based reversed ordering for logicals) by a flag.

So moving to MATLAB position based ordering for everything will be very easy with bug 63692 migrated by setting the bool to default value false in the c++ template.

Anonymous
Tue 28 Mar 2023 12:30:41 AM UTC, comment #19: 

only if the unsorted matched the matlab output. i haven't checked to see whether or not that is the case.

Nicholas Jankowski <nrjank>
Group Member
Mon 27 Mar 2023 09:59:35 PM UTC, comment #18: 

Isn't this just a question of dropping the line that sorts the input vector?

Michael Leitner <mleitner>
Mon 27 Mar 2023 04:39:22 PM UTC, comment #17: 

A recent discussion over on bug #63962 about perms sort ordering indicated that the fix implemented by this report isn't actually matlab compatible.

as laid out in comment #11, after initial sorting issues, matlab's perms is 'now sorting as expected' and as documented.  However, it appears that when Matlab says "sorts in reverse lexicographic order" they are referring to the position order not the element value ordering.  (or lexicographical set ordering).  hence in matlab 2022b:


>> perms([1 2 3])
ans =
     3     2     1
     3     1     2
     2     3     1
     2     1     3
     1     3     2
     1     2     3

>> perms([2 1 3])
ans =
     3     1     2
     3     2     1
     1     3     2
     1     2     3
     2     3     1
     2     1     3


while in octave 8.1.0:


>> perms([1 2 3])
ans =

   3   2   1
   3   1   2
   2   3   1
   2   1   3
   1   3   2
   1   2   3

>> perms([2 1 3])
ans =

   3   2   1
   3   1   2
   2   3   1
   2   1   3
   1   3   2
   1   2   3


Since this is the matlab behavior after they fixed the original ordering bug 7-8 years ago, and i don't see any other outstanding bugs for perms, I assume they consider this the 'correct' ordering behavior.  The matlab ordering is consistent with lexicographical set ordering if you just consider any input is actually just 1:N.  Of course their help currently gives minimal explanation and their examples all have sorted inputs. 

worth reopening and revisiting an efficient way of getting compatible ordering?

Nicholas Jankowski <nrjank>
Group Member
Tue 07 Mar 2017 12:14:56 AM UTC, comment #16: 

I pushed the change to the development branch here (http://hg.savannah.gnu.org/hgweb/octave/rev/b7da08507fae).  I added an input validation test on the input vector v to make sure it is numeric, logical, or char.  I also added some more BIST tests.  The example in the documentation was now in the wrong sort order so I updated that as well.

Marking as fixed and closing report.  Thanks Michael.

Rik <rik5>
Group administrator
Mon 06 Mar 2017 08:47:47 AM UTC, comment #15: 

Then let's say in the second paragraph of the documentation

Results are returned in inverse lexicographic order. Possible repetitions of entries are neglected, that is, the result has always size @code{factorial (@var{n}) * @var{n}}, where @var{n} is the length of @var{v}. For generating only differing permutations use @code{unique (perms (@var{v}), "rows")(end:-1:1,:)}.

Of course, this is now again a point where it would be more efficient to do this natively in the algorithm as opposed to afterwards. This non-matlab behaviour could be invoked by an additional argument to perms, but I think we wait until somebody really wants this, right?

Anonymous
Mon 06 Mar 2017 07:53:19 AM UTC, comment #14: 

Matlab gives all the 4! permutations of [true,false,true,false].

Marco Caliari <caliari>
Group Member
Sun 05 Mar 2017 11:33:07 PM UTC, comment #13: 

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)

Anonymous
Fri 03 Mar 2017 04:19:02 PM UTC, comment #12: 

Only thing left is to clean up the script to follow Octave core coding conventions and then we can commit it to the dev branch.

Rik <rik5>
Group administrator
Fri 03 Mar 2017 10:29:14 AM UTC, comment #11: 

Thank you everybody for your support!

It's amazing. The function is getting faster, is consuming less working memory, and becoming more compatible. Any wish still left open? ;-)

I have been browsing through the time lapse of the documentation of perms() archived at the "waybackmachine".

Octave bug 30114 is dating back to 2010-06.

There has been no sorting order defined until 2012-12 (=R2012b):
https://web.archive.org/web/20121219081641/http://www.mathworks.com/help/matlab/ref/perms.html

The first occurrence is 2013-03 (=R2013a):
https://web.archive.org/web/20130318033107/http://www.mathworks.com/help/matlab/ref/perms.html

However, according to Mathworks bug 1265636, it has not been working reliably in all cases from R2013a to R2015b.

R2016a is the first version where sorting order is defined + working as expected.

Armin Müller <arm_in>
Thu 02 Mar 2017 08:26:35 PM UTC, comment #10: 

I benchmarked the old and new perms functions.  The new function is slightly faster, about 16% improvement at N = 10.

bm_perms.m code


N = 50;

bm = zeros (N, 1);
x = zeros (3628800, 10);

for i = 1:N
  tic;
#  x = perms (1:10);
  x = perms_new (1:10);
  bm(i) = toc;
endfor


Results
perms : median = .189
perms_new : median = .157
-16.9% improvement

If I switch to using 'uint8' then the median is .187 which basically erases any savings.

So, I think this just needs to be updated to follow Octave coding conventions.

Rik <rik5>
Group administrator
Thu 02 Mar 2017 07:27:14 PM UTC, comment #9: 

Also, see the bug report #30114 which is the same issue reported 7 years ago.  As documented then, there was a reluctance to change the function because there was no stated ordering by Matlab and there was the very real possibility that Matlab would change its ordering in the future.  That is confirmed in comment #0 where the behavior changed from R2015B to R2016B.  If you must have a specific order for a set of permutations then your scripts should ensure that in some manner.

On the other hand, Octave is always happy to have faster, high-performance code.  The calculation in the existing perms.m was specifically done in uint8 to limit memory consumption.  How bad is the performance hit that you talk about?

I used an input of 1:10 to both perms.m and perms_new.m and ran both through the debugger to inspect the memory usage.

For perms.m:


B = 3,628,800 bytes
p = 36,288,800 bytes
A = 290,304,000 bytes


Essentially, 40MB worth of intermediate values.

For perms_new.m


idx = 26,127,360 bytes
perm = 2,580,480 bytes
A = 290,304,000 bytes


The new method only has 28.5MB of intermediate values so it is an improvement on the old script.

The script needs to be updated to follow Octave coding conventions, and I would like an estimate of the performance hit to use uint8 and whether there is a workaround, but otherwise this looks like a good addition to Octave.

Rik <rik5>
Group administrator
Thu 02 Mar 2017 03:23:33 PM UTC, comment #8: 

Dear Michael,

your perms_new is faster than perms on my 4.0.2


octave:24> tic,perms(1:10);,toc
Elapsed time is 0.281643 seconds.
octave:25> tic,perms_new(1:10);,toc
Elapsed time is 0.168704 seconds.


and seems to give the right ordering. Congratulations. Which algorithm did you implement? Can you adapt the syle to http://wiki.octave.org/Octave_style_guide and add proper tests?

Marco Caliari <caliari>
Group Member
Thu 02 Mar 2017 10:56:18 AM UTC, comment #7: 

See the attached reworked perms.m. In my 3.8.0 it is slightly slower than the original algorithm for large V (that is, length(V)==10), but about equally efficient for length(V)==5. In the used algorithm, the indices are permuted n times, while in the original one the values themselves are permuted. It seems that in Octave this index permutation is most efficient when done in data type double. In principle, here one would need to use only uint8, which would correspond first to much less bits being moved around, and second all casts from double to integer would become unnecessary. Perhaps in later Octave versions integer addressing will become more efficient, then this could be used here.

The new ordering should be correct, I hope.

(file #39878)

Anonymous
Thu 02 Mar 2017 10:01:41 AM UTC, comment #6: 

Can I work on this?

Utsav Mangal <mangal>
Thu 02 Mar 2017 02:31:58 AM UTC, comment #5: 

For performance, I think the internal algorithm in perm.m should just be reworked to generate the index vector in the correct order rather than using the additional sortrows operation.

Rik <rik5>
Group administrator
Thu 02 Mar 2017 12:08:09 AM UTC, comment #4: 

So this could be solved with a simple change


  A = sortrows (v(p), -(1:n));


which seems to work for me but is likely less efficient.

Or by lexicographically sorting the input vector first, which should be more efficient, and figuring out how to adjust the loop index construction logic to ensure that it produces the permutations of v in the right order.

Mike Miller <mtmiller>
Group Member
Wed 01 Mar 2017 09:01:24 PM UTC, comment #3: 

Okay, I've marked the bug as confirmed and changed it's category to "Octave Function".  I've change the severity to minor, since there are already workarounds available by using, for example, sortrows.

Rik <rik5>
Group administrator
Wed 01 Mar 2017 08:49:40 PM UTC, comment #2: 

I have to correct myself. In fact, there are two issues:

  • There should be a sort order. The documentation of Matlab says "in reverse lexicographic order".

https://de.mathworks.com/help/matlab/ref/perms.html
In that sense, Octave 4.2.0 is not compatible.

  • There is a bug report 1265636 which says that in the releases from R2013a to R2015b, the sort order ist just wrong.
Armin Müller <arm_in>
Wed 01 Mar 2017 06:35:10 PM UTC, comment #1: 

The one-line summary of the function from the documentation for perms is


Generate all permutations of V with one row per permutation


The fact that the perms documentation doesn't mention any sort of order implies to me that there is no order.  It doesn't appear to me that we need to re-iterate that, although if others are confused I suppose we could.


Rik <rik5>
Group administrator
Wed 01 Mar 2017 10:28:26 AM UTC, original submission:  

It might be worth noting in the documentation that the sort order of perms() is arbitrary. Results may change from version to version, and when switching from Octave to Matlab or Scilab. M-code that is relying on the sort order will give different results.

A defensive programming style would be to write something in the form of "sortrows(perms(xxx), [yyy])"

Example output:

Octave 4.2.0

>> perms(1:3)

ans =

   1   2   3
   2   1   3
   1   3   2
   2   3   1
   3   1   2
   3   2   1

Matlab R2015b

>> perms(1:3)

ans =
     3     2     1
     3     1     2
     2     3     1
     2     1     3
     1     2     3
     1     3     2

Matlab R2016b + R2017a Pr

>> perms(1:3)

ans =
     3     2     1
     3     1     2
     2     3     1
     2     1     3
     1     3     2
     1     2     3

Armin Müller <arm_in>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #39897:  perms_new2.m added by None (3KiB - text/x-matlab)
file #39878:  perms_new.m added by None (2KiB - text/x-objcsrc)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by arungiridhar (Posted a comment)
  • -email is unavailable- added by nrjank
  • -email is unavailable- added by nrjank
  • -email is unavailable- added by nrjank
  • -email is unavailable- added by mleitner (Posted a comment)
  • -email is unavailable- added by nrjank (Posted a comment)
  • -email is unavailable- added by caliari (Posted a comment)
  • -email is unavailable- added by mangal (Posted a comment)
  • -email is unavailable- added by mtmiller (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by arm_in (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 22 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2023-04-12 nrjank StatusReady For Test Fixed
        Open/ClosedOpen Closed
        Fixed ReleaseNone 9.1.0
    2023-03-31 arungiridhar StatusConfirmed Ready For Test
    2023-03-31 nrjank StatusFixed Confirmed
        Open/ClosedClosed Open
        Planned ReleaseNone 9.1.0
        Carbon-Copy- Added arungiridhar
        Carbon-Copy- Added jwe
        Carbon-Copy- Added koerhen
    2017-03-07 rik5 StatusIn Progress Fixed
        Open/ClosedOpen Closed
    2017-03-05 None Attached File- Added perms_new2.m, #39897
    2017-03-03 rik5 StatusConfirmed In Progress
    2017-03-02 None Attached File- Added perms_new.m, #39878
    2017-03-01 rik5 CategoryDocumentation Octave Function
        Severity3 - Normal 2 - Minor
        Priority5 - Normal 3 - Low
        StatusNone Confirmed
        Release4.2.0 dev
        Operating SystemMicrosoft Windows Any
        Summaryperms() yields arbitrary sort order perms() sort order different than Matlab

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code