1

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?

chb
  • 1,727
  • 7
  • 25
  • 47
Joe Slater
  • 115
  • 3

2 Answers2

2

There is nothing built into PARI for this. I would suggest reading How to generate all the permutations of a multiset?.

Andrew
  • 873
  • 4
  • 10
  • I suspected that was the case and will roll my own solution. A negative answer is much more useful than no answer at all! – Joe Slater Jan 07 '19 at 23:32
1

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.

Andrew
  • 873
  • 4
  • 10