bugGNU Octave - Bugs: bug #60364, Takes too much memory to call...

 
 

bug #60364: Takes too much memory to call unique(perms(...)), so here's a new function uniqueperms

Submitted by:  None
Submitted on:  Sat 10 Apr 2021 01:20:25 AM UTC  
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  None Assigned to:  None
Originator Name:  Originator Email:  -email is unavailable-
Open/Closed:  Open Release:  dev
Operating System:  Any

Add a New Comment (Rich Markup)
   

You are not logged in

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

 

Sat 10 Apr 2021 07:47:18 AM UTC, comment #2: 

Sorry, I made a mistake: when you expand the multiset permutation at step i, you first have to pre-allocate the new multiset permutation, set every entry to i, and then overwrite the entries at nchoosek(1:sum(n(1:i)),sum(n(1:i-1))) by the entries of the multiset permutation from the previous step.

Example: assume we want the permutations of [1 1 1 2 2 3 3 3 3], that is, n=[3 2 4]. Then at the second step we have a ten-row incoming permutation (bincoeff(n(1)+n(2),n(2))=10). After this step, each of these rows will have become bincoeff(n(1)+n(2)+n(3),n(3))=126 rows. So for each incoming row j conceptually you have to preallocate an index matrix out=3*ones(126,9), and then say

out((1:126)'+(nchoosek(1:sum(n(1:i)),sum(n(1:i-1)))-1)*126)=in(j,:)(ones(126,1),:);

And for this to be performant, you should not treat each row on its own, but all at the same time by index arithmetic, which I do not have time to work out at the moment.

Michael Leitner <mleitner>
Sat 10 Apr 2021 07:20:44 AM UTC, comment #1: 

Good idea, but, first, I doubt that the octave maintainers will be willing to introduce a new function into the main namespace. What seems more likely is if you propose to add a flag "unique" to perms(), which would then have the behaviour you propose -- at the moment, neither octave nor Matlab for that matter recognize flags to perms(), so that should be no problem. And I can even imagine that, if octave should introduce that, Matlab would follow, because: in the strict mathematical sense, a permutation is not a reordering of a specific (multi-)set, but a specific mapping of positions -- that is, it is not yet applied. Thus, an example of a permutation of order 3 would be "swap the second and third element and leave the first fixed", written as (1)(32). Only if you write perms(1:n) for a given n you really get permutations in the mathematical sense. 

What octave actually computes are multiset permutations applied to a specific multiset, but without dropping equivalent multiset permutations. I agree that offhand I do not see a situation where I would want those. What you propose are multiset permutations in the strict sense. Note that this is also what Wolfram alpha (and thus presumably Mathematica compute): if you enter Permutations[{1, 2, 2}], you get a three-, not six-element list of permutations. So I agree that your contribution is helpful.

As to the performance: I think that you can get close to the performance of perms (that means, in practical time you can generate permutations that fill memory) if you do the following: first, compute only the multiset permutations, not the application to a specific multiset. Thus, compute indices, and you have to use here only uint8 (saving memory), because you will never have more than 256 distinct elements in the multiset (because of memory). Then, do it iteratively: say that n(i) is the frequency that element i (sorted) appears in the multiset. You first compute the multiset permutations of the sub-multiset consisting only of this first element. This is of course ones(n(1),1). Then you iteratively compute the multiset permutations of the sub-multiset consisting of the first i unique elements from those consisting of the first i-1. You can do so by index arithmetics and cumsum(nchoosek(1:1+sum(n(1:i-1)),n(i)),2), which gives you the positions where you expand the input multiset permutation and put entry i. And of course you do that by a single assignment on the matrix of permutation vectors. This should need only a single for loop (over the unique entries in your input multiset), and in addition the for loop in nchoosek(). I think that this should be performant. And at the end of course you use your multiset permutation as input into the unique values of your input multiset.

Michael Leitner <mleitner>
Sat 10 Apr 2021 01:20:25 AM UTC, original submission:  

Calling

unique (perms (foo), "rows")

takes at least as much memory as N! and likely more when doing the sorting and unique operation. This is inconvenient for long vectors with many repeated elements where the small final result is prevented by the calculation of a large intermediate.

Here is a proposed function uniqueperms() to address that behavior. Feedback requested please.

Anonymous

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #51222:  uniqueperms.m added by None (3KiB - 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 mleitner (Posted a comment)
  •  

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

    Only project members can vote.

     

     

     

    Follows 1 latest change.

    Date Changed by Updated Field Previous Value => Replaced by
    2021-04-10 None Attached File- => Added uniqueperms.m, #51222

    Back to the top


    Powered by Savane 3.6