www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Working with arrays (flatten, transpose, verfify rectangular)

reply anonymouse <anony mouse.com> writes:
     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
next sibling parent reply Salih Dincer <salihdb hotmail.com> writes:
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
parent anonymouse <anony mouse.com> writes:
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
Jul 21 2022
prev sibling next sibling parent reply ag0aep6g <anonymous example.com> writes:
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
parent anonymouse <anony mouse.com> writes:
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
Jul 21 2022
prev sibling parent reply anonymouse <anony mouse.com> writes:
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
parent anonymouse <anony mouse.com> writes:
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
Jul 22 2022