Вставьте элемент в массив numpy и получите все свернутые перестановки

Question

Есть ли лучший способ вставлять один за другим элементы в массиве
во все возможные позиции (n + 1 позиций) .

Например, вставка [1][6 7 8 9] должно выдать:

[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]

Так что, если я вставлю A = [1 2 3] один за другим в B = [6 7 8 9], то получится:

[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]
--------------------

В настоящее время яиспользуйте numpy.roll вот так:

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

Answer 1

То, что вы просите здесь, известно как матрица Теплица , которая:

матрица, в которой каждая нисходящая диагональ слева направо является постоянной

К счастью для вас, scipy имеет простую в использовании реализацию этого:

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]])

Векторизованный способ масштабирования этого решения:

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]]])

Answer 2

2D Дело

Мы можем использовать np.lib.stride_tricks.as_strided на основе scikit-image's view_as_windows, чтобы получить раздвижные окна. Подробнее об использовании as_strided на основе view_as_windows.

Идея состоит в том, чтобы дополнить двумя копиями массива 1D вместе с новым добавляемым значением (в данном случае 1), а затем получить 2D представление о нем. Будучи представлением, это было бы очень эффективно и выглядело бы примерно так -

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]

Мы можем добиться некоторого незначительного улучшения при прямом использовании np.lib.stride_tricks.as_strided, чтобы избежать этой переворачивающейся части: [::-1], но читателям может быть сложно выполнить настройку.

Пробный прогон -

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]])

Время (также для демонстрации эффективности) на очень большом массиве -

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 Кейс

Расширение до 3D требует некоторых дополнительных шагов, но оно того стоит, поскольку мы все еще можем сохранять вывод в виде просмотра и, следовательно, практически свободны от времени (снова направляемся на юг!) -

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]

Пробный прогон -

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]]])

Время снова для очень большого массива -

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

Производительность будет пропорциональна длине добавляемого массива. Таким образом, для добавления массива 1000 элементов во входной массив длиной 10000 было бы -

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

Answer 3

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)