[GAP Forum] Permutations of a multiset, and another question

[Hebert Pérez-Rosés]

Happy new year everyone !

I wonder if anyone has a GAP function to generate all permutations of a
multiset with a given specification (i.e. n_0 elements of type 0, n_1
elements of type 1, and so on).

Moreover, I have been tinkering with a function to generate a special class
of permutations of a multiset, and I have found a problem with the function
Add. When it is called inside another function, it does not do what it is
supposed to do. That has happened to me in other occasions as well. Is that
a bug?

Below is the code of the function, with the call to Add:

##########################################################
## PermutationsMultiset generates the all the perms of
## a multiset {0,...m}, with specification <n_0, n_1>
## in co-lex order, using Ruskey's algorithm.
#########################################################

 PermutationsMultiset:= function(bign, spec)

   local n0, n1, GenMult, ran, perm, l, newperm, out;

   #--------------------------------------------------------------#
   # Recursive function that computes the perms #
   #-------------------------------------------------------------#
   GenMult:= function(smalln)

     if n0 = smalln then
        # Print(perm, "\n");
        Add(out, perm);
     else

        if n0 > 0 then
           perm[smalln+1]:= 0;
           n0:= n0-1;

           GenMult(smalln-1);            # Recursive call

           n0:= n0+1;
           perm[smalln+1]:= 0;
        fi;

        if n1 > 0 then
           perm[smalln+1]:= 1;
           n1:= n1-1;

           GenMult(smalln-1);            # Recursive call

           n1:= n1+1;
           perm[smalln+1]:= 0;
        fi;

     fi;
   end;
   #--------------------------------------------#
   #     Body of main function        #
   #--------------------------------------------#

   out:= [];
   n0:= spec[1];
   n1:= spec[2];
   ran:= [1..bign+1];
   perm:= ran;
   for l in ran do
       perm[l]:=0;
   od;

   GenMult(bign);      # First call to recursive function
   return out;

 end;

=============================================

Now try PermutationsMultiset(5, [3,2]);


Best regards,

Hebert Perez-Roses
The University of Newcastle, Australia