Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #6640 > unrolled thread

generating permutations

Back to article view | Back to comp.programming

Contents

  generating permutations luser droog <mijoryx@yahoo.com> - 2016-05-22 02:46 -0700
    Re: generating permutations bart4858@gmail.com - 2016-05-22 05:36 -0700
      Re: generating permutations luser droog <mijoryx@yahoo.com> - 2016-05-22 14:40 -0700
        Re: generating permutations Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-05-22 22:58 +0100
        Re: generating permutations BartC <bc@freeuk.com> - 2016-05-23 14:09 +0100
          Re: generating permutations luser droog <mijoryx@yahoo.com> - 2016-05-23 21:36 -0700
            Re: generating permutations BartC <bc@freeuk.com> - 2016-05-24 12:56 +0100
              Re: generating permutations luser droog <mijoryx@yahoo.com> - 2016-05-25 19:03 -0700
                Re: generating permutations BartC <bc@freeuk.com> - 2016-05-26 13:08 +0100
                  Re: generating permutations luser droog <mijoryx@yahoo.com> - 2016-05-26 08:35 -0700

#6640 — generating permutations

Background in the comp.lang.apl thread "implementing bracket indexing". 
I need to generate (indexed) permutations for general selections 
from my multi-dimensional arrays. It appears from Wikipedia that the 
way to convert between index and permutation is via the *factoradic 
number system*, a mixed-radix system following the factorial series. 

So, we're back to the old friend factorial. I'll probably outfit it 
with some sort of caching like we explored in a recent thread in
comp.lang.c. Then Lehmer de-code the resulting sequence. 

Maybe I'm getting ahead of my explanation. What I'm doing is, implementing 
the behavior for indexing an array with more than one number at an 
index position. I've got semicolons separating elements of the index 
vector and you can elide a position to select the entire dimension of
the array. 

    a[;;1]   //select just column 1 from 3D table, yielding 2D table 

But I want to enable selecting an arbitrary collection of elements 
at each index. 

    a[0 3 5;;1]  //select items 0 3 5, all rows, column 1 

So, to have an indirect representation so it's still an l-value slice* 
of the original array a, I need to search the space of permutations 
for one with the prefix (0 3 5), store its index in the representation 
(as an element of the `int perm[rank];` vector, probably). One 
incidental unsolved problem is storing the new dimension 3 (because 0 3 5 
is 3 numbers) and the dimension of the "source" array so the permutations 
are generated according to the shape of the actual data in memory. 

