Search code examples
combinatoricspari-gp

Iterating over distinct permutations of a vector in Pari/GP

I want to iterate over all distinct permutations of a vector. I have tried doing this by using vecextract() in combination with numtoperm() to create a vector of permutations, and vecsort(,,,8) to remove equivalent permutations.

Unfortunately, this doesn't scale well: the maximum size of a vector within my current stack size of 4GB is less than 12!, and my machine only has 16GB.

Is there a way to do this without running out of memory, maybe by generating the k-th distinct permutation directly?

Solution

  • Use forperm.

    forperm([1,1,2,3], v, print(v))

    Produces

    Vecsmall([1, 1, 2, 3])
Vecsmall([1, 1, 3, 2])
Vecsmall([1, 2, 1, 3])
Vecsmall([1, 2, 3, 1])
Vecsmall([1, 3, 1, 2])
Vecsmall([1, 3, 2, 1])
Vecsmall([2, 1, 1, 3])
Vecsmall([2, 1, 3, 1])
Vecsmall([2, 3, 1, 1])
Vecsmall([3, 1, 1, 2])
Vecsmall([3, 1, 2, 1])
Vecsmall([3, 2, 1, 1])

    Note that the input vector to forperm should be sorted for correct results.