% function definitions: % --------------------- % breadth_first_tree_search : establishes a whole maxdist-tree depth by depth % init_truth_administration : establishes a truth administration regarding a % single row establishes an array of all vectors % with a distance $leq$ 3 to the regarded row % counts the truths counts the Bits valued 1 in % truths for each position. % update_truth_administration : updates a truth administration regarding another % row % deletes each truth with a distance > 3 to the % regarded row % counts the residual truths % counts the Bits valued 1 in truths for each % position. % next_depth : computes the next depth of a maxdist-tree using % its last depth % case_abc : checks if any of the cases a), b), c) occures for % a matrix by the matrix's truth_administration % try_and_find_solution : tries to find a solution for a given set of truths % matrix_matcher : check's if two matrices are symmetric % appropriate_permutations : establishes a list of permutations for which two % pairs of distance_matrices would match % permute_distance_matrix : "permutes" a distance_matrix % given a distance_matrix A' of a matrix A and a % permutation p this function directly (not using % B) computes the distance_matrix B' for a matrix % B := (A under Permutation p) % permute_&_restructure_matrix: applies a row permutation to a matrix and swaps % the columns in the right part in order to % restore norm1 % restore_matrix_header : bitflipps and swaps columns in order to renorm % the first two rows of a matrix % try_and_equalize_left_part : swaps columns in the left part of a matrix % in order to complete a matching contempt ------------------------------------------------------------------------ ------------------------- main function ---------------------------- ------------------------------------------------------------------------ PROCEDURE search_all_trees IS BEGIN FOR maxdist IN 1..6 DO breadth_first_tree_search; OD; END search_all_trees; ------------------------------------------------------------------------ --------------- breadth_first_tree_search and subfunctions ------------- ------------------------------------------------------------------------ PROCEDURE breadth_first_tree_search RETURN boolean IS BEGIN create new output_file and file header; initialize row 1 and 2 of a matrix in last_depth according to current maxdist; establish a truth administration regarding row 1; % use function "init_truth_administration" for that update truth administration regarding row 2; % use function "update_truth_administration" for that WHILE last_depth not_empty DO set depth-header in output_file; compute next depth and assign: last_depth := next_depth; % use function "next_depth" for that OD; set end_of_file mark in output_file; END breadth_first_tree_search; ------------------------------------------------------------------------ ------------------------------------------------------------------------ FUNCTION init_truth_administration RETURN truth_administration IS output : truth_administration; BEGIN FOR every vector DO check distance from (0,0,0,0,0,0,0,0,0,0,0,0,2); % if d > 3 skip vector affiliate vector in truth array; increment number of truths; increment the componentes of 1-count-vector which are valued 1 in truth; OD; RETURN output; END init_truth_administration; ------------------------------------------------------------------------ ------------------------------------------------------------------------ FUNCTION update_truth_administration(old_administration: truth_administration; answer: row) RETURN truth_administration IS BEGIN For all truths IN old_administration DO check distance to answer; % If d $\leq$ 3 skip truth decrement the componentes of 1-count-vector which are valued 1 in truth; delete truth in possible truths; decrement number of truths; OD; RETURN old; END update_truth_administration; ------------------------------------------------------------------------ ------------------------------------------------------------------------ FUNCTION next_depth(last_depth: matrix_list) RETURN matrix_list IS next_depth : matrix_list; BEGIN FOR all matrices IN last_depth DO FOR all possible next rows DO append row to matrix; check maxdist; % If maxdist>3 skip this row Check norm 2; % If norm 2 violated skip this row Update truth administration; % Delete all vectors with distance > 3 % w.r.t. current row % use function "update_truth_administration" for that Check cases a, b, and c; % If such a case occurs, write that % to the output, and skip % use function "case_abc" for that Check symmetry to a former case; % If such a symmetry occurs, write that % to the output, and skip % use function "matrix_matcher" for all matrices in next_depth list for this Append new matrix to next_depth list; % matrix is to be investigated further OD OD RETURN next_depth; END next_depth; ------------------------------------------------------------------------ ------------------------------------------------------------------------ FUNCTION case_abc(truth_administration : truth_administration) RETURN case IS BEGIN IF number_of_truths = 0 THEN RETURN a; FI; IF any component of 1_count_vector is valued 0 or valued number_of_truths THEN RETURN b; FI; IF a solution can be found THEN RETURN c; % use function "try_and_find_solution" for that FI; RETURN d; -- which means neither of the cases a,b,c END case_abc; ------------------------------------------------------------------------ ------------------------------------------------------------------------ FUNCTION try_and_find_solution(truth_administration: truth_administration) RETURN Boolean IS BEGIN v := the first truth in truth administration; For v' with d(v',v) $\leq$ 3 DO IF the gained vector is a solution THEN RETURN True; OD; RETURN False; END try_and_find_solution; ------------------------------------------------------------------------ ======================================================================== ----------------------- The Matcher ------------------------------ ======================================================================== FUNCTION matrix_matcher(X,Y : Matrix) RETURN Boolean IS Permutationen : Permutationsliste := NEW Permutationslistenelement; Korrekte_Zeilen_Permutation : Permutation; Symmetrie : Boolean := FALSE; BEGIN Establish the row distance matrices for the left and the right part of X and Y; Check if the the left part matrices have the same entries % ELSE RETURN False; Check if the the right part matrices have the same entries % ELSE RETURN False; Establish a list of row-permutations that could possibly make the distance matrices match % use function "appropriate_permutations" for this FOR all these row-permutations DO apply the permutation to matrix Y; % use function "permute_&_restructure_matrix" for this % the function also sorts the columns in the right part according to norm 1 restore the correct form of the first two rows by symmetrie-operations % use function "restore_matrix_header" for this check if right parts of the matrices match % If they don't, skip this permutation try to attain a matching for the left parts of the matrices % use function "try_and_equalize_left_part" for this % If possible then write the permutation into the output_file OD END matrix_matcher; ------------------------------------------------------------------------ ------------------------------------------------------------------------ FUNCTION appropriate_permutations(A1,B1,A2,B2: Halbmatrix) RETURN permutations_list IS BEGIN For every permutation DO Apply Permutation to B1 and B2 % use function "permute_distance_matrix" for this IF A1 = B1 AND A2 = B2 THEN Append permutation to list; FI; OD; RETURN permutations; End appropriate_permutations; ------------------------------------------------------------------------ ------------------------------------------------------------------------ FUNCTION permute_distance_matrix(A: Halbmatrix; P: Permutation) RETURN Halbmatrix IS BEGIN For all entries in A DO A'(i,j) := A(P(i),P(j)) % An entry (i,j) in A marks the distance between row i an j % After the permutation it is meant to mark the distance between p(i) and p(j) OD RETURN A'; END permute_distance_matrix; ------------------------------------------------------------------------ ------------------------------------------------------------------------ FUNCTION permute_&_restructure_matrix(A: Matrix; Q: Permutation) RETURN Matrix IS BEGIN Apply Q to the rows of A % A'(i) := A(P(i)); for rows Sort the rows of the right part according to Norm 1 % A'(14-i) := A(14-Q(i)); for columns RETURN A'; END permute_&_restructure_matrix; ------------------------------------------------------------------------ ------------------------------------------------------------------------ FUNCTION restore_matrix_header(A: Matrix) RETURN Matrix IS BEGIN edit A in order to make row 1 "000000000000*" % Flip columns i with A(1)(i) = 1 edit A in order to make row 2 end with "..*0" % IF A(2)(13) = 1 THEN Flip column 13 edit A in order to make row 2 "11..00*0" % simply sort the columns 1..11 RETURN A; END restore_matrix_header; ------------------------------------------------------------------------ ------------------------------------------------------------------------ FUNCTION try_and_equalize_left_part(A,B: Matrix) RETURN Boolean IS BEGIN % at the beginning the unequalized part is to be left part of the matrices WHILE the unequalized part isn't empty DO take the most left column of the unequalized part in A; IF you can find this column in the unequalized part of B THEN Swap this column in B to the left (enlarging the equalized part); ELSE RETURN False; FI; OD; RETURN True; END try_and_equalize_left_part; ------------------------------------------------------------------------