Блог

Я пытаюсь выяснить, как создать матрицу nxn со значениями в диапазоне от 0 до n ^ 2. В строке и столбце не должно быть последовательности, за исключением n < 5.

Вот пример ожидаемого вывода:

 array([[ 8, 13, 39,  1, 22, 37,  2],
       [ 6, 26, 36,  3, 29, 35, 16],
       [18, 20, 46, 28, 15, 12, 43],
       [ 7, 24, 14, 41, 32, 21, 27],
       [34, 31,  9, 44, 30, 48, 45],
       [11, 33, 40, 10, 38,  0,  5],
       [17, 23,  4, 19, 25, 47, 42]])
  

Создайте свои значения, выберите случайным образом без замены (или используйте shuffle) и измените форму массива.

 import numpy as np

# dimension
n = 5
values = np.arange(0, n**2)

# randomly selected (or use shuffle)
selected = np.random.choice(values, size = n * n, replace = False)

# reshape array to matrix
matrix = np.reshape(selected, (n, n))

array([[21,  5, 12, 23,  4],
       [13, 10, 19, 22, 20],
       [ 7,  2, 15, 18, 17],
       [ 0, 16,  6,  8, 24],
       [11,  1,  9, 14,  3]])
  

Это возможное решение:

 import random
import pprint

number_rows_columns = 5
number_list = [i for i in range(number_rows_columns**2)]

final_matrix = []
for row in range(number_rows_columns):
    new_column = []
    for column in range(number_rows_columns):
        new_column.append(random.choice(number_list))
        number_list.remove(new_column[-1])
    final_matrix.append(new_column)
pprint.pprint(final_matrix)
  

Пример вывода этого кода:

 [[6, 13, 10, 20, 24],
 [2, 14, 16, 21, 19],
 [0, 8, 17, 15, 5],
 [3, 18, 7, 12, 23],
 [22, 1, 4, 9, 11]]
  

ОБНОВЛЕНИЕ: чтобы устранить проблему «последовательности», это возможное решение:

 import random
import pprint

number_rows_columns = 20
matrix_is_valid = False

def fill_matrix():
    number_list = [i for i in range(number_rows_columns**2)]
    matrix = []
    for row in range(number_rows_columns):
        new_column = []
        for column in range(number_rows_columns):
            new_column.append(random.choice(number_list))
            number_list.remove(new_column[-1])
        matrix.append(new_column)
    return matrix

def check_rows(matrix):
    global matrix_is_valid
    for row in matrix:
        for index, element in enumerate(row[:-1]):
            if abs(element - row[index   1]) == 1:
                matrix_is_valid = False
                return

def check_matrix(matrix):
    global matrix_is_valid
    matrix_is_valid = True
    check_rows(matrix)
    if not matrix_is_valid:
        return
    matrix = list(list(a) for a in zip(*matrix))
    check_rows(matrix)


while not matrix_is_valid:
    final_matrix = fill_matrix()
    check_matrix(final_matrix)

pprint.pprint(final_matrix)
  

ВАЖНО: я хотел бы указать, что это неэффективное решение. В основном этот алгоритм создает матрицу, проверяет, что в каждой строке и столбце (путем транспозиции) нет «последовательности» чисел, и, если они есть, создает новую матрицу и проверяет ее, пока не получит действительную.
Это алгоритм, который имеет среднюю временную сложность O((n 1)!) , см. Bogosort для углубления.

ОБНОВЛЕНИЕ УЛУЧШЕННОЙ ВЕРСИИ: эта улучшенная версия проверяет правильность каждой вставки чисел, поэтому матрицу необходимо перестраивать с нуля, только если и когда последнее число не может быть введено

Код:

 import random
import pprint

number_rows_columns = 12
matrix_is_valid = False
counter = 0

def fill_matrix():
    global matrix_is_valid
    matrix_is_valid = True
    number_list = [i for i in range(number_rows_columns**2)]
    matrix = []
    for row in range(number_rows_columns):
        new_column = []
        for column in range(number_rows_columns):
            new_column.append(random.choice(number_list))
            if (column > 0 or row > 0) and len(number_list) > 1:
                invalid_value = True
                if column != 0 and row != 0:
                    while abs(new_column[-1] - new_column[-2]) == 1 or abs(new_column[-1] - matrix[-1][column]) == 1:
                        new_column[-1] = random.choice(number_list)
                elif column != 0 and row == 0:
                    while abs(new_column[-1] - new_column[-2]) == 1:
                        new_column[-1] = random.choice(number_list)
                elif column == 0 and row != 0:
                    while abs(new_column[-1] - matrix[-1][column]) == 1:
                        new_column[-1] = random.choice(number_list)
            number_list.remove(new_column[-1])
        matrix.append(new_column)
    if abs(matrix[-1][-1] - matrix[-1][-2]) == 1 or abs(matrix[-1][-1] - matrix[-2][-1]) == 1:
        matrix_is_valid = False
    return matrix


while not matrix_is_valid:
    final_matrix = fill_matrix()

pprint.pprint(final_matrix)