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
– hpaulj, Commented Sep 6, 2018 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
– Jonas Wolff, Commented Sep 6, 2018 at 18:17
You're not so much inserting at every possible position, but instead inserting at the beginning then rolling your list. — user3483203
– user3483203, Commented Sep 6, 2018 at 18:18
@user3483203 yes thats right... but I will do whatever is faster. — Panos Kalatzantonakis
– Panos Kalatzantonakis, Commented Sep 6, 2018 at 18:21
@JonasWolff your solution was very good why did you deleted it? — Panos Kalatzantonakis
– Panos Kalatzantonakis, Commented Sep 6, 2018 at 18:33

user3483203 · Accepted Answer · 2018-09-06 19:01:40Z

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 · Accepted Answer · 2018-09-06 19:15:39Z

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

Jonas Wolff · Accepted Answer · 2018-09-06 18:22:10Z

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 6, 2018 at 18:22

Jonas Wolff

2,2941 gold badge14 silver badges17 bronze badges

Collectives™ on Stack Overflow

Insert element into numpy array and get all rolled permutations

3 Answers 3

Vectorized way to scale this solution:

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Vectorized way to scale this solution:

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related