Создание программы на латинском квадрате в python

Question

order=input('Input the order of a Latin Square: ')
top_left=input('Input the top-left number: ')
int_order=int(order)
int_top_left=int(top_left)
for order in range(int_order):
    for top_left in range(int_order):
        print(int_top_left, end = ' ')
    print()

Итак, я пытаюсь ввести порядок, затем верхнюю левую сумму и создать оттуда латинский квадрат, проблема в том, что я не знаю, как заставить его считать в строках и столбцах, эта программа размещает только верхнюю левую число в квадратной сетке с размером порядка x порядка. Любая помощь приветствуется.

Answer 1

Ключевая идея состоит в том, что вы можете создать действительную строку и повернуть строку, чтобы создать правильный квадрат:

def create_latin_square(n: int):
    row = [i for i in range(1, n+1)]
    return [row[i:] + row[:i] for i in range(n)]

Квадрат 4 размера выглядит так:

[1, 2, 3, 4]  # row
[2, 3, 4, 1]  # row, rotated by 1 to the left
[3, 4, 1, 2]  # row, rotated by 2 to the left
[4, 1, 2, 3]  # row, rotated by 3 to the left

Затем просто поверните первую строку:

def create_latin_square(n: int, start_el: int=1):
    row = [i for i in range(1, n+1)]
    row = row[start_el-1:] + row[:start_el-1]
    return [row[i:] + row[:i] for i in range(n)]

Answer 2

Латинский квадрат - это NP-полная проблема (см. http://en.wikipedia.org/wiki/Latin_square), как и в судоку, только с некоторыми снятыми ограничениями.

Вам нужно (как-то) искать пространство латинских квадратов заданного порядка. У вас есть несколько возможностей:

1. Ручной поиск в пространстве состояний

Вы можете написать решатель Латинского квадрата самостоятельно, используя некоторые методы поиска в пространстве состояний. Ваше начальное состояние будет латинским квадратом со всеми полями, кроме верхнего левого поля. Чем вы можете посмотреть на одно поле за раз и попытаться установить его в число, удовлетворяющее ограничениям. Если есть, перейдите к следующему полю, иначе вернитесь к родительскому состоянию.

Вы можете найти огромное количество ресурсов по поиску в пространстве состояний онлайн. Поиск по ключевым словам, таким как: возвратный путь, DFS, BFS, ветвление и привязка, A *

2. Преобразовать в другую комбинаторную задачу и использовать существующий решатель

Вы можете преобразовать эту проблему в другую, хорошо изученную проблему комбинаторной оптимизации и использовать для ее решения решатель.

Эта проблема может быть выражена как раскраска графа - вы можете преобразовать ее в задачу раскраски графа следующим образом:

1. Каждое поле в квадрате - это один узел на графике, каждое число в квадрате - один цвет.
2. Между двумя узлами есть грань, если они находятся в одной строке или столбце.
3. После того, как раскраска решена, вы заменяете цвета числами.

На самом деле, латинский квадрат (более или менее) - это раскраска графа, только с использованием другой терминологии:).

Раскраска графика может быть решена с помощью решателей CSP (Constraint Satisfaction Programming), или вы можете подключить свою проблему непосредственно к CSP.

Вы можете решить это, используя ILP (Integer Linear Programming). Для этого есть настроенные решатели. GLPK является открытым исходным кодом, и для него есть привязки к Python (например, PyGLPK)

3. Используйте метаэвристический подход

Если вы выясните способ выражения ошибки для некоторого квадрата, заполненного некоторыми числами (например, количеством нарушений ограничений, т.е. количеством пар одинаковых чисел в одной строке или столбце), вы можете использовать некоторую стохастическую метаэвристику, например, Simmulated. Отжиг или эволюционные алгоритмы для использования этой функции ошибок, чтобы привести решения к действительному.

Answer 3

Что насчет этого?

def latin_square(n, mod='ballanced'):
  import numpy as np

  mat = np.empty((n,n,))*np.nan

  mat[:,0] = range(1,n+1)

  if mod=='ballanced':
    shift = (.5-np.mod(np.array(range(1,n)),2))/.5*np.ceil(np.array(range(1,n))/2)
    shift = shift.astype(int)
  elif mod=='normal':
    shift = np.array(range(n-1, -1, -1))

  for col in range(1, n):
    mat[:, col] = np.roll(mat[:,0], shift[col-1])
    
  return(mat)


latin_square(6)

array([[1., 2., 6., 3., 5., 4.],
   [2., 3., 1., 4., 6., 5.],
   [3., 4., 2., 5., 1., 6.],
   [4., 5., 3., 6., 2., 1.],
   [5., 6., 4., 1., 3., 2.],
   [6., 1., 5., 2., 4., 3.]])

Answer 4

Вы можете использовать подход Якобсона и П. Мэтьюса.

MT Jacobson и P. Matthews, Генерирование равномерно распределенных случайных латинских квадратов, J. Combinatorial Design 4 (1996), 405-437

Посмотри.

Answer 5

#Highest number in square
order_of_sq = int(input("Enter order of sq: "))

#Number you want to start the square with
top_left = int(input("Enter top left number: "))

#Sets a placeholder for a variable called top_left_init
top_left_init=0

#Sets the initial value of top_left to a new variable because the code will change the value of top left later on 
top_left_init += top_left

#Initialize the value of count
count = 0

#Add 1 to the highest value in latin square to account for the range function (the ending number is always one less than the number you enter into the range function)
for values in range (1,order_of_sq+1):

    #Prevents the program from adding too many characters to the line
    while count != order_of_sq:

        #Prints numbers with spaces after them in a horizontal manner
        print(top_left,sep=' ',end=' ')

        #Adds 1 to the top_left
        top_left += 1

        #Count is used to keep track of how many characters are in your line
        count+=1

        #Restarts the numbers in your line when you reach the highest number
        if top_left == order_of_sq+1:
            top_left = 1

    #Creates a new row
    print()
    count = 0

    #Calls the initial value of top_left and adds 1 to it before beginning the next row
    top_left_init += 1

    #Resets top_left_init to 1 if it reaches the highest number in the square
    if top_left_init == order_of_sq + 1:
        top_left_init = 1
        top_left = top_left_init
    else:
        top_left = top_left_init

главный()