Conversation started Apr 25, 2018 at 17:30.
Apr 25, 2018 5:30 PM
Welcome to APL Cultivation!
Today, we'll have a look at a very old (and famous) programming problem in the APL world.
(That is, unless someone has a better idea…)
Consider two vectors, e.g. L←'abacba' ⋄ R←'baabaac'.
By now, you should know about dyadic :
⋄ L←'abacba' ⋄ R←'baabaac' ⋄ L⍳R
@Adám

Rebuilding user command cache... done

Real time: 1.044 s
User time: 0.987 s
Sys. time: 0.048 s
CPU share: 99.11 %
Exit code: 0
⋄ L←'abacba' ⋄ R←'baabaac' ⋄ ⍞←L⍳R
@Adám

Rebuilding user command cache... done
2 1 1 2 1 1 4

Real time: 0.988 s
User time: 0.879 s
Sys. time: 0.082 s
CPU share: 97.23 %
Exit code: 0
⋄ L←'abacba' ⋄ R←'baabaac' ⋄ ⎕←L⍳R
@Adám
2 1 1 2 1 1 4
Apr 25, 2018 5:33 PM
(Sorry about that noise.)
Dyalog bot has a mind of its own, we're used to it
But that finds first location in L of each element in R.
However, what if we wanted the first b in R to "consume" the first b in L so that the second b in R would have to contend with the index of the second b in L`?
That is, we want some function which gives 2 1 3 5 6 7 4.
You could call it "iota without replacement".
I assume we need some form of recursion?
@J.Sallé Oh no, no looping!
Apr 25, 2018 5:37 PM
Let's do it the APL way.
Sounds good
Let's begin by labelling the elements so we can see what goes where:
⍞←'a1' 'b1' 'a2' 'c1' 'b2' 'a3' ⍳ 'b1' 'a1' 'a2' 'b2' 'a3' 'a4' 'c1'
@Adám 2 1 3 5 6 7 4
@Adám Okay, so we need a way to "label" the elements?
@J.Sallé Yes, exactly.
Apr 25, 2018 5:40 PM
without actually labeling them, if that makes any sense
So, because we numbered the as (which otherwise all match each other) and the bs, the right pairs get matched up.
So if you remember the lesson about , you may recall what ⍋⍋ does.
While gives use the indices that will sort, ⍋⍋ gives us the positions that each element will occupy in the sorted result.
⎕←↑ L(L⍳L)(⍋⍋L⍳L) ⊣ L←'abacba'
@Adám
a b a c b a
1 2 1 4 2 1
1 4 2 6 5 3
The first line is the data and the second is the indices of the first occurrences (i.e. all identical items will get the same index). The third line is the position that each will occupy when sorted. That means that identical elements get consecutive positions.
E.g. you can see that the first b gets 4 (because there are 3 as) and the second gets 5.
This almost solves the problem.
However, there are a couple of issues:
1. The two arrays must have the same set of elements.
2. The two arrays must have equally many of each unique element
3. The unique elements must initially occur in the same order
Why these conditions?
1. is because otherwise the purely numeric "labels" will match the wrong things.
2. is because otherwise one element's "label" will be paired up the the label of a different value element of the other array.
3. is because otherwise identical "labels" numbers refer to two entirely different things, and so the matching won't give a meaningful result.
But if these conditions are met, we get the right result:
⋄ L←'abacba' ⋄ R←'aaabcb' ⋄ ⎕←(⍋⍋L⍳L)⍳⍋⍋R⍳R
@Adám
1 3 6 2 4 5
The first a in R gets paired with the element in position 1 of L, and the second a in R goes with the element in position 3, and the third goes with the last element of L.
@all Clear so far?
Apr 25, 2018 5:56 PM
Yes
OK, let's have a stab at how we can ensure that all conditions are eliminated, and then we'll have our solution.
Since we're going to look up elements of R in L anyway, we can use indices into L (that is L⍳R) instead of the lookup of R into itself (R⍳R) This ensures that elements of R are labelled with "L's labelling system".
⋄ L←'abacba' ⋄ R←'bcabaa' ⋄ ⎕←↑L(L⍳L)(⍋⍋L⍳L) ⋄ ⎕←↑R(L⍳R)(⍋⍋L⍳R)
⋄ L←'abacba' ⋄ R←'bcabaa' ⋄ ⎕←↑L(L⍳L)(⍋⍋L⍳L) ⋄ ⎕←↑R(L⍳R)(⍋⍋L⍳R)
⎕←0 0⍴L←'abacba' ⋄ R←'bcabaa' ⋄ ⎕←↑L(L⍳L)(⍋⍋L⍳L) ⋄ ⎕←↑R(L⍳R)(⍋⍋L⍳R)
@Adám
a b a c b a
1 2 1 4 2 1
1 4 2 6 5 3
b c a b a a
2 4 1 2 1 1
4 6 1 5 2 3
@DyalogAPL I warn you!
You need to read the first three lines and the last three lines separately.
The first line (of each group) is the data, the second line is the first-positions of that data in L. The third is the progressive labelling of that.
No you can see that the first a is labelled 1 for both L and R and the first b is labelled 4 for both L and R.
⎕←0 0⍴L←'abacba' ⋄ R←'bcabaa' ⋄ ⎕←(⍋⍋L⍳L)⍳(⍋⍋L⍳R)
@Adám
2 4 1 5 3 6
And so we have that the first b of R takes out element 2 of L, and the c takes out element 4 of L and so on.
But this still requires both sides to have the same set of elements and equally many of each element.
How can we ensure that there are equally many of each unique element on each side?
Apr 25, 2018 6:10 PM
?
Nope
Well, if you think about it, L,R and R,L must necessarily have the same set in equal proportions.
⍴eshape and unique?
But of course this also gives us way more elements than we need. We'll take care of that later.
@J.Sallé Yes, reshape, but we don't want unique, since we need to preserve duplicates. But we're getting ahead of ourselves.
⎕←0 0⍴L←'abacba' ⋄ R←'bcabaa' ⋄ ⎕←(⍋⍋L⍳L,R)⍳(⍋⍋L⍳R,L)
@Adám
2 4 1 5 3 6 9 7 11 8 10 12
Notice that this sequence begins with what we want, and now we have equal proportions, so we've eliminated issue 2. We just need to reshape (or take) to chop the unneeded elements:
⎕← ((⍴L)⍴⍋⍋L⍳L,R)⍳((⍴R)⍴⍋⍋L⍳R,L) ⊣ (L R)←'abacba' 'bcdabaa'
Apr 25, 2018 6:17 PM
@Adám
2 4 7 1 5 3 6
So many parenthesis though, looks like something I'd code in apl :p
Now it works even though we have a d in R which doesn't occur in L. In accordance with the rules of , not-found elements get the index 1+the last index of the left argument. Since we chopped the left list of labels to the length of L, that's what we get.
@Adám would it be the same index number if we had multiple elements that don't occur?
⎕← ((⍴L)⍴⍋⍋L⍳L,R)⍳((⍴R)⍴⍋⍋L⍳R,L) ⊣ (L R)←'abacba' 'bcdabaaaaa'
@Adám
2 4 7 1 5 3 6 7 7 7
Apr 25, 2018 6:22 PM
Okay, I thought as much
And so, we've taken care of issue 1 (different sets of elements).
One use case might be in a first-come, first-served queue... let's say you have First Class, Premium, and Economy seats on a plane. This algorithm will use them up in order as requests are processed
Btw, this algorithm can be adapted to use with any-rank arrays by using instead of monadic and instead of dyadic and instead of , .
Let's have a look back at what we did. Consider:
⎕←↑ (L R)←'abacba' 'baabaac'
@Adám
abacba
baabaac
So we labelled the elements:
⎕←↑ ('a1' 'b8' 'a2' 'c12' 'b9' 'a3')('b8' 'a1' 'a2' 'b9' 'a3' 'a4' 'c12')
Apr 25, 2018 6:32 PM
@Adám
┌──┬──┬──┬───┬──┬──┬───┐
│a1│b8│a2│c12│b9│a3│   │
├──┼──┼──┼───┼──┼──┼───┤
│b8│a1│a2│b9 │a3│a4│c12│
└──┴──┴──┴───┴──┴──┴───┘
And looked those labels up:
⍞←('a1' 'b8' 'a2' 'c12' 'b9' 'a3') ⍳ ('b8' 'a1' 'a2' 'b9' 'a3' 'a4' 'c12')
@Adám 2 1 3 5 6 7 4
But actually, we don't need the original values (the letters); the numeric labels are enough:
⍞←(1 8 2 12 9 3) ⍳ (8 1 2 9 3 4 12)
@Adám I have to go eat now, but I have a pretty nifty solution that I think is valid. I'll be back soon
@Adám 2 1 3 5 6 7 4
Apr 25, 2018 6:34 PM
@H.PWiz No worries!
And how did we get those labels?
⎕←↑ (L R)←'abacba' 'baabaac' ⋄ ⎕←(⍴L)⍴⍋⍋L⍳L,R ⋄ ⎕←(⍴R)⍴⍋⍋L⍳R,L
@Adám
abacba
baabaac
1 8 2 12 9 3
8 1 2 9 3 4 12
So now we can define our function:
⍞←'abacba' {((⍴⍺)⍴⍋⍋⍺⍳⍺,⍵)⍳(⍴⍵)⍴⍋⍋⍺⍳⍵,⍺} 'bcabaa'
@Adám 2 4 1 5 3 6
@Adám we called it ⍳ without replacement right?
@J.Sallé Yes, or "progressive dyadic iota".
Apr 25, 2018 6:41 PM
Sounds good
Now to take Brian's example of filling a plane with multiple classes, using first-come, first-serve, we may want to ask: For each customer, will he fit on the plane?
Well that depends on how many seats are available
So, say we have a plane like '11bbbpeepee' where 1 is first class, b is business, p is economy plus (extra legroom at emergency exits), and e is regular economy.
And we have a bunch of customers coming to buy seats: '1bbbpppeeeee'. That's one 1st class customer, three business people, three want more legroom, and a load of regular people.
⍞←'11bbbpeepee'  {((⍴⍺)⍴⍋⍋⍺⍳⍺,⍵)⍳(⍴⍵)⍴⍋⍋⍺⍳⍵,⍺} '1bbbpppeeeee'
@Adám 1 3 4 5 6 9 12 7 8 10 11 12
Being that the plane only has 11 seats, we can see that one plus and one economy will not fit (indicated by the 12s), but we just want a Boolean, not the actual seating.
Apr 25, 2018 6:51 PM
We can do result ∊(⍴ (or ≢)Result)?
So think about it. progressive dyadic iota (or iota without replacement) asks "For each element, where would it go in the remaining elements?" Now we need to ask "For each element, does it fit in (i.e. is it in) the remaining elements?"
@J.Sallé Good, yes, but we don't need to first calculate the indices.
I forgot a there also
Ah, I see
you wanna do that directly from the string
"is it in" is APL's . Just note that the arguments of and are "reversed" in that the array we look up in is on the left for and on the right for , so we just swap the parts of our function and substitute for the middle :
⍞←'11bbbpeepee'  {((⍴⍵)⍴⍋⍋⍺⍳⍵,⍺)∊((⍴⍺)⍴⍋⍋⍺⍳⍺,⍵)} '1bbbpppeeeee'
@Adám 1 1 1 1 1 1 0 1 1 1 1 0
Alternatively, we could just call the function with swapped arguments:
⍞←'1bbbpppeeeee' {((⍴⍺)⍴⍋⍋⍺⍳⍺,⍵)∊(⍴⍵)⍴⍋⍋⍺⍳⍵,⍺} '11bbbpeepee'
Apr 25, 2018 6:54 PM
@Adám 1 1 1 1 1 1 0 1 1 1 1 0
This function is "membership without replacement", or "progressive dyadic epsilon".
@Adám that would make more sense to me because I'd phrase it as "How many people would fit in this plane."
@J.Sallé Yup, that's why and have their arguments in the order they have.
Did you notice the pattern? We are taking two functions and modifying them in a consistent manner? This calls for an operator!
⎕←↑ (p c)←'11bbbpeepee' '1bbbpppeeeee' ⋄ WithoutReplacement←{((⍴⍺)⍴⍋⍋⍺⍳⍺,⍵)⍺⍺(⍴⍵)⍴⍋⍋⍺⍳⍵,⍺} ⋄ ⎕←'11bbbpeepee' ⍳WithoutReplacement '1bbbpppeeeee'
@Adám
11bbbpeepee
1bbbpppeeeee
1 3 4 5 6 9 12 7 8 10 11 12
@DyalogAPL I'll assume that's not what we wanted :p
Apr 25, 2018 6:59 PM
⎕←↑ (p c)←'11bbbpeepee' '1bbbpppeeeee' ⋄ WithoutReplacement←{((⍴⍺)⍴⍋⍋⍺⍳⍺,⍵)⍺⍺(⍴⍵)⍴⍋⍋⍺⍳⍵,⍺} ⋄ ⎕←'1bbbpppeeeee' ∊WithoutReplacement '11bbbpeepee'
@Adám
11bbbpeepee
1bbbpppeeeee
1 1 1 1 1 1 0 1 1 1 1 0
@J.Sallé Retroactively, it is ;-)
Notice how the APL code reads much like normal English.
And that's all for tonight. Thank you for participating!
 
Conversation ended Apr 25, 2018 at 19:01.