bugGNU Octave - Bugs: bug #30114, perms generates different results...

 
 

bug #30114: perms generates different results to matlab

Submitter:  Qianqian Fang <fangq>
Submitted:  Fri 11 Jun 2010 03:07:54 PM UTC
   
 
Category:  Libraries Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Wont Fix Assigned to:  None
Originator Name:  Qianqian Fang Open/Closed:  * Closed
Release:  * dev Operating System:  * GNU/Linux
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Fri 11 Jun 2010 11:15:28 PM UTC, comment #8: 

If you choose to modify the perms function, please remember that it is essential that you not examine the code in the Matlab function in order to create your version.

I agree with David and Rik.  I don't see any point in trying to make the function produce identical output.  There seems to be no logic to the ordering, so it appears arbitrary.  Perhaps it will never change in Matlab.  So what?  The function doesn't guarantee any ordering.  It just produces all the permutations.  Octave's function gives you that, same as Matlab.  If you want a particular order, I recommend that you do whatever is needed to obtain the ordering you desire.  That way you are not dependent on the apparently arbitrary ordering that Matlab happens to give you.

John W. Eaton <jwe>
Group administrator
Fri 11 Jun 2010 10:19:05 PM UTC, comment #7: 

I agree with David that reverse engineering an interface that may change probably isn't worth your time, although you are welcome to do it.  The factorial function grows so quickly that perms isn't all that useful unless N is small.  As a quick test,

z = perms(1:10);
zs = zeros(size(z));
tic; zs = sortrows(zs); toc;

The time taken to sort 3.6 million rows was 2.94 seconds.  The storage required for Z is already 290 MB.  You might be able to push N a little higher, but you're going to run out of memory well before sortrows becomes a significant time sink.

Rik <rik5>
Group administrator
Fri 11 Jun 2010 10:06:57 PM UTC, comment #6: 

Neither Rik or I stated that the matlab perms order wasn't consistent between versions. However, matlab doesn't guarantee won't change and there is no logic in the current order at all. If you can reproduce the exact ordering of matlab with a code that is no slower than the existing octave code then I see no reason not to accept it into Octave. But I think you're wasting your time.

Take a good look at the results of perms(1:4) that you supplied. The ordering is clearly not lexicographical as you seem to imply.

As for the speed, neither perms or sortrows should take more than a second or so on most modern machines before you run out of memory. I suspect that what you're using this mesh for will take a much larger portion of your computation time

David Bateman <dbateman>
Group Member
Fri 11 Jun 2010 09:53:23 PM UTC, comment #5: 

On 06/11/2010 05:00 PM, Rik wrote:

> Follow-up Comment #3, bug #30114 (project octave):
>
> The documentation from Matlab
> (http://www.mathworks.com/access/helpdesk/help/techdoc/ref/perms.html) doesn't
> guarantee any order to the permutations returned.  It seems that your script
> should not be relying on any order since Matlab itself might change the order
> between versions.
>   


I tried all versions of matlab (6~7.8), and the output orders
seem to be pretty consistent and predictable. In fact,
the help page does not say the orders are arbitrary either.

> I think it makes even less sense for Octave to try and match Matlab behavior
> here since it is potentially a moving target.  Does this make sense to you?
> Can you recode your script to not depend on the order of the permutations?
>   


I used permutation functions to generate tetrahedral
meshes from a grid. Because the orders of the elements are
not fixed, the indices of the element that encloses a 3D point
can vary. I could sort the elements, but that will add more
computation. I would rather rewrite the perms function.
If no one want to work on this, I will give it a try when I
have time.

Qianqian Fang <fangq>
Fri 11 Jun 2010 09:39:14 PM UTC, comment #4: 

The page

http://www.mathworks.com/access/helpdesk/help/techdo/ref/perms.html

doesn't document that the behavior of perms has this nature and so there is no guarantee that matlab will continue to respect the ordering of the permutations... So this is hardly a bug..

Looking at what the page above says perms([2 4 6]) returns, you'll see

     6     4     2
     6     2     4
     4     6     2
     4     2     6
     2     4     6
     2     6     4

So this isn't a lexicographical sort in descending order as the last two rows are in ascending order. So as far as I can see there is no logic in the manner in which matlab sorts its rows of permutation vectors.. Reproducing matlab behavior in this case seems counter productive to me.

What I suggest you do is to run "sortrows(perm([1,2,3,4]))" in your code to ensure a consistent ordering for both matlab and octave

D.


David Bateman <dbateman>
Group Member
Fri 11 Jun 2010 09:00:12 PM UTC, comment #3: 

The documentation from Matlab (http://www.mathworks.com/access/helpdesk/help/techdoc/ref/perms.html) doesn't guarantee any order to the permutations returned.  It seems that your script should not be relying on any order since Matlab itself might change the order between versions.

I think it makes even less sense for Octave to try and match Matlab behavior here since it is potentially a moving target.  Does this make sense to you?  Can you recode your script to not depend on the order of the permutations?

Rik <rik5>
Group administrator
Fri 11 Jun 2010 04:52:44 PM UTC, comment #2: 

ok, here are the outputs:

==========================================
octave
octave:1> perms(1:4)
ans =

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

octave:2> perms([2 1 4 3])
ans =

   2   1   4   3
   1   2   4   3
   2   4   1   3
   1   4   2   3
   4   2   1   3
   4   1   2   3
   2   1   3   4
   1   2   3   4
   2   4   3   1
   1   4   3   2
   4   2   3   1
   4   1   3   2
   2   3   1   4
   1   3   2   4
   2   3   4   1
   1   3   4   2
   4   3   2   1
   4   3   1   2
   3   2   1   4
   3   1   2   4
   3   2   4   1
   3   1   4   2
   3   4   2   1
   3   4   1   2
==========================================
matlab

>> perms(1:4)


ans =

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

>> perms([2 1 4 3])


ans =

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

Qianqian Fang <fangq>
Fri 11 Jun 2010 04:19:27 PM UTC, comment #1: 

Please don't assume that we have Matlab.  Include enough information in your report that we can understand what the problem is.  Precisely what result do you see with Matlab and Octave?

John W. Eaton <jwe>
Group administrator
Fri 11 Jun 2010 03:07:54 PM UTC, original submission:  

basically, the orders of the rows are different, this had caused some inconsistent results for a script I have been working on.

to test, try perms(1:4) and perms([2 1 4 3]) in octave and matlab.

In general, the first column of matlab's output is the slowest index, moving by the order from the end of the input vector to the front. While, octave's is a bit reversed, and more random.

The algorithm in perms.m should be rewrite in order to match the output orders.

Qianqian Fang <fangq>

 

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

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by dbateman (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by fangq (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 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2010-06-11 jwe Open/ClosedOpen Closed
    2010-06-11 dbateman StatusNeed Info Wont Fix
    2010-06-11 jwe StatusNone Need Info

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code