[Top][All Lists]

[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,

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]