[Octave-bug-tracker] [bug #60364] New option "unique" for perms

[Michael Leitner]

Follow-up Comment #6, bug #60364 (project octave):

Sorry for the belated response, but please consider the attached proposal: it
is a reworking also of the non-unique part of perms, so that the two options
use the same code path. It is a bit less time-efficient than the old version
of the non-unique case (some 10% at large problems, up to somewhat like a
factor two for smaller ones), but much more efficient for the unique case (up
to a factor 20 for large problems -- on my less powerful computer, the case
reported below is 6 seconds in the trivial unique(perms(v),"rows")
implementation, 0.19 seconds in the new implementation of Arun , and 0.014
seconds in mine). I did not analyse the old code in detail, but it could be
that my implementation is more efficient in terms of memory. 

As it is, it does not pass the BISTs, but as I see it, this is only because of
the ordering of the returned permutations. I think that it should be possible
to give the reversed lexicographic ordering that is currently promised, and as
it is the same code path, the same should hold for the unique case (where
Arun's implementation makes no promises). But apart from that, it should be
correct, as far as I have tried. If you are interested, I could try to fix the
ordering.

Of course, you could leave the old non-unique case untouched and use my
implementation for the unique case, which should give the best performance
overall. But I would judge the simplification of having a common code path to
be worth the loss in performance.

(file #53258)

    _______________________________________________________

Additional Item Attachment:

File name: perms_m.m                      Size:6 KB
    <https://file.savannah.gnu.org/file/perms_m.m?file_id=53258>



    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?60364>

_______________________________________________
Message sent via Savannah
https://savannah.gnu.org/