digitalmars.D.learn - Working with arrays (flatten, transpose, verfify rectangular)
- anonymouse (59/59) Jul 20 2022 Given an array of arbitrary dimensions, I would like to
- Salih Dincer (69/76) Jul 20 2022 Yesterday, I published an example of a lesson we developed with
- anonymouse (69/80) Jul 21 2022 Hello Salih, thanks for responding. I'm not seeing the transpose
- ag0aep6g (128/164) Jul 20 2022 (Aside: You don't need that many backticks to mark code fragments.)
- anonymouse (15/54) Jul 21 2022 Thought I was following the instructions but it looks like I got
- anonymouse (110/112) Jul 21 2022 By not knowing how to begin, I mean that I don't know how to
- anonymouse (16/24) Jul 22 2022 If figure if I could do something like this, it would work:
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
Jul 20 2022
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
Jul 20 2022
anonymouse <anony mouse.com> 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: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, --anonymouseGiven 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 copyYesterday, 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.
Jul 21 2022
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; } unittest { assert(flatten([[1, 2], [3, 4, 5], [6]]) == [1, 2, 3, 4, 5, 6]); assert(flatten([[[1, 2], [3, 4]], [[5, 6], [7, 8]]]) == [1, 2, 3, 4, 5, 6, 7, 8]); } [...]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.
Jul 20 2022
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.This is pure gold. Thank you.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; } }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.[...]Thanks again. I really appreciate the assistance. --anonymouseAs 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.
Jul 21 2022
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)
Jul 21 2022
On Friday, 22 July 2022 at 05:17:49 UTC, anonymouse wrote:On Wednesday, 20 July 2022 at 09:18:29 UTC, anonymouse wrote: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, --anonymouseAs 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.
Jul 22 2022