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

 
 

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

Submitted by:  Armin Müller <arm_in>
Submitted on:  Wed 01 Mar 2017 10:28:26 AM UTC  
 
Category: Octave FunctionSeverity: 2 - Minor
Priority: 3 - LowItem Group: Matlab Compatibility
Status: FixedAssigned to: None
Originator Name: Open/Closed: Closed
Release: devOperating System: Any

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission Jump to the original submission)

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>
Project 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>
Project 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>
Project 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

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>
Project 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:

Essentially, 40MB worth of intermediate values.

For perms_new.m

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>
Project 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

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>
Project 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>
Project Administrator
Thu 02 Mar 2017 12:08:09 AM UTC, comment #4:

So this could be solved with a simple change

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>
Project Administrator
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>
Project 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

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>
Project 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 File(s):
   
   
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
  • -unavailable- added by caliari (Posted a comment)
  • -unavailable- added by mangal (Posted a comment)
  • -unavailable- added by mtmiller (Posted a comment)
  • -unavailable- added by rik5 (Posted a comment)
  • -unavailable- added by arm_in (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 12 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Tue 07 Mar 2017 12:14:56 AM UTCrik5StatusIn Progress=>Fixed
      Open/ClosedOpen=>Closed
    Sun 05 Mar 2017 11:33:07 PM UTCNoneAttached File-=>Added perms_new2.m, #39897
    Fri 03 Mar 2017 04:19:02 PM UTCrik5StatusConfirmed=>In Progress
    Thu 02 Mar 2017 10:56:18 AM UTCNoneAttached File-=>Added perms_new.m, #39878
    Wed 01 Mar 2017 09:01:24 PM UTCrik5CategoryDocumentation=>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.1-cleanup1