How to Swap Array-Elements to Transfer the Array from a Column-Like into a Row-Like Representation

how to swap array-elements to transfer the array from a column-like into a row-like representation

The term you're looking for is in-place matrix transpose, and here's an implementation.

Transposing a 2D-array in JavaScript

output = array[0].map((_, colIndex) => array.map(row => row[colIndex]));

map calls a provided callback function once for each element in an array, in order, and constructs a new array from the results. callback is invoked only for indexes of the array which have assigned values; it is not invoked for indexes which have been deleted or which have never been assigned values.

callback is invoked with three arguments: the value of the element, the index of the element, and the Array object being traversed. [source]

Transforming a row vector into a column vector in Numpy

you can use the transpose operation to do this:

Example:

In [2]: a = np.array([[1,2], [3,4], [5,6]])
In [5]: a.shape
Out[5]: (3, 2)

In [6]: a_trans = a.T    #or: np.transpose(a), a.transpose()
In [8]: a_trans.shape
Out[8]: (2, 3)
In [7]: a_trans
Out[7]: 
array([[1, 3, 5],
       [2, 4, 6]])

Note that the original array a will still remain unmodified. The transpose operation will just make a copy and transpose it.

---

If your input array is rather 1D, then you can promote the array to a column vector by introducing a new (singleton) axis as the second dimension. Below is an example:

# 1D array
In [13]: arr = np.arange(6)

# promotion to a column vector (i.e., a 2D array)
In [14]: arr = arr[..., None]    #or: arr = arr[:, np.newaxis]

In [15]: arr
Out[15]: 
array([[0],
       [1],
       [2],
       [3],
       [4],
       [5]])

In [12]: arr.shape
Out[12]: (6, 1)

---

For the 1D case, yet another option would be to use numpy.atleast_2d() followed by a transpose operation, as suggested by ankostis in the comments.

In [9]: np.atleast_2d(arr).T
Out[9]: 
array([[0],
       [1],
       [2],
       [3],
       [4],
       [5]])

Interleave three equally sized partitions in an array inplace in O(n) time

Since David does not seem interested in writing it down (well obviously he is interested, see the other answer :), I will use his reference to arrive at an algorithm for the case with 3 partitions.

First note that if we can solve the problem efficiently for some m < n using an algorithm A, we can rearrange the array so that we can apply A and are then left with a smaller subproblem. Say the original array is

x1 .. xm x{m+1}.. xn y1 .. ym y{m+1} .. yn z1 .. zm z{m+1} .. zn

We want to rearrange it to

x1 .. xm y1 .. ym z1 .. zm x{m+1} .. xn y{m+1} .. yn z{m+1} .. zn

This is basically a transformation of the pattern AaBbCc to ABCabc where A, B, C and a, b, c have the same lengths, respectively. We can achieve that through a series of reversals. Let X' denote the reversal of string X here:

   AaBbCc
