Prolog：获取包含给定整数的子列表

Question

我正在尝试通过解决 Advent Of Code 难题来学习 Prolog，但最终被困在了一个我认为应该非常简单的任务上。有问题的谜题是 this one。该任务要求我找到所有连接到程序 ID 0 的程序 ID（整数）。连接是对称的和可传递的，因此如果来自不同连接组的程序之间存在连接，则给定组中的所有程序都相互连接.

我目前的情况是，我已将拼图中的整数分类为子列表，每个子列表代表它们所属的组。

例如：[[0, 2], [1, 1], [2, 0, 3, 4], [3, 2, 4], [4, 2, 3, 6], [5, 6], [6, 4, 5]]

我需要获取所有以某种方式连接到 0 的程序。在此示例中，这将是除 ID 为 1 的程序之外的所有程序。

因此，我正在寻找的逻辑是设法检查给定整数是否同时存在于包含 0 的扩展组和我的递归谓词连接的当前正在查看的组中。我意识到这种方法可能最终会忽略在递归早期查看的与组的新连接，但这是一个单独的问题。

像上面那样将程序分类到子列表中不是问题，所以我从目前的内容中省略了那部分。

main(R) :-
  Groups = [[0, 2], [1, 1], [2, 0, 3, 4], [3, 2, 4], [4, 2, 3, 6], [5, 6], [6, 4, 5]],
  connected(Groups, [0], R). 

connected([H|T], X, R) :-
  member(Y, H), member(Y, X) -> flatten([H|X], X1), connected(T, X1, R) ; R = X.

我得到的结果很简单：[0,2,0]
我期望的结果是：[0,2,0,2,0,3,4,3,2,4,4,2,3,6,5,6,6,4,5]

我意识到元素 [1,1] 可能会过早停止递归，所以我尝试将上面的最后一行更改为以下内容：
member(Y, H), member(Y, X) -> flatten([H|X], X1), connected(T, X1, R) ; connected(T, X, R).

但是，这只会导致 main(R)。出于某种原因评估为假。同样，如果我只是从组中删除 [1,1] 而不更改最后一行，则 returns 为 false。

我假设我忽略了一些非常简单的事情，并希望收到任何意见。

Answer 1

假设您的组具有正确的结构，您可以保留 "unvisited" 个组的列表，并在每个递归步骤中获取一个未访问的项目并添加其仍未访问的邻居。

即：

main(R) :-
  Groups = [[0, 2], [1, 1], [2, 0, 3, 4], [3, 2, 4], [4, 2, 3, 6], [5, 6], [6, 4, 5]],
  connected([0], [], Groups, R).

connected([], _, _, []).
connected([P|Tail], Visited, Groups, [P|R]):-
  select([P|Ps], Groups, NGroups), % Get the item's neighours
  subtract(Ps, [P|Visited], NPs),  % subtract from it the visited ones
  union(Tail, NPs, NTail),         % and add these neighours to the unvisited list
  connected(NTail, [P|Visited], NGroups, R).

这将得到 "connected" 个没有重复的程序集：

?- main(R).
R = [0, 2, 3, 4, 6, 5]

Prolog：获取包含给定整数的子列表

Prolog: Get sublists that contain given integer

recursion

prolog

edges

sublist

undirected-graph