# Permutation block (maybe in APL libary?)

I'm needing to generate all permutations of a list
e.g
permutations of (1,2,3)

should give

1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,3

I've found an algorithm to do the job but I'm wondering (before I start creating a custom block) if a simple combination of a few APL library blocks would do the job for me?

Good question; I had to look it up. No, there isn't, to my surprise.

there is Heap's algorithm, I suppose...

I've been trying to implement that for the past 24 hours - mine (which doesn't work of course) looks nothing like that

Can you share the block to save me retyping it please?

Oh, sure, here goes: https://snap.berkeley.edu/project?user=jens&project=Heaps%20Algorithm

Excellent

It has highlighted a problem though - I needed 20 permutations of [1..20] which turns out to be a VERY big number!

(This is for an Advent of Code puzzle)

So I might have to change my approach to the problem

The length of a permutation is directly proportionate to the factorial of the length of the original list. So the maximum length list you can generate a permutation for without completely crashing Snap! is about 7, sadly. (And even that takes several minutes.)

I've managed to get [1..8] to work without crashing but now I'm looking into how to make a streaming type thingy

I've got this so far

based on the python code in this

You probably need a calculator of permutations number, not all the items.
So the goal is to calculate factorials
$$V^n_r = \frac{n!}{(n-r)!}$$\$
eg. with

I actually need all the items, but only one at a time (well only if I carry on with same approach ) - I've got a list of 20 items and need to check all permutations to see if they are valid or not

I'm now more interested in producing a stream of the permutations more than actually applying it to the puzzel

So You want something like this to iterate over every permutation without storing it permanently.

Used this way it builds a list of permutations.

This way just counts them.

But it takes forever to iterate over 20 items.
For 10 items ~ 300s.

Sample project Perm4Each

[edited]
Excellent

What I'm actually after is to produce each permuation one after each other without storing the running total
e.g

I'm embarrassed to say how long it took me to debug this (days rather than hours), but here is a stream solution that gives a result instantly, but actually does the computation of each permutation as it's needed.

Note: It's important to feed the result of PERMUTATIONS directly into FOR EACH rather than say

because the latter would keep all the previously computed permutations in memory and eventually run out. The first version will in principle run to completion, although your computer will have turned to rust before it can generate 120! different permutations.

Here's the code:
permutations.xml (20.6 KB)

P.S. It has to use INTERLEAVE DELAYED, not plain INTERLEAVE. If you want an explanation of this, read SICP 3.5.4. Way too detailed for me to do here.

Creating a stream generator is instantaneous but consuming all items...

As compared to

Oh. Yeah, it's slow because the stream higher order functions aren't primitive as the ordinary list ones are. And the underlying algorithm isn't elegant -- I don't know an elegant algorithm for permutations. But I think it's really cool that you can build huge lists (even infinite lists) instantly.

I've played with all the solutions and @dardoro is the quickest

But I wanted to see if I could produce a version for muggles like me that simply supplies an upvar with each permutation

I tried modifying all your solutions but failed so I implemented an algorithm I found on the internet and came up with this

(Image corrected now)
so that it can be used in this sort of way

(project corrected now)
I used the library repeat/until block as my template

Although its more straight-forward than the other solutions - its is very slow

Simple wrapper over recursive method does not fit Your needs?

It certainly does thank you

Just to say - after 4 days of running @dardoro block on two different computers - one starting at numbers 1..20 and the other at numbers 20..1 - I gave up on the iterative approach (they both had only got as far as looking at 1,000,000 permutations out of the possible 2.4 x 10^18 ones) and looked to solving the puzzle in a different way

After a day, I've done it

But, by golly, I've learnt a lot about Snap! and permutation algorithms