Minimum amount of numbers to change inside of n*n matrix to make it symmetrical about multiple lines-CodePudding

There is a n*n matrix made of numbers 0 - 9. For example:

6 0 0 8 9 6 1 
5 1 6 8 1 1 0 
4 2 1 3 7 1 5 
8 8 6 6 2 5 2 
7 9 4 6 9 6 4 
1 4 7 8 5 3 8 
9 4 8 3 9 2 9

I need to find the minimum amount of numbers to change (inside the matrix) to make it symmetrical about multiple lines (/, \, -, |) at once.

I made four functions for every symmetry (/, \, -, |). They make lists of two numbers that need to have the same value. The functions look like this:

import math
"""lenght = how many numbers in one line"""

def symmetry_horizontaln(lenght):
    for i in range(math.ceil(lenght/2)):
        for j in range(lenght):
            round_result = []
            round_result.append((i, j))
            round_result.append((lenght-i-1, j))

def symmetry_vertical(lenght):
    for i in range(lenght):
        for j in range(lenght):
            if j < math.ceil(lenght/2):
                round_result= []
                round_result.append((i, j))
                round_result.append((i, lenght-j-1))
    
def symmetry_main_diagonal(lenght):
    for i in range(lenght):
        for j in range(lenght):
            if j <= i:
                   round_result= []
                   round_result.append((i, j))
                   round_result.append((j, i))

def symmetry_second_diagonal(lenght): 
    for i in range(lenght):
        for j in range(lenght):
            if j <= lenght-i-1:
                   round_result= []
                   round_result.append((i, j))
                   round_result.append((lenght-j-1, lenght-i-1))

Now i need to somehow put the round results together so i get lists of points in the matrix that need to have the same value. For example if there is a matrix like this:

6 0 0 8 9 6 1 
5 1 6 8 1 1 0 
4 2 1 3 7 1 5 
8 8 6 6 2 5 2 
7 9 4 6 9 6 4 
1 4 7 8 5 3 8 
9 4 8 3 9 2 9

and it needs to be symatrical about these lines: - and /, the final list would look like this:

[[(6, 2), (4, 0), (0, 4), (4, 6), (2, 0), (6, 4), (0, 2), (2, 6)], [(2, 3), (3, 2), (3, 4), (4, 3)], [(3, 1), (5, 3), (1, 3), (3, 5)], [(1, 2), (2, 1), (5, 4), (1, 4), (4, 5), (2, 5), (4, 1), (5, 2)], [(1, 1), (5, 5), (5, 1), (1, 5)], [(0, 1), (6, 5), (6, 1), (5, 0), (5, 6), (0, 5), (1, 0), (1, 6)], [(4, 4), (2, 4), (4, 2), (2, 2)], [(6, 3), (0, 3), (3, 6), (3, 0)], [(3, 3)], [(6, 6), (6, 0), (0, 6), (0, 0)]]

from this list i know how to get the minimum amount of numbers to change to make i symmetrical about those lines. I think its 30. But i have no idea how to get that list.

This is what i tried:

I modified the previous functions like this (last two lines in every function are new):

def symmetry_horizontaln(lenght):
    for i in range(math.ceil(lenght/2)):
        for j in range(lenght):
            round_result = []
            round_result.append((i, j))
            round_result.append((lenght-i-1, j))
              
            function((i, j), round_result)
            function((delka-i-1, j), round_result)

def symetry_horizontal(lenght):
    ...
    function((i, j), round_result)
    function((i, lenght-j-1), round_result)

...

and made a new function to get the final list:

x = []

def function(point, round_result):
    if round_result[0] == round_result[1]:
        round_result = list(set(round_result))

    if not x:
        x.append(round_result)
    else:
        for i in x:
            if i == round_result:
                pass
            elif point in i:
                i.append(round_result[0])
                i.append(round_result[1])
            else:
                x.append(round_result)
                break

print(x)

but it desn´t work. Any help is appreciated!

CodePudding user response：

You can try this:

import numpy as np
import scipy

a = np.array([[6, 0, 0, 8, 9, 6, 1],
              [5, 1, 6, 8, 1, 1, 0],
              [4, 2, 1, 3, 7, 1, 5],
              [8, 8, 6, 6, 2, 5, 2],
              [7, 9, 4, 6, 9, 6, 4],
              [1, 4, 7, 8, 5, 3, 8],
              [9, 4, 8, 3, 9, 2, 9]])

def symm(a, pattern="hvdc"):
    b = np.stack([np.rot90(a, k=i) for i in range(4)])
    b = np.concatenate([b, b.swapaxes(1, 2)])
    subgps = {frozenset(s) : [0, i]  for i, s in enumerate("dvch", 4)}
    subgps |= {frozenset("vh"): [0, 2, 5, 7], frozenset("dc"): [0, 2, 4, 6]}
    if (p := frozenset(pattern)) in subgps:
        b = b[subgps[p]] 
    return scipy.stats.mode(b, keepdims=False)[0]

This function returns a matrix which has all specified symmetries: h = horizontal, v = vertical, d = diagonal (i.e. \), c = cross-diagonal (i.e. /). The characters -|/\ are not convenient as a function argument, since e.g. "\" is not a valid Python string.

For example, to get a matrix symmetric with respect to both diagonals one can use

print(symm(a, "dc"))

Which gives:

[[6 0 4 8 5 0 1]
 [0 1 6 8 1 1 0]
 [4 6 1 6 4 1 5]
 [8 8 6 6 6 8 8]
 [5 1 4 6 1 6 4]
 [0 1 1 8 6 1 0]
 [1 0 5 8 4 0 6]]

The symmetrized matrix obtained in this way has the minimal number of entries changed. Such matrix is not unique, since in some places there may be a choice which number to use. Then one can check how many entries were changed:

print((a != symm(a, "dc")).sum())

It gives:

The list with coordinates of entries that will have the same value after symmetrization can be obtained as follows (in this example for the "dc" symmetries, i.e. with respect to both diagonals):

n = a.shape[0]
b = symm(np.arange(n**2).reshape(n, n), "dc")
orbits = [list(zip(*np.where(b == i))) for i in np.unique(b)]

for c in orbits:
    print(c)

This gives:

[(0, 0), (6, 6)]
[(0, 1), (1, 0), (5, 6), (6, 5)]
[(0, 2), (2, 0), (4, 6), (6, 4)]
[(0, 3), (3, 0), (3, 6), (6, 3)]
[(0, 4), (2, 6), (4, 0), (6, 2)]
[(0, 5), (1, 6), (5, 0), (6, 1)]
[(0, 6), (6, 0)]
[(1, 1), (5, 5)]
[(1, 2), (2, 1), (4, 5), (5, 4)]
[(1, 3), (3, 1), (3, 5), (5, 3)]
[(1, 4), (2, 5), (4, 1), (5, 2)]
[(1, 5), (5, 1)]
[(2, 2), (4, 4)]
[(2, 3), (3, 2), (3, 4), (4, 3)]
[(2, 4), (4, 2)]
[(3, 3)]