Insert element into numpy array and get all rolled permutations

Question

Is there a better way to insert, one by one, elements in an array
to all posible positions (n+1 positions).

E.g inserting [1] to [6 7 8 9] should produce:

[1 6 7 8 9]
[9 1 6 7 8]
[8 9 1 6 7]
[7 8 9 1 6]
[6 7 8 9 1]

So if I insert A = [1 2 3] one by one to B = [6 7 8 9] it should produce:

[1 6 7 8 9]
[9 1 6 7 8]
[8 9 1 6 7]
[7 8 9 1 6]
[6 7 8 9 1]
--------------------
[2 6 7 8 9]
[9 2 6 7 8]
[8 9 2 6 7]
[7 8 9 2 6]
[6 7 8 9 2]
--------------------
[3 6 7 8 9]
[9 3 6 7 8]
[8 9 3 6 7]
[7 8 9 3 6]
[6 7 8 9 3]
--------------------

Currently I use numpy.roll like this:

import numpy as np
import timeit

A = np.array([1, 2, 3, 4, 5])
B = np.array([6, 7, 8, 9])

def inject_one(Ad, Bd):
    for i, _ in enumerate(Ad):
        C = np.append(Ad[i], Bd)
        for _ in range(len(C) - 1):
            C = np.roll(C, 1)

t = timeit.Timer(lambda: inject_one(A, B))
print("{:.3f}secs for 1000 iterations".format(t.timeit(number=1000))) 
# > 0.160 secs

`np.append` is just a front end to `np.concatenate`; it isn't a list `append` clone. As such, it isn't efficient when applied repeatedly in a loop. — hpaulj, Sep 06 '18 at 18:17
if your problem is scrolling the list so the last number come first you can you write outa = list[-1]+list[:-1] — Jonas Wolff, Sep 06 '18 at 18:17
You're not so much inserting at every possible position, but instead inserting at the beginning then rolling your list. — user3483203, Sep 06 '18 at 18:18
@user3483203 yes thats right... but I will do whatever is faster. — Panos Kalatzantonakis, Sep 06 '18 at 18:21
@JonasWolff your solution was very good why did you deleted it? — Panos Kalatzantonakis, Sep 06 '18 at 18:33
my usual experience with numpy and scipy is that if they have a solution, they will do it lightyears faster than their counter part, so i deleted my post when i saw you already had one. BTW i reuploaded it now ;) — Jonas Wolff, Sep 06 '18 at 18:38

user3483203 · Accepted Answer · 2018-09-06T19:01:40.037

What you're asking for here is known as a Toeplitz Matrix, which is:

a matrix in which each descending diagonal from left to right is constant

Luckily for you, scipy has an easy to use implementation of this:

from scipy.linalg import toeplitz

def magic_toeplitz(arr, to_add):
    return toeplitz(np.hstack([to_add, arr[::-1]]), np.hstack([to_add, arr]))

a = [6,7,8,9]
add = [1]
magic_toeplitz(a, add)

array([[1, 6, 7, 8, 9],
       [9, 1, 6, 7, 8],
       [8, 9, 1, 6, 7],
       [7, 8, 9, 1, 6],
       [6, 7, 8, 9, 1]])

Vectorized way to scale this solution:

A = np.array([1, 2, 3, 4, 5])
B = np.array([6, 7, 8, 9])

out = toeplitz(np.hstack([[np.nan], B[::-1]]), np.hstack([np.nan, B]))
out = np.tile(out, (len(A), 1, 1))
m = np.ma.array(out, mask=np.isnan(out))
vals = np.repeat(A, (B.shape[0] + 1)**2).reshape(out.shape)
print(m.filled(vals))

