检查矩阵索引列表是否相邻 [英] Check if List of Matrix Indexes are adjacent

问题描述

给定一个索引列表List和矩阵大小N，我想检查该列表的索引是否连续.

Given a list of indexes List and the matrix size N, I want to check if indexes of that list are contiguous.

例如，矩阵5x5，索引如下:

For example, matrix 5x5, the indexes are as it follows:

 1  2  3  4  5
 6  7  8  9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25


isContiguous([11,12,13,7,2], 5) :- yes.

isContiguous([14,15,16,17,18], 5) :- no.

我尝试实现深度优先搜索，从第一个索引开始，然后检查以下内容是否连续，但是我不能，因为只有在列表为一行或一列且第一个元素位于其中时，此方法才有效该形状的开始或结尾.

I tried to implement a depth first search, starting with the first index and checking if the following is contiguous, but I couldn't, as it only works if the list makes a line or a column and the first element is in the beginning or in the end of that shape.

谢谢您的时间:)

推荐答案

您可以定义节点邻接关系和确定节点之间是否存在单个连接图的过程:

You may define a relation for a node adjacencies and a procedure to see if there is a single connected graph between your nodes:

:-use_module(library(clpfd)).

adjacent(Size, N, _, Adj):-
  Adj #= N-Size,
  Adj #> 0.
adjacent(Size, N, Max, Adj):-
  Adj #= N+Size,
  Adj #=< Max.
adjacent(Size, N, _, Adj):-
  0 #\= N mod Size,
  Adj #= N+1.
adjacent(Size, N, _, Adj):-
  1 #\= N mod Size,
  Adj #= N-1.

is_contiguous(L, Size):-
  Max #= Size*Size,
  between(1, Max, Len), % sanity checks for when L is not instantiated
  length(L, Len),
  select(N, L, L1),
  between(1, Max, N),   % idem
  is_contiguous1([N], L1, Size, Max).

is_contiguous1(_, [], _, _).
is_contiguous1(Seen, Rem, Size, Max):-
  member(N, Seen),
  adjacent(Size, N, Max, Adj),
  \+(member(Adj, Seen)),
  select(Adj, Rem, NRem),
  is_contiguous1([Adj|Seen], NRem, Size, Max).

样品运行:

?- is_contiguous([11,12,13,7,2], 5).
true.
?- is_contiguous([14,15,16,17,18], 5).
false.
?- once(is_contiguous([14,15,X,16,17,18], 5)).
X = 19

这篇关于检查矩阵索引列表是否相邻的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！