あけましておめでとう。Another year sees me using another slightly-different array lang to demonstrate a trivial solution to a trivial problem. I'm playing with Shakti for this one, which is Arthur Whitney's latest version of K—the 9th iteration to be precise. Last winter I used one of his previous efforts, Q/kdb+, to solve a real problem at work involving millions of rows. I was impressed with its performance and loved how I could use SQL syntax interchangeably with concepts borrowed from APL/J. kdb+ is an incredibly expensive piece of proprietary software whose free version demands an always-online connection, which discouraged me from exploring it further. Shakti is also not FOSS, but its free tier is a tad less restrictive. Like kdb+, it also boasts the tables that I've come to appreciate, so I figured it was worth reading the tutorial and making a hello world program of sorts: returning every permutation of a set. This solution doesn't involve a lot of number-crunching or require tables of course; I don't have any massive data on hand to play with. Sorry.
! is the enumeration operator, like ι in APL or i. in J. !n returns 0…n-1.
! 10
0 1 2 3 4 5 6 7 8 9
Things get funky when the argument to ! is itself a list. For a list x1…xn, ! generates a matrix of n rows, where each row's length is the product of x1…xn. The elements of a given row xi are !xi repeated as many times as necessary to fill the length of the row.
! 3
0 1 2
! 3 3
0 0 0 1 1 1 2 2 2
0 1 2 0 1 2 0 1 2
! 3 3 3
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2
0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2
0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2
Since !2 returns 0 1, for a set of n items, invoking ! against a list of n 2s, then transposing it (with +) will result in a matrix of truth vectors representing all permutations of the set.
+! 2 2 2
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
The heavy lifting is already done. Now it's just a matter of generating a list of 2s and applying the permutation matrix against a set.
The set xs contains three symbols.
xs:`dog`cat`magpie
Shakti has no built in repeated list generation function, but mapping the partially-applied K combinator K[x]across each value (') in an enumeration 0…n-1 will return a vector n items long full of x values.
K:{[x;y]x}
replicate:{K[x]'!y}
replicate[`hello;3]
`hello`hello`hello
The # operator counts the length of a list. So replicate[2;#x] gives the number of 2s needed for any set x.
replicate[2;#xs]
2 2 2
Enumerating and transposing returns the permutation truth matrix.
+!replicate[2;#xs]
(0 0 0;0 0 1;0 1 0;0 1 1;1 0 0;1 0 1;1 1 0;1 1 1)
Running & against a vector returns its indices with a non-zero value.
& 0 1 0 1
1 3
So it needs to be applied to every row of the matrix.
&'+!replicate[2;#xs]
(0#,0;,2;,1;1 2;,0;0 2;0 1;0 1 2)
A list of indices ys can be passed as an argument to a list xs, even if ys is multi-dimensional one. It will return the values of xs in the shape of ys.
xs[(0;0 1;0 1 2)]
(`dog;`dog`cat;`dog`cat`magpie)
So it's enough to index the set xs by the code blurb from above.
xs[&'+!replicate[2;#xs]]
(0#,`;,`magpie;,`cat;`cat`magpie;,`dog;`dog`magpie;`dog`cat;`dog`cat`magpie)
The function definition.
perms:{x[&'+!replicate[2;#x]]}
Shakti is minimal and still in development. In fact, the syntax itself may have changed by the time you're reading this. It's certainly nothing I'd write a web app in. I'd like to use it like I do J: a powerful calculator I can spin up instantly and work out my thoughts with. The built in tables extend this easel metaphor to the realm of data too. Maybe I'll actually use them in the next article I write.