Re: Working with arrays (flatten, transpose, verfify rectangular)
On Friday, 22 July 2022 at 05:17:49 UTC, anonymouse wrote: On Wednesday, 20 July 2022 at 09:18:29 UTC, anonymouse wrote: As for task 3, while I understand the concept of transposing a matrix, I'm not sure how to even begin. By not knowing how to begin, I mean that I don't know how to generalize the algorithm so that it applies to an array of arbitrary dimension/shape. If figure if I could do something like this, it would work: ```d static string s; s ~= FlatElementType!T.stringof; static foreach (i; a) s ~= "[" ~ to!string(i) ~ "]"; mixin(s) var; ``` Here, I'm receiving the shape of the array (```a```), composing a string of the actual type, then mixing it in to declare a variable of that type. Of course the compiler barfs at the idea as coded, but is there a way to accomplish this? Note that if you comment out the foreach loop, the variable gets created. Thanks, --anonymouse
Re: Working with arrays (flatten, transpose, verfify rectangular)
On Wednesday, 20 July 2022 at 09:18:29 UTC, anonymouse wrote:
As for task 3, while I understand the concept of transposing a
matrix, I'm not sure how to even begin.
By not knowing how to begin, I mean that I don't know how to
generalize the algorithm so that it applies to an array of
arbitrary dimension/shape. If I already know the dimensions, I
can hardcode that information and get it to work just fine. In
the example below, since I know that ```a``` has a shape of [3,
5, 7], I use that information to transpose the array:
```d
import std.traits;
auto transpose(A)(A a) if (isArray!A)
{
auto tmp = new FlatElementType!A[3][5][7]; // [1]
foreach(n0, i; a)
foreach(n1, j; i)
foreach(n2, k; j)
tmp[n2][n1][n0] = k;
return tmp;
}
void main()
{
auto a = [
[
[111,112,113,114,115,116,117],
[121,122,123,124,125,126,127],
[131,132,133,134,135,136,137],
[141,142,143,144,145,136,147],
[151,152,153,154,155,156,137]
],
[
[211,212,213,214,215,216,217],
[221,222,223,224,225,226,227],
[231,232,233,234,235,236,237],
[241,242,243,244,245,236,247],
[251,252,253,254,255,256,237]
],
[
[311,312,313,314,315,316,317],
[321,322,323,324,325,326,327],
[331,332,333,334,335,336,337],
[341,342,343,344,345,336,347],
[351,352,353,354,355,356,337]
]
];
a.transpose.writeln;
}
```
Output reformatted for visual presentation:
```
[
[
[111, 211, 311],
[121, 221, 321],
[131, 231, 331],
[141, 241, 341],
[151, 251, 351]
],
[
[112, 212, 312],
[122, 222, 322],
[132, 232, 332],
[142, 242, 342],
[152, 252, 352]
],
[
[113, 213, 313],
[123, 223, 323],
[133, 233, 333],
[143, 243, 343],
[153, 253, 353]
],
[
[114, 214, 314],
[124, 224, 324],
[134, 234, 334],
[144, 244, 344],
[154, 254, 354]
],
[
[115, 215, 315],
[125, 225, 325],
[135, 235, 335],
[145, 245, 345],
[155, 255, 355]
],
[
[116, 216, 316],
[126, 226, 326],
[136, 236, 336],
[136, 236, 336],
[156, 256, 356]
],
[
[117, 217, 317],
[127, 227, 327],
[137, 237, 337],
[147, 247, 347],
[137, 237, 337]
]
]
```
As the example demonstrates, by knowing beforehand that it is a
3D array of shape [3, 5, 7] , I can hardcode that information
into the temp array and use the correct amount of nested loops to
unwind and reassigned the values. I would like to accomplish this
without knowing the shape before hand.
Any pointers would be appreciated.
Thanks,
--anonymouse
[1] Contributed by
[ag0aep6g](https://forum.dlang.org/post/tb9pl1$gc1$1...@digitalmars.com)
Re: Working with arrays (flatten, transpose, verfify rectangular)
On Wednesday, 20 July 2022 at 16:15:33 UTC, Salih Dincer wrote: On Wednesday, 20 July 2022 at 09:18:29 UTC, anonymouse wrote: Given an array of arbitrary dimensions, I would like to accomplish three things: 1) verify that it is rectangular (e.g. all elements have the same length, all sub-elements have the same length, etc.) 2) flatten and return the flattened copy 3) transpose and return the transposed copy Yesterday, I published an example of a lesson we developed with Ali. It's same `transpose()` when I add extra `swap()` for you. I hope it works for you. Hello Salih, thanks for responding. I'm not seeing the transpose function here. What I meant by transpose is, given the following: ```d auto array = [ [111, 112, 113, 114], [121, 122, 123, 124], [131, 132, 133, 134], [141, 142, 143, 144] ] ``` after applying transpose(), you'd get back the following in return: [ [111, 121, 131, 141], [112, 122, 132, 142], [113, 123, 133, 143], [114, 124, 134, 144] ] This should scale to arrays of all dimensions, so the row vector (1D array): [100, 200, 300, 4000] would transpose to: [[100], [200], [300], [400]] In general, the transpose of any array yields an array with its shape reversed. For example, the following array of shape [2, 4, 5]: ```d auto array = [[ [111, 112, 113, 114, 115], [121, 122, 123, 124, 125], [131, 132, 133, 134, 135], [141, 142, 143, 144, 145] ], [ [211, 212, 213, 214, 125], [221, 222, 223, 224, 225], [231, 232, 233, 234, 235], [241, 242, 243, 244, 245] ]] ``` would become this array of shape [5, 4, 2] after transpose, with its columns becoming its rows and its rows becoming its columns: ```d [[[111, 211], [121, 221], [131, 231], [141, 241]], [[112, 212], [122, 222], [132, 232], [142, 242]], [[113, 213], [123, 223], [133, 233], [143, 243]], [[114, 214], [124, 224], [134, 234], [144, 244]], [[115, 215], [125, 225], [135, 235], [145, 245]]] ``` Thanks, --anonymouse
Re: Working with arrays (flatten, transpose, verfify rectangular)
On Wednesday, 20 July 2022 at 20:47:28 UTC, ag0aep6g wrote:
(Aside: You don't need that many backticks to mark code
fragments.)
Thought I was following the instructions but it looks like I got
a bit carried away. lol.
You've got a bug there. This should pass, but fails with your
version:
assert(!isRectangular([[1, 2], [], [3, 4]]));
Once `result` becomes false, you cannot let it switch to true
again.
Yeah, I noticed that. I actually fixed it at one point but since
I was having problems scaling whole thing beyond 2D, I thought I
got it wrong.
As for generalizing the function, instead of comparing the
lengths of the elements, you want to compare their "shapes".
The shape of a `Foo[] a1;` is `[a1.length]`. The shape of a
rectangular `Foo[][] a2;` is `[a2.length, a2[0].length]`. And
so on.
[...]
Thank you so much. That was super helpful.
I'm sure the function can be improved further, but I'm not
going to get into that.
For task 3, I can visit each element of the array, but I have
no idea how to compose the flattened (1D) version:
You've got the right idea there with `flatten` calling itself
on each element. You only need to apply that idea when getting
the element type, too (and actually append the result of the
recursive call to `result`):
import std.range.primitives: ElementType;
template FlatElementType(A) if (isArray!A)
{
alias E = ElementType!A;
static if (isArray!E)
{
alias FlatElementType = FlatElementType!E;
}
else
{
alias FlatElementType = E;
}
}
This is pure gold. Thank you.
result ~= flatten(i);
Wow. That simple. I actually printed out the contents of result
and saw the entire thing got was flattened during the recursion,
but for the life of me I couldn't figure out why the final output
always be empty.
[...]
As for task 3, while I understand the concept of transposing a
matrix, I'm not sure how to even begin.
I'm gonna leave that one for someone else.
Thanks again. I really appreciate the assistance.
--anonymouse
Re: Working with arrays (flatten, transpose, verfify rectangular)
On 20.07.22 11:18, anonymouse wrote:
d
auto isRectangular(A)(A a) if (isArray!A)
{
bool result;
size_t length = a[0].length;
foreach (e; a) {
result = e.length == length;
}
return result;
}
This only works if a is a 2D array, how do I extend this to
support arrays with larger dimensions (3D, 4D, 5D, etc.)?
(Aside: You don't need that many backticks to mark code fragments.)
You've got a bug there. This should pass, but fails with your version:
assert(!isRectangular([[1, 2], [], [3, 4]]));
Once `result` becomes false, you cannot let it switch to true again.
As for generalizing the function, instead of comparing the lengths of
the elements, you want to compare their "shapes". The shape of a `Foo[]
a1;` is `[a1.length]`. The shape of a rectangular `Foo[][] a2;` is
`[a2.length, a2[0].length]`. And so on.
Start by extending `isRectangular` to also (optionally) return the shape
of the array:
bool isRectangular(A)(A a) if (isArray!A)
{
size_t[] dummy;
return isRectangular(a, dummy);
}
bool isRectangular(A)(A a, out size_t[] shape) if (isArray!A)
{
size_t first_length = a[0].length;
foreach (e; a)
{
if (e.length != first_length) return false;
}
shape = [a.length, first_length];
return true;
}
unittest
{
size_t[] shape;
assert(isRectangular([[1, 2], [3, 4], [5, 6]], shape));
assert(shape == [3, 2]);
assert(!isRectangular([[1, 2], [], [3, 4]]));
}
Extend it to one-dimensional arrays:
bool isRectangular(A)(A a, out size_t[] shape) if (isArray!A)
{
shape = [a.length];
alias E = typeof(a[0]);
static if (isArray!E)
{
size_t first_length = a[0].length;
shape ~= first_length;
foreach (e; a)
{
if (e.length != first_length) return false;
}
}
return true;
}
unittest /* one dimension */
{
size_t[] shape;
assert(isRectangular([1, 2, 3], shape));
assert(shape == [3]);
}
Finally, use the magic of recursion to conquer higher dimensions:
bool isRectangular(A)(A a, out size_t[] shape) if (isArray!A)
{
shape = [a.length];
alias E = typeof(a[0]);
static if (isArray!E)
{
size_t[] first_shape;
if (!isRectangular(a[0], first_shape)) return false;
shape ~= first_shape;
foreach (e; a)
{
size_t[] e_shape;
if (!isRectangular(e, e_shape)) return false;
if (e_shape != first_shape) return false;
}
}
return true;
}
unittest /* higher dimensions */
{
size_t[] shape;
assert(isRectangular([
[[ 1, 2, 3, 4], [ 5, 6, 7, 8], [ 9, 10, 11, 12]],
[[13, 14, 15, 16], [17, 18, 19, 20], [21, 22, 23, 24]]
], shape));
assert(shape == [2, 3, 4]);
}
I'm sure the function can be improved further, but I'm not going to get
into that.
For task 3, I can visit each element of the array, but I have no idea
how to compose the flattened (1D) version:
d
import std.range.primitives: ElementType;
auto flatten(A)(A a) if (isArray!A)
{
//ElementType!(A)[] result; //[1]
foreach (i; a) {
static if (isArray!(typeof(i)))
flatten(i);
else {
writeln(i);
// result ~= i; //[2]
}
}
//return result; // [3]
}
You've got the right idea there with `flatten` calling itself on each
element. You only need to apply that idea when getting the element type,
too (and actually append the result of the recursive call to `result`):
import std.range.primitives: ElementType;
template FlatElementType(A) if (isArray!A)
{
alias E = ElementType!A;
static if (isArray!E)
{
alias FlatElementType = FlatElementType!E;
}
else
{
alias FlatElementType = E;
}
}
unittest
{
static assert(is(FlatElementType!(int[]) == int));
static assert(is(FlatElementType!(int[][]) == int));
static assert(is(FlatElementType!(int[][][]) == int));
}
auto flatten(A)(A a) if (isArray!A)
{
FlatElementType!A[] result;
foreach (i; a)
{
static if (isArray!(typeof(i)))
result ~= flatten(i);
else
result ~= i;
}
return result;
Re: Working with arrays (flatten, transpose, verfify rectangular)
On Wednesday, 20 July 2022 at 09:18:29 UTC, anonymouse wrote:
Given an array of arbitrary dimensions, I would like to
accomplish three things:
1) verify that it is rectangular (e.g. all elements
have the same length, all sub-elements have the same length,
etc.)
2) flatten and return the flattened copy
3) transpose and return the transposed copy
Yesterday, I published an example of a lesson we developed with
Ali. It's same `transpose()` when I add extra `swap()` for you.
I hope it works for you.
```d
import std.stdio;
struct Arrayish(T) {
T[] element;
size_t row, column;
this(size_t row, size_t column) {
this.element = new T[row * column];
this.row = row;
this.column = column;
}
ref T opIndex(size_t row, size_t column) {
size_t first = row * this.column;
size_t index = first + column;
return element[index];
}
auto opCast(R : T[][])() {
T[][] d;
foreach(i; 0..row)
d ~= slice(i);
return d;
}
auto slice(size_t i) {
size_t n = i * column;
return element[n..n + column];
}
@property {
auto length() {
return row * column;
}
auto dup() {
T[][] d;
foreach(i; 0..row)
d ~= slice(i).dup;
return d;
}
void swap() {
auto tmp = row;
row = column;
column = tmp;
}
}
}
enum { row = 2, col = 4 }
void main() {
auto arrayish = Arrayish!int(row, col);
foreach(r; 0..row) {
foreach(c; 0..col) {
const value = r * 1000 + c;
arrayish[r, c] = value;
}
}
//arrayish.swap();
const array = cast(int[][])arrayish;
arrayish[1, 0] = 100;
typeid(array).writeln(": ", array.length);
array.writefln!"%(%s\n%)";
arrayish.length.writeln(" total items");
auto arrayCopy = arrayish.dup;
arrayish[1, 0] = 1000;
typeid(arrayCopy).writeln(": ", array.length);
arrayCopy.writefln!"%(%s\n%)";
}
```
SDB@79
Working with arrays (flatten, transpose, verfify rectangular)
Given an array of arbitrary dimensions, I would like to
accomplish three things:
1) verify that it is rectangular (e.g. all elements have
the same length, all sub-elements have the same length, etc.)
2) flatten and return the flattened copy
3) transpose and return the transposed copy
Here is my naive attempt to accomplish the first task:
d
auto isRectangular(A)(A a) if (isArray!A)
{
bool result;
size_t length = a[0].length;
foreach (e; a) {
result = e.length == length;
}
return result;
}
This only works if a is a 2D array, how do I extend this
to support arrays with larger dimensions (3D, 4D, 5D, etc.)?
For task 3, I can visit each element of the array, but I have no
idea how to compose the flattened (1D) version:
d
import std.range.primitives: ElementType;
auto flatten(A)(A a) if (isArray!A)
{
//ElementType!(A)[] result; //[1]
foreach (i; a) {
static if (isArray!(typeof(i)))
flatten(i);
else {
writeln(i);
// result ~= i; //[2]
}
}
//return result; // [3]
}
The thought I had was to get the BaseType of the array (int,
double, etc.) and use it to create a dynamic array [1]. I could
then concatenate each element [2], and return the result once
completed [3]. This approach has two major problems and probably
many other's I'm not yet experienced enough to see. The first is
that there's no way to get the BaseType of an array. ElementType
in the example assumes that array is 2D, therefore anything else
passed in will result in a multi-dimensional array being created
to which individual elements cannot be concatenated. The second
issue is that each call to flatten will have it's own result
which will be discarded when the function exits, so the final
result will be an empty array.
As for task 3, while I understand the concept of transposing a
matrix, I'm not sure how to even begin.
These tasks are all self assigned and not associated with any
high school or college course. Just trying get a better
understanding of how arrays and matrices/tensors work while
reading up on linear algebra. This is purely self study and I
would really appreciate some assistance.
Thanks,
---anonymouse
