Как сгенерировать все возможные векторы размера k в матрице (включая диагонали)? - PullRequest
Новая
       35

Как сгенерировать все возможные векторы размера k в матрице (включая диагонали)?

0 голосов
/ 11 июня 2019

Учитывая эту матрицу: 

x = [[1,2,3,4,5], [1,2,3,4,5], [1,2,3,4,5], [1,2,3,4,5], [1,2,3,4,5], [1,2,3,4,5]]

Какой эффективный способ вернуть все возможные векторы 4 на 1 и матрицу 1 на 4 в этой матрице.Как и любые 4 диагональных пробела, соединенных в линию.

Например: [1,1,1,1] появится 3 раза

Диагонали также должны быть адресованы, поэтому [1,2,3,4] будет включен в строкуно и диагональ.

1 Ответ

1 голос
/ 11 июня 2019

Разделение задачи на два этапа:

Шаг 1 - получить все горизонтальные, вертикальные и диагональные линии

Диагонали решаются с использованием того факта, что i+j, или соответственно i-j, является постоянной величиной для индексов i, j

x = [[1,2,3,4,5], [1,2,3,4,5], [1,2,3,4,5], [1,2,3,4,5], [1,2,3,4,5], [1,2,3,4,5]]

pprint.pprint(x)

# [[1, 2, 3, 4, 5],
# [1, 2, 3, 4, 5],
# [1, 2, 3, 4, 5],
# [1, 2, 3, 4, 5],
# [1, 2, 3, 4, 5],
# [1, 2, 3, 4, 5]]

all_lines = (
    # Horizontal
    [x[i] for i in range(len(x))] +
    # Vertical
    [[x[i][j] for i in range(len(x))] for j in range(len(x[0]))] +
    # Diagonal k = i - j
    [[x[k+j][j] for j in range(len(x[0])) if 0 <= k+j < len(x)] for k in range(-len(x[0])+1, len(x))] +
    # Diagonal k = i + j
    [[x[k-j][j] for j in range(len(x[0])) if 0 <= k-j < len(x)] for k in range(len(x[0])+len(x)-1)]
)

>>> pprint.pprint(all_lines)
[[1, 2, 3, 4, 5],
 [1, 2, 3, 4, 5],
 [1, 2, 3, 4, 5],
 [1, 2, 3, 4, 5],
 [1, 2, 3, 4, 5],
 [1, 2, 3, 4, 5],
 [1, 1, 1, 1, 1, 1],
 [2, 2, 2, 2, 2, 2],
 [3, 3, 3, 3, 3, 3],
 [4, 4, 4, 4, 4, 4],
 [5, 5, 5, 5, 5, 5],
 [5],
 [4, 5],
 [3, 4, 5],
 [2, 3, 4, 5],
 [1, 2, 3, 4, 5],
 [1, 2, 3, 4, 5],
 [1, 2, 3, 4],
 [1, 2, 3],
 [1, 2],
 [1],
 [1],
 [1, 2],
 [1, 2, 3],
 [1, 2, 3, 4],
 [1, 2, 3, 4, 5],
 [1, 2, 3, 4, 5],
 [2, 3, 4, 5],
 [3, 4, 5],
 [4, 5],
 [5]]

Шаг 2 - для каждой строки выберите каждый срез длиной 4 

ans = [a[i:i+4] for i in range(len(a)-4+1) for a in all_lines if len(a[i:i+4]) == 4]

>>> ans = [a[i:i+4] for i in range(len(a)-4+1) for a in all_lines if len(a[i:i+4]) == 4]
>>> pprint.pprint(ans)
[[1, 2, 3, 4],
 [1, 2, 3, 4],
 [1, 2, 3, 4],
 [1, 2, 3, 4],
 [1, 2, 3, 4],
 [1, 2, 3, 4],
 [1, 1, 1, 1],
 [2, 2, 2, 2],
 [3, 3, 3, 3],
 [4, 4, 4, 4],
 [5, 5, 5, 5],
 [2, 3, 4, 5],
 [1, 2, 3, 4],
 [1, 2, 3, 4],
 [1, 2, 3, 4],
 [1, 2, 3, 4],
 [1, 2, 3, 4],
 [1, 2, 3, 4],
 [2, 3, 4, 5],
 [2, 3, 4, 5],
 [2, 3, 4, 5],
 [2, 3, 4, 5],
 [2, 3, 4, 5],
 [2, 3, 4, 5],
 [2, 3, 4, 5],
 [1, 1, 1, 1],
 [2, 2, 2, 2],
 [3, 3, 3, 3],
 [4, 4, 4, 4],
 [5, 5, 5, 5],
 [2, 3, 4, 5],
 [2, 3, 4, 5],
 [2, 3, 4, 5],
 [2, 3, 4, 5],
 [1, 1, 1, 1],
 [2, 2, 2, 2],
 [3, 3, 3, 3],
 [4, 4, 4, 4],
 [5, 5, 5, 5]]

Может быть, не самый эффективный, но это по крайней мере способ сделать это. Вероятно, найдется способ использовать itertools combinations, чтобы значительно упростить это.

...