Then I need the reverse: taking the perm index and the dimension 
(so, I think, according to Wikipedia, I'm doing a k-permutation of n) 
and taking the first k elements to transform my indices to access 
the array itself. 

Unless there are better ways of going about this that I'm not seeing?? 



* It needs to be an "l-value", indirectly referring to the original array 
so that an indexed expression can be the target of assignment. 
This already works for the simple slicing that is implemented. 
So if I maintain this l-value property, then the assignment feature 
will keep working with these more-powerful indexing behaviors. 

At a later point I may wish to extend this behavior to allow repetitions
to duplicate elements at a particular dimension. 

[toc] | [next] | [standalone]

#6641

On Sunday, 22 May 2016 10:46:20 UTC+1, luser droog  wrote:

> Maybe I'm getting ahead of my explanation. What I'm doing is, implementing 
> the behavior for indexing an array with more than one number at an 
> index position. I've got semicolons separating elements of the index 
> vector and you can elide a position to select the entire dimension of
> the array. 
> 
>     a[;;1]   //select just column 1 from 3D table, yielding 2D table 
> 
> But I want to enable selecting an arbitrary collection of elements 
> at each index. 
> 
>     a[0 3 5;;1]  //select items 0 3 5, all rows, column 1 
> 
> So, to have an indirect representation so it's still an l-value slice* 


> * It needs to be an "l-value", indirectly referring to the original array 
> so that an indexed expression can be the target of assignment. 
> This already works for the simple slicing that is implemented. 

Simple slicing is easy, at least in one dimension. Your proposal sounds much more difficult. If you consider only a 2D array and allow any set of indices and ranges for each of the two dimensions, you will, in general, end up with a 2D matrix of separate sub-arrays. Each might be a single element, a short row or column, or a small matrix.

Suppose you do want to assign to such a set of arrays, what will the right-hand-side of the assignment look like?

And can indices in the array be repeated? For example: a[2 2 2 2;] which returns 4 copies of element #2. This can make sense for an rvalue, but not for an lvalue.

(For simple slices, then for the same 2D array, a different slice for each dimension yields a single sub-array. It's still not that simple to implement for an lvalue, but the rhs of an assignment at least is easy to write: it's just an array with the same dimensions as the slice.)

I don't know where the permutations come into it, unless it's to do with setting up sort of indirect array which maps indices in the range of your chosen sets of elements, into the indices of the original array.


-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#6642

On Sunday, May 22, 2016 at 7:36:30 AM UTC-5, bart...@gmail.com wrote:
> On Sunday, 22 May 2016 10:46:20 UTC+1, luser droog  wrote:
> 
> > Maybe I'm getting ahead of my explanation. What I'm doing is, implementing 
> > the behavior for indexing an array with more than one number at an 
> > index position. I've got semicolons separating elements of the index 
> > vector and you can elide a position to select the entire dimension of
> > the array. 
> > 
> >     a[;;1]   //select just column 1 from 3D table, yielding 2D table 
> > 
> > But I want to enable selecting an arbitrary collection of elements 
> > at each index. 
> > 
> >     a[0 3 5;;1]  //select items 0 3 5, all rows, column 1 
> > 
> > So, to have an indirect representation so it's still an l-value slice* 
> 
> 
> > * It needs to be an "l-value", indirectly referring to the original array 
> > so that an indexed expression can be the target of assignment. 
> > This already works for the simple slicing that is implemented. 
> 
> Simple slicing is easy, at least in one dimension. Your proposal sounds much more difficult. If you consider only a 2D array and allow any set of indices and ranges for each of the two dimensions, you will, in general, end up with a 2D matrix of separate sub-arrays. Each might be a single element, a short row or column, or a small matrix.
> 

That is also possible. An element of an array can in fact be another array,
but it's "concealed" behind its encoding as an atomic element. But an array
is implemented with a hefty 'dope vector' or descriptor or display which
allow simple slicing to still share the original data through a modified
descriptor. The result will still be rectangular, but is no longer bound
by the linear mapping of the generalized indexing formula. The descriptor
will be augmented with extra index-transformation powers.

> Suppose you do want to assign to such a set of arrays, what will the right-hand-side of the assignment look like?

The rhs is simply reshaped to the shape of the lhs. So it relies entirely
on the lhs object to have a coherent representation.
 
> And can indices in the array be repeated? For example: a[2 2 2 2;] which returns 4 copies of element #2. This can make sense for an rvalue, but not for an lvalue.
> 

That's a good point. I may want to flag arrays with duplicated ... what do
you call those? ... referents along a dimension as not acceptable targets.

> (For simple slices, then for the same 2D array, a different slice for each dimension yields a single sub-array. It's still not that simple to implement for an lvalue, but the rhs of an assignment at least is easy to write: it's just an array with the same dimensions as the slice.)
> 
> I don't know where the permutations come into it, unless it's to do with setting up sort of indirect array which maps indices in the range of your chosen sets of elements, into the indices of the original array.
> 

Permutations were a way of thinking into the implementation issues. 
It makes for a very storage-efficient representation, I think, but
generating permutations on-the-fly seems algorithmically irresponsible,
especially in light of Tim Rentsch's ideas in the duplicate clc thread.

It doesn't address duplicated referents in a dimension, but I skimmed
over a blurb about perms with dups in the Wikipedia article, so I
thought I might worry about that later and focus on implementing 
some step towards that sooner.

[toc] | [prev] | [next] | [standalone]

#6643

luser droog <mijoryx@yahoo.com> writes:
<snip>
> [...] But an array
> is implemented with a hefty 'dope vector' or descriptor or display which
> allow simple slicing to still share the original data through a modified
> descriptor. The result will still be rectangular, but is no longer bound
> by the linear mapping of the generalized indexing formula. The descriptor
> will be augmented with extra index-transformation powers.

Yes, surely a slice (like yours at least) is just an array whose indexes
go through a table first?  And it seems possible (at first glance) that
you could implement this table as one of your unsliced array objects.
This might be slow for something or memory hungry for others (which it
why some languages have a more constrained notion of a slice) but often
the best plan is to implement something and see if indeed suits your
purpose.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#6644

On 22/05/2016 22:40, luser droog wrote:
> On Sunday, May 22, 2016 at 7:36:30 AM UTC-5, bart...@gmail.com wrote:
>> On Sunday, 22 May 2016 10:46:20 UTC+1, luser droog  wrote:
>>
>>> Maybe I'm getting ahead of my explanation. What I'm doing is, implementing
>>> the behavior for indexing an array with more than one number at an
>>> index position. I've got semicolons separating elements of the index
>>> vector and you can elide a position to select the entire dimension of
>>> the array.
>>>
>>>     a[;;1]   //select just column 1 from 3D table, yielding 2D table
>>>
>>> But I want to enable selecting an arbitrary collection of elements
>>> at each index.
>>>
>>>     a[0 3 5;;1]  //select items 0 3 5, all rows, column 1
>>>
>>> So, to have an indirect representation so it's still an l-value slice*
>>
>>
>>> * It needs to be an "l-value", indirectly referring to the original array
>>> so that an indexed expression can be the target of assignment.
>>> This already works for the simple slicing that is implemented.
>>
>> Simple slicing is easy, at least in one dimension. Your proposal sounds much more difficult. If you consider only a 2D array and allow any set of indices and ranges for each of the two dimensions, you will, in general, end up with a 2D matrix of separate sub-arrays. Each might be a single element, a short row or column, or a small matrix.
>>
>
> That is also possible. An element of an array can in fact be another array,
> but it's "concealed" behind its encoding as an atomic element.

No, I mean the result of your slicing can be an array, and perhaps lots 
of them, depending on how you pin down exactly what is meant by multiple 
slicing.

For example, take this is 2D array A of 3 rows of 5 columns:

((3 1 4 1 5)
  (9 2 6 5 3)
  (5 8 9 7 9)
  (3 2 3 8 4))

Assume indexing is one-based. A[2] is (9,2,6,5,3). A[2..3] is a slice 
consisting of the two rows:

  ((9,2,6,5,3),
   (5,8,8,7,9))

What about A[2..3;4] (using your semicolon method to separate 
dimensions)? Should it be the vertical vector (5,7)?

(I tried it on my language and that doesn't work, since arrays are 
1-dimensional: once A[2..3] yields the slice of two rows, then the 4 is 
out of bounds as it is operating on that slice, not the original array.)

With your true multi-dim arrays, then A[;4] presumably yields the column 
(1,5,7,8), while A[1 3 5;4] gives the column (1,7,8), and A[1 3 4;2 4] 
will give... now I'm lost! The A[1 3 4] is:

((3 1 4 1 5)
  (5 8 9 7 9)
  (3 2 3 8 4))

So adding ;2 4 might yield:

((1 1)
  (8 7)
  (2 8))

Nice and compact, perhaps the shape of your RHS on an assignment. But 
take a look at the original with just these highlighted:

((- 1 - 1 -)
  (- - - - -)
  (- 8 - 7 -)
  (- 2 - 8 -))

You selected 4 sub-arrays of the original: 2 individual elements, and 2 
column vectors of two elements each, arranged as a 2x2 array of 
sub-arrays; this is what I meant before. You're defining a rectangular 
matrix of sub-arrays using this slicing scheme.

(Note also that once you've created your complex multi-dimensional 
slice, someone might want to slice /that/!)

>> And can indices in the array be repeated? For example: a[2 2 2 2;] which returns 4 copies of element #2. This can make sense for an rvalue, but not for an lvalue.
>>
>
> That's a good point. I may want to flag arrays with duplicated ... what do
> you call those? ... referents along a dimension as not acceptable targets.

There's also ordering to consider: A[2 4 6] might give a different slice 
to A[6 4 2]. This can be useful for both lvalues and rvalues.

(I suppose it depends on whether the index for each dimension is a 
number, a range (ie. a normal slice from A to B), an ordered set, or a 
list, or ...)

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#6651

On Monday, May 23, 2016 at 8:09:33 AM UTC-5, Bart wrote:
> On 22/05/2016 22:40, luser droog wrote:
> > On Sunday, May 22, 2016 at 7:36:30 AM UTC-5, bart...@gmail.com wrote:
> >> On Sunday, 22 May 2016 10:46:20 UTC+1, luser droog  wrote:
> >>
> >>> Maybe I'm getting ahead of my explanation. What I'm doing is, implementing
> >>> the behavior for indexing an array with more than one number at an
> >>> index position. I've got semicolons separating elements of the index
> >>> vector and you can elide a position to select the entire dimension of
> >>> the array.
> >>>
> >>>     a[;;1]   //select just column 1 from 3D table, yielding 2D table
> >>>
> >>> But I want to enable selecting an arbitrary collection of elements
> >>> at each index.
> >>>
> >>>     a[0 3 5;;1]  //select items 0 3 5, all rows, column 1
> >>>
> >>> So, to have an indirect representation so it's still an l-value slice*
> >>
> >>
> >>> * It needs to be an "l-value", indirectly referring to the original array
> >>> so that an indexed expression can be the target of assignment.
> >>> This already works for the simple slicing that is implemented.
> >>
> >> Simple slicing is easy, at least in one dimension. Your proposal sounds much more difficult. If you consider only a 2D array and allow any set of indices and ranges for each of the two dimensions, you will, in general, end up with a 2D matrix of separate sub-arrays. Each might be a single element, a short row or column, or a small matrix.
> >>
> >
> > That is also possible. An element of an array can in fact be another array,
> > but it's "concealed" behind its encoding as an atomic element.
> 
> No, I mean the result of your slicing can be an array, and perhaps lots 
> of them, depending on how you pin down exactly what is meant by multiple 
> slicing.
> 
> For example, take this is 2D array A of 3 rows of 5 columns:
> 
> ((3 1 4 1 5)
>   (9 2 6 5 3)
>   (5 8 9 7 9)
>   (3 2 3 8 4))
> 
> Assume indexing is one-based. A[2] is (9,2,6,5,3). A[2..3] is a slice 
> consisting of the two rows:
> 
>   ((9,2,6,5,3),
>    (5,8,8,7,9))
> 
> What about A[2..3;4] (using your semicolon method to separate 
> dimensions)? Should it be the vertical vector (5,7)?
> 
> (I tried it on my language and that doesn't work, since arrays are 
> 1-dimensional: once A[2..3] yields the slice of two rows, then the 4 is 
> out of bounds as it is operating on that slice, not the original array.)
> 
> With your true multi-dim arrays, then A[;4] presumably yields the column 
> (1,5,7,8), while A[1 3 5;4] gives the column (1,7,8), and A[1 3 4;2 4] 
> will give... now I'm lost! The A[1 3 4] is:
> 
> ((3 1 4 1 5)
>   (5 8 9 7 9)
>   (3 2 3 8 4))
> 
> So adding ;2 4 might yield:
> 
> ((1 1)
>   (8 7)
>   (2 8))
> 
> Nice and compact, perhaps the shape of your RHS on an assignment. But 
> take a look at the original with just these highlighted:
> 
> ((- 1 - 1 -)
>   (- - - - -)
>   (- 8 - 7 -)
>   (- 2 - 8 -))
> 
> You selected 4 sub-arrays of the original: 2 individual elements, and 2 
> column vectors of two elements each, arranged as a 2x2 array of 
> sub-arrays; this is what I meant before. You're defining a rectangular 
> matrix of sub-arrays using this slicing scheme.
> 
> (Note also that once you've created your complex multi-dimensional 
> slice, someone might want to slice /that/!)

Yes, all correct. And other APLs already have this power AFAIUI.

> >> And can indices in the array be repeated? For example: a[2 2 2 2;] which returns 4 copies of element #2. This can make sense for an rvalue, but not for an lvalue.
> >>
> >
> > That's a good point. I may want to flag arrays with duplicated ... what do
> > you call those? ... referents along a dimension as not acceptable targets.
> 
> There's also ordering to consider: A[2 4 6] might give a different slice 
> to A[6 4 2]. This can be useful for both lvalues and rvalues.
> 
> (I suppose it depends on whether the index for each dimension is a 
> number, a range (ie. a normal slice from A to B), an ordered set, or a 
> list, or ...)

Yes, that is exactly the issue that comes up. I think it can be managed
due to the flexibility of the data structure.

As it is now, the nounidx() function which performs the indexing
receives the indices already packed in an array object. It is a 1D
array or vector and (since it currently accepts only 0 or 1 indices)
each element is a nonnegative index or -1 which designates the 
entire range of the respective dimension.

So [1;2;3;4] becomes (1,2,3,4)
   [;;;2]    becomes (-1,-1,-1,2)

So, I can naturally pack several indices into a single position
by encoding the sub-array as an atomic object, nesting it.

So [1 2 3;;;4] becomes ((1,2,3),-1,-1,4)

And the `type()` of each element will indicate whether it is a
number or an encoded array (or any of several other types of 
object).

The last example of mine is bad, because if the multiset is 
a linear sequence then it can be accommodated by existing
means by manipulating the extents and weights used in the
indexing formula. So for 1,2,3 you just add 1 to the offset
and trim the extents to 3. For 2,4,8 you add 2 to the offset,
trim the extents to 3, *and* multiply the weight by 2.
I can recognize these easily if they are the result of 
the iota() function, possibly with additional arithmetic applied,
because the result will be a special 'lazy' function-type array.
But I'll need special logic to try to recognize these patterns
from a multiset that is the result of free-form input, ie. 
literally typing "1,2,3" rather than "1+⍳3".

[toc] | [prev] | [next] | [standalone]

#6655

On 24/05/2016 05:36, luser droog wrote:
> On Monday, May 23, 2016 at 8:09:33 AM UTC-5, Bart wrote:

>> For example, take this is 2D array A of 3 rows of 5 columns:
>>
>> ((3 1 4 1 5)
>>   (9 2 6 5 3)
>>   (5 8 9 7 9)

>> So adding ;2 4 might yield:
>>
>> ((1 1)
>>   (8 7)
>>   (2 8))
>>
>> Nice and compact, perhaps the shape of your RHS on an assignment. But
>> take a look at the original with just these highlighted:
>>
>> ((- 1 - 1 -)
>>   (- - - - -)
>>   (- 8 - 7 -)
>>   (- 2 - 8 -))
>>
>> You selected 4 sub-arrays of the original: 2 individual elements, and 2
>> column vectors of two elements each, arranged as a 2x2 array of
>> sub-arrays; this is what I meant before. You're defining a rectangular
>> matrix of sub-arrays using this slicing scheme.

> Yes, all correct. And other APLs already have this power AFAIUI.

I tried adding this feature on one of my languages, using functions to 
do the slicing rather than changing the language.

It was surprisingly difficult!

As I chose to implement it (bear in mind I only spent an hour or so):

* It only handles rvalues (lvalues require language changes)

* The selection set for each dimension doesn't allow duplicates (they 
are ignored) and the indices are always sorted

* For a 2D array, the row-selector highlights a set of rows, and the 
column-selector highlights a set of columns. Where those intersect, 
those are the elements that are selected.

* Selected elements are copied (using a shallow copy in this case) to 
form a new 2D array consisting of the chosen elements in a compact 
non-sparse format.

* It needs a dedicated routine for each number of dimensions.

(The best I can do with lvalues, without changing anything deep, is to 
instead return a compact selection array consisting of /pointers/ to 
each element, but then code must explicitly dereference those pointers.)

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#6662

On Tuesday, May 24, 2016 at 6:56:30 AM UTC-5, Bart wrote:
> On 24/05/2016 05:36, luser droog wrote:
> > On Monday, May 23, 2016 at 8:09:33 AM UTC-5, Bart wrote:
> 
> >> For example, take this is 2D array A of 3 rows of 5 columns:
> >>
> >> ((3 1 4 1 5)
> >>   (9 2 6 5 3)
> >>   (5 8 9 7 9)
> 
> >> So adding ;2 4 might yield:
> >>
> >> ((1 1)
> >>   (8 7)
> >>   (2 8))
> >>
> >> Nice and compact, perhaps the shape of your RHS on an assignment. But
> >> take a look at the original with just these highlighted:
> >>
> >> ((- 1 - 1 -)
> >>   (- - - - -)
> >>   (- 8 - 7 -)
> >>   (- 2 - 8 -))
> >>
> >> You selected 4 sub-arrays of the original: 2 individual elements, and 2
> >> column vectors of two elements each, arranged as a 2x2 array of
> >> sub-arrays; this is what I meant before. You're defining a rectangular
> >> matrix of sub-arrays using this slicing scheme.
> 
> > Yes, all correct. And other APLs already have this power AFAIUI.
> 
> I tried adding this feature on one of my languages, using functions to 
> do the slicing rather than changing the language.
> 
> It was surprisingly difficult!
> 
> As I chose to implement it (bear in mind I only spent an hour or so):

Very cool. It took me an hour to write but a day to
debug it. Stupid typo early on took forever to find.

Here's a an illustration of some of the slices described upthread,
adjusting for 0-based indexing.

$ ./olmec
        b←3 5⍴3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
        b[;2 4]
 4 5
 6 3
 9 9

        b[;1 3]
 1 1
 2 5
 8 7

        b←4 5⍴3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4
        b
 3 1 4 1 5
 9 2 6 5 3
 5 8 9 7 9
 3 2 3 8 4

        b[1]
 0 0 12 1 3
        b[1;]
 9 2 6 5 3
        b[1 2;]
 9 2 6 5 3
 5 8 9 7 9

        b[1 2;3]
 5 7
        b[;3]
 1 5 7 8
        b[0 2 4;3]             # Bug: missing error: index 4 out of range
 1 7 0
        b[0 2 3;]  
 3 1 4 1 5
 5 8 9 7 9
 3 2 3 8 4

        b[0 2 3;][;1 3]         ## Bug!
 1 1
 4 5
 1 9

        b[0 2 3;1 3]
 1 1
 8 7
 2 8

        b[0 2 3;1 3]←'X'
        b
 3 X 4 X 5
 9 2 6 5 3
 5 X 9 X 9
 3 X 3 X 4

      

[toc] | [prev] | [next] | [standalone]

#6663

On 26/05/2016 03:03, luser droog wrote:
> On Tuesday, May 24, 2016 at 6:56:30 AM UTC-5, Bart wrote:
>> On 24/05/2016 05:36, luser droog wrote:
>>> On Monday, May 23, 2016 at 8:09:33 AM UTC-5, Bart wrote:
>>
>>>> For example, take this is 2D array A of 3 rows of 5 columns:
>>>>
>>>>  ((3 1 4 1 5)
>>>>   (9 2 6 5 3)
>>>>   (5 8 9 7 9)
 >>>>   (3 2 3 8 4))  [Reinstated snipped last row)

>> I tried adding this feature on one of my languages, using functions to
>> do the slicing rather than changing the language.
>>
>> It was surprisingly difficult!

> Very cool. It took me an hour to write but a day to
> debug it. Stupid typo early on took forever to find.
>
> Here's a an illustration of some of the slices described upthread,
> adjusting for 0-based indexing.
>
> $ ./olmec
>         b←3 5⍴3 1 4 1 5 9 2 6 5 3 5 8 9 7 9

(Note my example was actually 4x5 but the last row was lost at some point)

>         b[;2 4]
>  4 5
>  6 3
>  9 9

So this is all rows (the first index) and columns 2 and 4.

>         b←4 5⍴3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4
>         b
>  3 1 4 1 5
>  9 2 6 5 3
>  5 8 9 7 9
>  3 2 3 8 4
>
>         b[1]
>  0 0 12 1 3

What does the above do?

>         b[1;]
>  9 2 6 5 3

OK, row 1 of 0..3, and all columns.

>         b[1 2;]
>  9 2 6 5 3
>  5 8 9 7 9
>
>         b[1 2;3]
>  5 7

Select columm 3 of the above two rows, although I would have expected:

    5
    7

>         b[0 2 3;1 3]←'X'
>         b
>  3 X 4 X 5
>  9 2 6 5 3
>  5 X 9 X 9
>  3 X 3 X 4

OK, your assign semantics just treats the rhs as a stream of data or 
whatever shape. When it gets to the end of the data, it starts again.

This a further example you posted to comp.lang.c:

 >         + a←⍳3 3 3
 >   0  1  2
 >   3  4  5
 >   6  7  8
 >
 >   9 10 11
 >  12 13 14
 >  15 16 17
 >
 >  18 19 20
 >  21 22 23
 >  24 25 26
 >
 >
 >         a[2 0;;2]
 >  20 23 26
 >   2  5  8

I had some difficulties with this slicing and had to re-imagine this 
3x3x3 matrix like this in '3D' (fixed pitch font needed):

                             18
                                  19
               9             21        20
                    10            22
0             12        11  24        23
      1             13            25
3          2  15        14            26
      4             16
6          5            17
      7
            8

X index is front to back
Y is top to bottom (omitted, so entire columns are selected)
Z is right to left

So it actually works quite well, apart from the orientation of the 
selection. I'll have a go at implementing this I think, allowing 
repeated indices and using the specified order.

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#6664

On Thursday, May 26, 2016 at 7:08:52 AM UTC-5, Bart wrote:
> On 26/05/2016 03:03, luser droog wrote:
> > On Tuesday, May 24, 2016 at 6:56:30 AM UTC-5, Bart wrote:
> >> On 24/05/2016 05:36, luser droog wrote:
> >>> On Monday, May 23, 2016 at 8:09:33 AM UTC-5, Bart wrote:
> >>
> >>>> For example, take this is 2D array A of 3 rows of 5 columns:
> >>>>
> >>>>  ((3 1 4 1 5)
> >>>>   (9 2 6 5 3)
> >>>>   (5 8 9 7 9)
>  >>>>   (3 2 3 8 4))  [Reinstated snipped last row)
> 
> >> I tried adding this feature on one of my languages, using functions to
> >> do the slicing rather than changing the language.
> >>
> >> It was surprisingly difficult!
> 
> > Very cool. It took me an hour to write but a day to
> > debug it. Stupid typo early on took forever to find.
> >
> > Here's a an illustration of some of the slices described upthread,
> > adjusting for 0-based indexing.
> >
> > $ ./olmec
> >         b←3 5⍴3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
> 
> (Note my example was actually 4x5 but the last row was lost at some point)
> 
> >         b[;2 4]
> >  4 5
> >  6 3
> >  9 9
> 
> So this is all rows (the first index) and columns 2 and 4.
> 
> >         b←4 5⍴3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4
> >         b
> >  3 1 4 1 5
> >  9 2 6 5 3
> >  5 8 9 7 9
> >  3 2 3 8 4
> >
> >         b[1]
> >  0 0 12 1 3
> 
> What does the above do?

That's a bug I neglected to mark. It should be the same as `b[1;]`.
There's a different grammar production used when there's no semicolon
present.

> >         b[1;]
> >  9 2 6 5 3
> 
> OK, row 1 of 0..3, and all columns.
> 
> >         b[1 2;]
> >  9 2 6 5 3
> >  5 8 9 7 9
> >
> >         b[1 2;3]
> >  5 7
> 
> Select columm 3 of the above two rows, although I would have expected:
> 
>     5
>     7

Since only one column was selected, the whole dimension was suppressed.
So the result is just a 1D vector.

> >         b[0 2 3;1 3]←'X'
> >         b
> >  3 X 4 X 5
> >  9 2 6 5 3
> >  5 X 9 X 9
> >  3 X 3 X 4
> 
> OK, your assign semantics just treats the rhs as a stream of data or 
> whatever shape. When it gets to the end of the data, it starts again.

Right, the APL reshape function creates an array of the appropriate 
dimensions and then just copies the data over, in row-major order,
repeating as necessary. And the 'copy assignment' implicitly does
a reshape(shapeof(lhs),rhs) so the two parts are compatible.

> This a further example you posted to comp.lang.c:
> 
>  >         + a←⍳3 3 3
>  >   0  1  2
>  >   3  4  5
>  >   6  7  8
>  >
>  >   9 10 11
>  >  12 13 14
>  >  15 16 17
>  >
>  >  18 19 20
>  >  21 22 23
>  >  24 25 26
>  >
>  >
>  >         a[2 0;;2]
>  >  20 23 26
>  >   2  5  8
> 
> I had some difficulties with this slicing and had to re-imagine this 
> 3x3x3 matrix like this in '3D' (fixed pitch font needed):
> 
>                              18
>                                   19
>                9             21        20
>                     10            22
> 0             12        11  24        23
>       1             13            25
> 3          2  15        14            26
>       4             16
> 6          5            17
>       7
>             8
> 
> X index is front to back
> Y is top to bottom (omitted, so entire columns are selected)
> Z is right to left

Yes, the 3D ones required more effort for me to imagine as well.
The way I think of it is that each block or plane is printed out
on a page and then those pages are stacked up. So I think of it
as pulling the bottom edge of each block *forward*, and adding
pillars or pylons that connect the corners.

          + a←⍳3 3 3 
    |0  1  2 
    |  3  4  5 
    |    6  7  8| 
    |           |
    |9 10 11    |
    | 12 13 14  |
    |   15 16 17| 
    |           |
    |18 19 20   |
      21 22 23  |
        24 25 26| 

This pov requires less 'rotation'.

> So it actually works quite well, apart from the orientation of the 
> selection. I'll have a go at implementing this I think, allowing 
> repeated indices and using the specified order.

Excellent.

-- 
"That's Tron. He fights for the Users."

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web