array([[[1, 6, 7, 8, 9],
        [9, 1, 6, 7, 8],
        [8, 9, 1, 6, 7],
        [7, 8, 9, 1, 6],
        [6, 7, 8, 9, 1]],

       [[2, 6, 7, 8, 9],
        [9, 2, 6, 7, 8],
        [8, 9, 2, 6, 7],
        [7, 8, 9, 2, 6],
        [6, 7, 8, 9, 2]],

       [[3, 6, 7, 8, 9],
        [9, 3, 6, 7, 8],
        [8, 9, 3, 6, 7],
        [7, 8, 9, 3, 6],
        [6, 7, 8, 9, 3]],

       [[4, 6, 7, 8, 9],
        [9, 4, 6, 7, 8],
        [8, 9, 4, 6, 7],
        [7, 8, 9, 4, 6],
        [6, 7, 8, 9, 4]],

       [[5, 6, 7, 8, 9],
        [9, 5, 6, 7, 8],
        [8, 9, 5, 6, 7],
        [7, 8, 9, 5, 6],
        [6, 7, 8, 9, 5]]])

Divakar · Answer 2 · 2018-09-06T19:15:39.663

2D Case

We can leverage np.lib.stride_tricks.as_strided based scikit-image's view_as_windows to get sliding windows. More info on use of as_strided based view_as_windows.

The idea is to pad with two copies of the 1D array alongwith the new value to be added (1 in this case) and then get 2D view into it. Being a view, it would be very efficient and would look something like this -

from skimage.util.shape import view_as_windows

def rolling_add(a,val=1):
    a_ext = np.r_[a,val,a]
    return view_as_windows(a_ext,len(a)+1,1)[::-1]

We can gain some marginal improvement with a direct usage of np.lib.stride_tricks.as_strided to avoid that flipping part : [::-1], but the setup might be difficult to follow for the readers.

Sample run -

In [254]: a = np.array([6, 7, 8, 9])

In [255]: rolling_add(a)
Out[255]: 
array([[1, 6, 7, 8, 9],
       [9, 1, 6, 7, 8],
       [8, 9, 1, 6, 7],
       [7, 8, 9, 1, 6],
       [6, 7, 8, 9, 1]])

Timings (also to showcase the efficiency part) on very large array -

In [263]: a = np.random.randint(0,10,10000)

In [264]: %timeit rolling_add(a)
10000 loops, best of 3: 58 µs per loop

3D Case

Extending to 3D requires some additional steps, but it's worth it as we can still keep the output as a view and hence virtually free on timings (head down south again!) -

def rolling_add3D(a,add_ar):
    a_ext = np.r_[a,0,a]
    a_ext2 = np.repeat(a_ext[None],len(add_ar),0)
    a_ext2[:,len(a)] = add_ar
    return view_as_windows(a_ext2,(1,len(a)+1))[...,0,:][:,::-1]

Sample run -

In [292]: a
Out[292]: array([6, 7, 8, 9])

In [293]: rolling_add3D(a,[1,2,3])
Out[293]: 
array([[[1, 6, 7, 8, 9],
        [9, 1, 6, 7, 8],
        [8, 9, 1, 6, 7],
        [7, 8, 9, 1, 6],
        [6, 7, 8, 9, 1]],

       [[2, 6, 7, 8, 9],
        [9, 2, 6, 7, 8],
        [8, 9, 2, 6, 7],
        [7, 8, 9, 2, 6],
        [6, 7, 8, 9, 2]],

       [[3, 6, 7, 8, 9],
        [9, 3, 6, 7, 8],
        [8, 9, 3, 6, 7],
        [7, 8, 9, 3, 6],
        [6, 7, 8, 9, 3]]])

Timings on again very large array -

In [294]: a = np.random.randint(0,10,10000)

In [295]: %timeit rolling_add3D(a,[1,2,3])
10000 loops, best of 3: 83.7 µs per loop

The performance would be proportional to the length of array to be added. So, to add a 1000 elements array into an 10000 length input array would be -

In [301]: a = np.random.randint(0,10,10000)

In [302]: add_array = np.random.randint(0,10,1000)

In [303]: %timeit rolling_add3D(a,add_array)
100 loops, best of 3: 16.9 ms per loop

score 2 · Answer 3 · answered Sep 06 '18 at 18:22

2

for i in A:
   new_list = B[:]
   new_list.append(i)
   print(new_list)
   for q in B:
        new_list = [new_list[-1]]+new_list[:-1]
        print(new_list)
   print("-"*15)

answered Sep 06 '18 at 18:22

Jonas Wolff

2,034
1
12
17

Insert element into numpy array and get all rolled permutations

3 Answers3

Vectorized way to scale this solution: