Программирование набора ответов: переставьте матрицу так, чтобы ни в одной строке 2 числа не были в одинаковом порядке - PullRequest
Новая
       25

Программирование набора ответов: переставьте матрицу так, чтобы ни в одной строке 2 числа не были в одинаковом порядке

0 голосов
/ 02 мая 2019

Давайте, у меня есть матрица

A =

1 2 3

1 3 5

1 2 4

2 3 7

Задача состоит в том, чтобы переставить матрицу так, чтобы ни в одной строке два элемента не были в одном и том же порядке.

Например, в строке 1 и строке 2 у нас есть номера 1 и 3 в одинаковом порядке. Мы переворачиваем числа в 1 и 3 слева направо в строке 1 и получаем

3 2 1

1 3 5

1 2 4

2 3 7

Я думаю, что это проблема поиска, которая может быть решена с помощью программирования набора ответов? Проблема в том, что если вы попытаетесь сделать это с помощью какого-либо алгоритма, в какой-то момент вы в конечном итоге поместите два числа в том же порядке, что и в каком-то другом ряду.

Это полезно для переориентации граней треугольной поверхности сетки, где нормали граней указывают на непоследовательные направления, так что все нормали указывают внутрь (или наружу)

Ответы [ 2 ]

0 голосов
/ 05 мая 2019

С учетом ввода в форме: 

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

Вы можете сделать что-то вроде: 

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).

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

0 голосов
/ 03 мая 2019

Да, вы можете сделать это с ASP.

Это не самый элегантный код, но я думаю, что вы могли бы сделать это так, если бы вы использовали Clingo series 5: 

%% List the numbers to fill the matrix, we must associated each with an index value
number(1,1;2,2;3,3;1,4;3,5;5,6;1,7;2,8;4,9;2,10;3,11;7,12).

%% x limits
x(0..2).

%% y limits
y(0..3).

%% Generate the matrix
{ matrix(V, I, X, Y) } :- number(V, I), x(X), y(Y).

%% Define the order of the elements
order(V1, I1, V2, I2, Y) :- matrix(V1, I1, X1, Y), matrix(V2, I2, X2, Y), X1 < X2.

%% Do not allow two different rows to have the same order of elements
:- order(V1, I1, V2, I2, Y1), order(V1, I3, V2, I4, Y2), Y1 != Y2.

%% Each number must be in the matrix exactly once
:- not { matrix(V, I, X, Y) } = 1, number(V, I).

%% Each element can contain only one number
:- not #count { V, I : matrix(V, I, X, Y) } = 1, matrix(_, _, X, Y).

%% Show the matrix
#show matrix/4.

Что дает вам это как вывод:

3 1 3

4 2 3

1 1 5

2 2 7

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

...