[Octave-bug-tracker] [bug #60364] Takes too much memory to call unique(perms(...)), so here's a new function uniqueperms

[Michael Leitner]

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

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.

    _______________________________________________________

Reply to this item at:

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

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