-> Aa(BbCc)' = Aac'C'b'B'
-> Aac'(C'b')'B' = Aac'bCB'
-> A(ac'bCB')' = ABC'b'ca'
-> ABCb'ca'
-> ABC(b'ca')' = ABCac'b
-> ABCa(c'b)' = ABCab'c
-> ABCabc

There's probably a shorter way, but this is still just a constant number of operations, so it takes only linear time. One could use a more sophisticated algorithm here to implement some of the cyclic shifts, but that's just an optimization.

Now we can solve the two partitions of our array recursively and we're done.

The question remains, what would be a nice m that allows us to solve the left part easily?

To figure this out, we need to realize that what we want to implement is a particular permutation P of the array indices. Every permutation can be decomposed into a set of cycles a0 -> a1 -> ... -> a{k-1} -> a0, for which we have P(ai) = a{(i + 1) % k}. It is easy to process such a cycle in-place, the algorithm is outlined on Wikipedia.

Now the problem is that after you completed processing one of the cycle, to find an element that is part of a cycle you have not yet processed. There is no generic solution for this, but for some particular permutations there are nice formulas that describe what exactly the positions are that are part of the different cycles.

For your problems, you just choose m = (5^(2k) - 1)/3, such that m < n and k is maximum. A sequence of elements that are part of all the different cycles is 5^0, 5^1, ..., 5^{k-1}. You can use those to implement the cycle-leader algorithm on the left part of the array (after the shifting) in O(m).

We solve the leftover right part recursively and get an algorithm to solve the problem in time

T(n) = O(m) + T(n - m)

and since m >= Omega(n), we get T(n) = O(n).

How to flip rows in a 1D short/int array representing a 2D array in Java

You have a physical 1D array representing a logical 2D array, and you want to swap rows. You can do this partly by mapping 2D array indices into a 1D array index.

Let height be the number of rows, and width be the number of columns.

for ( int i = 0; i < height/2; ++i ) {
    int k = height - 1 - i;
    for ( int j = 0; j < width; ++j ) {
        short temp = array[i * width + j];
        array[i * width + j] = array[k * width + j];
        array[k * width + j] = temp;
    }
}    

I've written this for readability. You or the compiler may optimize some of the repeated computations.

You might be able to optimize further by using a 2D array, which would allow you to swap references to rows in O(height), rather than copying all the rows in O(height * width).

Rearrange sparse arrays by swapping rows and columns

CSC format keeps a list of the row indices of all non-zero entries, CSR format keeps a list of the column indices of all non-zero entries. I think you can take advantage of that to swap things around as follows, and I think there shouldn't be any side-effects to it:

def swap_rows(mat, a, b) :
    mat_csc = scipy.sparse.csc_matrix(mat)
    a_idx = np.where(mat_csc.indices == a)
    b_idx = np.where(mat_csc.indices == b)
    mat_csc.indices[a_idx] = b
    mat_csc.indices[b_idx] = a
    return mat_csc.asformat(mat.format)

def swap_cols(mat, a, b) :
    mat_csr = scipy.sparse.csr_matrix(mat)
    a_idx = np.where(mat_csr.indices == a)
    b_idx = np.where(mat_csr.indices == b)
    mat_csr.indices[a_idx] = b
    mat_csr.indices[b_idx] = a
    return mat_csr.asformat(mat.format)

You could now do something like this:

>>> mat = np.zeros((5,5))
>>> mat[[1, 2, 3, 3], [0, 2, 2, 4]] = 1
>>> mat = scipy.sparse.lil_matrix(mat)
>>> mat.todense()
matrix([[ 0.,  0.,  0.,  0.,  0.],
        [ 1.,  0.,  0.,  0.,  0.],
        [ 0.,  0.,  1.,  0.,  0.],
        [ 0.,  0.,  1.,  0.,  1.],
        [ 0.,  0.,  0.,  0.,  0.]])
>>> swap_rows(mat, 1, 3)
<5x5 sparse matrix of type '<type 'numpy.float64'>'
    with 4 stored elements in LInked List format>
>>> swap_rows(mat, 1, 3).todense()
matrix([[ 0.,  0.,  0.,  0.,  0.],
        [ 0.,  0.,  1.,  0.,  1.],
        [ 0.,  0.,  1.,  0.,  0.],
        [ 1.,  0.,  0.,  0.,  0.],
        [ 0.,  0.,  0.,  0.,  0.]])
>>> swap_cols(mat, 0, 4)
<5x5 sparse matrix of type '<type 'numpy.float64'>'
    with 4 stored elements in LInked List format>
>>> swap_cols(mat, 0, 4).todense()
matrix([[ 0.,  0.,  0.,  0.,  0.],
        [ 0.,  0.,  0.,  0.,  1.],
        [ 0.,  0.,  1.,  0.,  0.],
        [ 1.,  0.,  1.,  0.,  0.],
        [ 0.,  0.,  0.,  0.,  0.]])

I have used a LIL matrix to show how you could preserve the type of your output. In your application you probably want to already be in CSC or CSR format, and select whether to swap rows or columns first based on it, to minimize conversions.

In-place transposition of a matrix

Inspired by the Wikipedia - Following the cycles algorithm description, I came up with following C++ implementation:

#include <iostream>  // std::cout
#include <iterator>  // std::ostream_iterator
#include <algorithm> // std::swap (until C++11)
#include <vector>

template<class RandomIterator>
void transpose(RandomIterator first, RandomIterator last, int m)
{
    const int mn1 = (last - first - 1);
    const int n   = (last - first) / m;
    std::vector<bool> visited(last - first);
    RandomIterator cycle = first;
    while (++cycle != last) {
        if (visited[cycle - first])
            continue;
        int a = cycle - first;
        do  {
            a = a == mn1 ? mn1 : (n * a) % mn1;
            std::swap(*(first + a), *cycle);
            visited[a] = true;
        } while ((first + a) != cycle);
    }
}

int main()
{
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
    transpose(a, a + 8, 4);
    std::copy(a, a + 8, std::ostream_iterator<int>(std::cout, " "));
}

The program makes the in-place matrix transposition of the 2 × 4 matrix

0 1 2 3
4 5 6 7

represented in row-major ordering {0, 1, 2, 3, 4, 5, 6, 7} into the 4 × 2 matrix

0 4
1 5
2 6
3 7

represented by the row-major ordering {0, 4, 1, 5, 2, 6, 3, 7}.

The argument m of transpose represents the rowsize, the columnsize n is determined by the rowsize and the sequence size. The algorithm needs m × n bits of auxiliary storage to store the information, which elements have been swapped. The indexes of the sequence are mapped with the following scheme:

0 → 0
1 → 2
2 → 4
3 → 6
4 → 1
5 → 3
6 → 5
7 → 7

The mapping function in general is:

idx → (idx × n) mod (m × n - 1) if idx < (m × n), idx → idx otherwise

We can identify four cycles within this sequence: { 0 }, { 1, 2, 4 }, {3, 5, 6} and { 7 }. Each cycle can be transposed independent of the other cycles. The variable cycle initially points to the second element (the first does not need to be moved because 0 → 0). The bit-array visited holds the already transposed elements and indicates, that index 1 (the second element) needs to be moved. Index 1 gets swapped with index 2 (mapping function). Now index 1 holds the element of index 2 and this element gets swapped with the element of index 4. Now index 1 holds the element of index 4. The element of index 4 should go to index 1, it is in the right place, transposing of the cycle has finished, all touched indexes have been marked visited. The variable cycle gets incremented till the first not visited index, which is 3. The procedure continues with this cycle till all cycles have been transposed.

change values in array when doing foreach

The callback is passed the element, the index, and the array itself.

arr.forEach(function(part, index, theArray) {
  theArray[index] = "hello world";
});

edit — as noted in a comment, the .forEach() function can take a second argument, which will be used as the value of this in each call to the callback:

arr.forEach(function(part, index) {
  this[index] = "hello world";
}, arr); // use arr as this

That second example shows arr itself being set up as this in the callback.One might think that the array involved in the .forEach() call might be the default value of this, but for whatever reason it's not; this will be undefined if that second argument is not provided.

(Note: the above stuff about this does not apply if the callback is a => function, because this is never bound to anything when such functions are invoked.)

Also it's important to remember that there is a whole family of similar utilities provided on the Array prototype, and many questions pop up on Stackoverflow about one function or another such that the best solution is to simply pick a different tool. You've got:

• forEach for doing a thing with or to every entry in an array;
• filter for producing a new array containing only qualifying entries;
• map for making a one-to-one new array by transforming an existing array;
• some to check whether at least one element in an array fits some description;
• every to check whether all entries in an array match a description;
• find to look for a value in an array

and so on. MDN link

Swap rows with columns (transposition) of a matrix in javascript

See article: Transpose An Array In JavaScript and jQuery

function transpose(a) {
  // Calculate the width and height of the Array  var w = a.length || 0;  var h = a[0] instanceof Array ? a[0].length : 0;
  // In case it is a zero matrix, no transpose routine needed.  if(h === 0 || w === 0) { return []; }
  /**   * @var {Number} i Counter   * @var {Number} j Counter   * @var {Array} t Transposed data is stored in this array.   */  var i, j, t = [];
  // Loop through every item in the outer array (height)  for(i=0; i<h; i++) {
    // Insert a new row (array)    t[i] = [];
    // Loop through every item per item in outer array (width)    for(j=0; j<w; j++) {
      // Save transposed data.      t[i][j] = a[j][i];    }  }
  return t;}
console.log(transpose([[1,2,3],[4,5,6],[7,8,9]]));

---

Related Topics