Answer Set Programming: Re-arrange matrix so that in no row 2 numbers are in the same order

Question

Let's I have matrix

A =

1 2 3

1 3 5

1 2 4

2 3 7

The task is to re-arrange the matrix so that in no row two elements are in the same order.

For example, in row 1 and row 2 we have numbers 1 and 3 in the same order. We flip the numbers in 1 and 3 left to right in row 1 and get

3 2 1

1 3 5

1 2 4

2 3 7

My thoughts are this is a search problem, that could be maybe solved with Answer Set Programming? The problem is that if you try to do this with some algorithm, at some point you end up putting two numbers in to the same order as they are in some other row.

This is useful for reorienting triangular surface mesh faces of a mesh where the face normals point to inconsistent directions so that all normals point to inward (or outward)

Answer 1

Given input in the form:

value(ROW,COL,VAL).
nrows(nr).
ncols(nc).

You can do something like:

row(1..NR) :- nrows(NR).
col(1..NC) :- ncols(NC).
is_value(V) :- value(_, _, V).

% For each position in the original matrix, say what new column it's in.
{new_place(ROW,OLDCOL,NEWCOL,VAL) : col(NEWCOL)} = 1 :- value(ROW,OLDCOL,VAL).
% Can't have more than one value in the same position.
:- {new_place(ROW,_,COL,_)} > 1; row(ROW); col(COL).
% A comes before B in row ROW if COL_A < COL_B
ordered(A,B,ROW) :- new_place(ROW,_,COL_A,A); new_place(ROW,_,COL_B,B); COL_A < COL_B.
% For any two values A and B, there exists at most one row where A comes before B
:- {ordered(A,B,ROW) : row(ROW)} > 1; is_value(A); is_value(B).

#show.
#show p(R,C,V) : new_place(R,_,C,V).

Note that you have to keep track of the original column in case there are duplicates within a row. If no row contains duplicates (as is the case in your example) the second parameter of new_place is unnecessary.