Permutations in K ?

[Bob Armstrong]

I got this post :

-------- Forwarded Message --------

Subject:	[svfig] [NSF] [ACM Members] Show off your skills in Week 8 Code Golf!
Date:	Tue, 17 May 2016 14:29:39 -0700
From:	David L. Jaffe <dljaffe @ stanford.edu>
Reply-To:	David L. Jaffe <dljaffe @ stanford.edu>, Silicon Valley Forth Interest Group <sv...@zork.net>
To:	sv...@zork.net

Can you do this in Forth?

Hey everyone!

ACM is hosting our next weekly code golf challenge. Just write a solution to the problem below in Python or Javascript using the fewest number of characters, and the winner gets to take home an adorable plush penguin. Deadline for submissions is Saturday, May 21 at 11:59pm!

Problem:

Write a function that takes an input string and returns a list of all permutations of that string. The string will be at most 10 characters long.

Examples:

"abc" --> ["abc", "acb", "bac", "bca", "cab", "cba"]
 
"" --> [""]

Submit here:

http://goo.gl/forms/9EnodbZn7Pa2ccOK2

Can somebody give a succinct algorithm in K ?

This is an excellent test for 4th.CoSy but I find after many years in K.CoSy ( which I still use for all my accounting ) I have been too isolated from traditional APL , in particular , JohnScholes+Dyalog path , eg : https://dfns.dyalog.com/n_pmat.htm , much less http://www.chilton.com/~jimw/permute.html , that It's easier to pass the question on to the K.ommunity .

Dyalog's pmat looks most interesting .


[Ryan Gonzalez]

See https://github.com/kevinlawler/kona/wiki/Idioms#combinatorics .

Also, K6 actually has a built-in permutation function: prm.

--
Ryan
[ERROR]: Your autotools build scripts are 200 lines longer than your program. Something’s wrong.
http://kirbyfan64.github.io/

--
You received this message because you are subscribed to the Google Groups "Kona Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to kona-dev+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Bob Armstrong]

Thanks Ryan .
That was near instantaneous .
looks like they all require a grade .  I have posted at comp.lang.apl a question about an efficient  Algorithm for "grade" which has reached the status of being most annoying lack in 4th.CoSy . Got some useful responses . Need post it over on comp.lang.forth
 in which the actual algorithm is needed , but I doubt any of them have thought about implementing grade as opposed to simply sort .

Thanks again .

[Kevin Lawler]

> looks like they all require a grade

If you use the next-permutation method in Knuth, you get sorted
output. This is what we do in Kerf. The question then becomes do you
want to iterate from the supplied permutation or from the canonical
sorted version, and do you want to consider repeats as distinct or
not.

In Kona I considered adding an operator that produced the next
permutation (I think on '!'), and then you can get all permutations
via scan ("!\"). Combinatorial solutions like this work great on
restricted problem sizes, but in general the effort is moot. Array
languages especially are not structured to handle this, because they
attempt to store the representations in memory. You could improve on
the problem by encoding the combinatorial space as a fixed-size range,
which you then iterate over, but you are still dealing a runtime which
is too large for brute-force. Outside of some special purpose symbolic
language, programming languages are ill-equipped for such
computations.

> an efficient Algorithm for "grade"

I've spent a good bit of time producing grade algorithms from sort
algorithms. They seem to always translate with modest effort, provided
you fully understand the sort algorithm you are miming. Of course
there are cases of both kinds, where grading is faster than sorting,
and vice-versa. Speaking asymptotically, I don't think you will find a
substantial advantage in any grading algorithm, because sorts always
reduce to grades plus a linear indexing, a simple conversion, albeit
cache-unfriendly; and sorting is among the most well-trod areas in
computer science.

[Bakul Shah]

A slightly different take on this:

p:{:[1<x;,/(>:'(x,x)#1,x#0)[;0,'1+_f x-1];,!x]}
p 3
(0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0)

This can then be used as a building block:

perm:{x@p@#x}

On Thu, 19 May 2016 06:25:55 PDT Bob Armstrong <cos...@gmail.com> wrote:
>
> I got this post :
> -------- Forwarded Message --------
> Subject: [svfig] [NSF] [ACM Members] Show off your skills in Week 8 Code
> Golf!
> Date: Tue, 17 May 2016 14:29:39 -0700
> From: David L. Jaffe <dljaffe @ stanford.edu>
> Reply-To: David L. Jaffe <dljaffe @ stanford.edu>, Silicon Valley Forth
> Interest Group <sv...@zork.net>
> To: sv...@zork.net
> Can you do this in Forth?
>
> Hey everyone!
>
> ACM is hosting our next weekly code golf challenge. Just write a solution

> to the problem below in *Python* or *Javascript* using the fewest number of

> characters, and the winner gets to take home an adorable plush penguin.

> Deadline for submissions is *Saturday, May 21 at 11:59pm!*

>
> Problem:
> Write a function that takes an input string and returns a list of all
> permutations of that string. The string will be at most 10 characters long.
>
> Examples:
> "abc" --> ["abc", "acb", "bac", "bca", "cab", "cba"]
>
> "" --> [""]
>
>
> Submit here:
> http://goo.gl/forms/9EnodbZn7Pa2ccOK2
>

> Can somebody give a succinct algorithm in *K* ?
>
> This is an excellent test for *4th.CoSy <http://CoSy.com> *but I find after
> many years in *K.CoSy* <http://cosy.com/K/CoSy.htm> ( which I still use for
> all my accounting ) I have been too isolated from traditional *APL* , in

> particular , JohnScholes+Dyalog path , eg :
> https://dfns.dyalog.com/n_pmat.htm , much less
> http://www.chilton.com/~jimw/permute.html , that It's easier to pass the

> question on to the *K*.ommunity .