Program to Change the least number of a given Matrix Elements to get a condition on the sum of the numbers from collated row digits of the Matrix

I have a given Matrix A=k x n (k rows and n columns), with all elements digits in base 4,(can be only {0,1,2,3}). I want to write a program to change for any input matrix A to a new output B matrix respecting a condition. The condition is to change the least number of elements of A to form a modified matrix B(which keeps all the other unchanged elements of A), such that the k numbers of the row collated digits summed in base 4, are a multiple of (4^n)-1, expressed in base 4(n the number of columns of A and B)(The multiple must be the one such that B differs with the minimum nr of elements from A). Note that (4^n)-1 in base 4 is a row of n digits all 3s(3333...33, n times) . (4^3)-1 in base 4 = 333, However, a multiple of (4^3)-1, for instance [5*(4^3)-1] in base 4= 10323.

%I will give just an Example of a matrix A=3x6, k=3, n=6

A= [3,3,3,2,2,2; 3,2,3,3,1,2; 3,1,0,1,3,2]

%Convert row collated digits to numbers then to decimal

base2base('333222',4,10)

base2base('323312',4,10)

base2base('310132',4,10)

%ans = '4074'

%ans = '3830'

%ans = '3358'

%Calculate their sum in base 10 of row digits 3 numbers

S=4074+3830+3358

%S = 11262

%Calculate (4^6) - 1 in decimal

(4^6) - 1

%4095

% One can see that a multiple of 2 of (4^6) - 1=8190, which can be expressed in base 4 , and is close to S

base2base('8190',10,4)

%ans = '1333332'

%To get this row digits sum just one element change is sufficient, change element of A (2,1)=3 to B(2,1)=0, hence B is

B= [3,3,3,2,2,2; 0,2,3,3,1,2; 3,1,0,1,3,2]

base2base('333222',4,10)

base2base('023312',4,10)

base2base('310132',4,10)

%ans = '4074'

%ans = '758'

%ans = '3358'

%Sum all in decimal to check if it is in base 4

S2=4074+758+3358

%S2 = 8190

% Which is the sought result. The program should be able to do such conversions of A to B for any input A

Answer 1

[Subhajyoti]

Hi Radu,

Approach

The intuitive solution to the problem is to get all possible matrices by changing the given matrix and sort them according to the number of elements that are changed from the original matrix. The first element that satisfies the condition as we iterate linearly through the list is our answer.

Algorithm

Please follow the below-mentioned steps to design your algorithm:

• Let, q be the queue of matrices (where, each matrix is changed from the original matrix). Initialize it to the given matrix.
• For each iteration, check if the front matrix is satisfying the condition:

- TRUE: return the matrix as result and exit the function

- FALSE: Add the other subsequent matrices that are obtained by changing this matrix to the queue and continue.

Note: This loop will terminate within finite iterations because there always exists a matrix which satisfies the condition. A null matrix with one right-most element as '1' will always satisfy the condition.

This approach uses ‘Breadth-First Search (BFS)’. This can be further optimised using ‘Level-Order Breadth-First Search’.

Here, in the following sample code,I have implemented the supporting functions in MATLAB R2024a.

[k, n] = size(A);
target_modulo = (4^n) - 1;

- Convert a base 4 number to base 10

function num = base4_to_base10(digits)
    num = sum(digits .* (4 .^ (length(digits)-1:-1:0)));
end

- Check if a number is a multiple of targert-modulo

function is_multiple = is_multiple_of_4n_minus_1(number, target_modulo)
    is_multiple = mod(number, target_modulo) == 0;
end

- Generate all possible modifications of A

function all_modifications = generate_all_modifications(A)
    [k, n] = size(A);
    all_modifications = {};
    for r = 1:k
        for c = 1:n
            original_value = A(r, c);
            for new_value = 0:3
                if new_value ~= original_value
                    modified = A;
                    modified(r, c) = new_value;
                    all_modifications{end+1} = modified;
                end
            end
        end
    end
end

Refer to the following MathWorks Documentation to understand more about ‘BFS’.

https://www.mathworks.com/help/matlab/ref/graph.bfsearch.html

Hope the above information is helpful.