bug-apl
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Lambda recursions on the example of generating permutations

 From: Robin Haberkorn Subject: Lambda recursions on the example of generating permutations Date: Mon, 3 Apr 2023 21:12:48 +0300 User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.7.1

```Hello everybody,

```
I stumbled across an interesting little problem. I would like to generate all possible combinations of taking ⍺ things from a total of ⍵. The number of possible combinations is consequently ⍺!⍵.
```
Here's a straight-forward "brute force" solution:

Perm ← {(X/⍨⍺=+/¨X←(⊂2⍴⍨⍵)⊤¨⍳2*⍵) /¨ ⊂⍳⍵; X}

2 Perm 4
3 4  2 4  2 3  1 4  1 3  1 2
3 Perm 4
2 3 4  1 3 4  1 2 4  1 2 3

```
Unfortunately the algorithm has O(2^⍵) time and space complexity. Which is okay for what I am using it, but I was still curious of how this could be solved recursively in a lambda. I feel that simple things like this should have elegant solutions in GNU APL. Unfortunately this is the best I could come up with:
```
Perm ← {⍎∊('↑,/X,¨¨X+(⍺-1) Perm¨⍵-X' 'X')[1+⍺≤1] ⊣ X←⍳1+⍵-⍺; X}

```
At this point I was really feeling the limitations of lambdas in GNU APL. There apparently aren't enough means of control flow. At least I couldn't find a way to utilize one of APL's operators elegantly for this purpose, so I fell back to a computed ⍎, which feels really clumsy and is probably quite slow as well.
```
```
Or you write a traditional ∇ function with →... I mean you could also write your own ⍶IfElse⍹ operator, but due to the lack of lexical scoping this would be pretty useless for recursion, unless you pass in your context as ⍺ or ⍵ which is again very clumsy.
```
```
I would therefore claim that we are either lacking lexical scoping and/or built-in structured If-Else constructs. Or lambdas should simply be allowed to contain ⋄, new lines and →. Or I am missing something obvious. I am not sure. But IMHO something fundamental is missing in the language.
```
I am interested in hearing your thoughts.

Yours sincerely,
Robin

```
PS: I am not saying "I want it like in Dyalog!!!11". GNU APL is great for what it is and I am not ready to switch over to Dyalog yet. I particularly like two things about GNU APL: 1) It's FREE software. 2.) It's more conservatively designed than Dyalog.
```

```

reply via email to

 [Prev in Thread] Current Thread [Next in Thread]