Prolog：将列表拆分为 N 个列表的列表，每个列表包含 N 个项目

Question

我一直在搜索与拆分相关的许多现有 Prolog 问题，但找不到像我想要的那样通用的问题。我想指出，我已经能够通过使用在列表变量之前传输的 2/3/4 变量将列表拆分为 2/3/4 元素的列表。这个问题与那个问题的不同只是因为它的通用性。

因此，我的列表将始终包含 N*N 项，N 事先是未知的（通常会在 4 到 36 之间变化，是的，N 也是一个完美的正方形）。我想将它拆分成一个包含 N 个列表的列表，每个列表包含 N 个项目，因为这将允许我将它视为一个矩阵，从而允许转置和某些此类操作。由于我对声明式编程还比较陌生，所以我并没有真正了解逻辑。请看下面我不完整（错误）的尝试：

listmodel(1,L):- L = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16].
size(L,N) :- length(L,N1), N is round(sqrt(N1)).

% add_tail(+Liste, +Element, -ResultantList)
add_tail([],L,[L]).
add_tail([X|L1],L2,[X|LI]):-add_tail(L1,L2,LI).

% partition the list containing N*N items into a list of N lists containing N elements each.
% part(+Liste, +Size, -ResultantList)
part([],_,DL).
part(L,N,DL) :-
    length(P,N), % P(refix) initialized
    append(P,S,L), % S(uffix) contains rest of L, using append in (-,-,+) mode
    add_tail(DL,P,DL1), %add P(first N elements) as first element of DL.
    part(S,N,DL1).

现在运行 ?- listmodel(1,L),size(L,N),part(L,N,DL). 将生成 DL=[] 因为这是它在 part 谓词的第一个 add_tail 调用中初始化的结果。我似乎无法弄清楚如何将所有元素存储在通过递归保留的列表中。

任何类型的 help/direction 都将不胜感激。我被困在这里已经超过 23 小时 10 分钟了。

谢谢。

Answer 1

应该这样做：

part([], _, []).
part(L, N, [DL|DLTail]) :-
   length(DL, N),
   append(DL, LTail, L),
   part(LTail, N, DLTail).

基本情况是 first/last 参数是空列表。

递归步骤获取 N 个元素的新列表，从 L 中获取前 N 个元素（这将是第三个参数的项目之一）并递归调用。

Answer 2

想要结合多功能性和有利的终止特性？ 使用clpfd!

:- use_module(library(clpfd)).

首先，我们定义 list_prefix_n_suffix/4。 list_prefix_n_suffix(Zs,Xs,N,Ys) 在逻辑上等同于 <a href="https://www.complang.tuwien.ac.at/ulrich/iso-prolog/prologue#append" rel="nofollow">append</a>(Xs,Ys,Zs), <a href="https://www.complang.tuwien.ac.at/ulrich/iso-prolog/prologue#length" rel="nofollow">length</a>(Xs,N) and <a href="https://www.complang.tuwien.ac.at/ulrich/iso-prolog/prologue#length" rel="nofollow">length</a>(Xs,N), <a href="https://www.complang.tuwien.ac.at/ulrich/iso-prolog/prologue#append" rel="nofollow">append</a>(Xs,Ys,Zs)，但比 either 具有更好的通用终止行为]¹个！

list_prefix_n_suffix(Zs, Xs, N, Ys) :-
   list_prefix_n0_n_suffix(Zs, Xs, 0,N, Ys).

list_prefix_n0_n_suffix(Zs, Xs, N0,N, Ys) :-
   zcompare(Order, N0, N),
   rel_list_prefix_n0_n_suffix(Order, Zs, Xs, N0,N, Ys).

rel_list_prefix_n0_n_suffix(=, Ys, [], _,_, Ys).
rel_list_prefix_n0_n_suffix(<, [Z|Zs], [Z|Xs], N0,N, Ys) :-
   N1 #= N0 + 1,
   list_prefix_n0_n_suffix(Zs, Xs, N1,N, Ys).

list_prefix_n_suffix/4 的一些示例查询：

?- list_prefix_n_suffix([a,b,c], Xs,-1, Ys).
false.                                          % OK: too small

?- list_prefix_n_suffix([a,b,c], Xs, 0, Ys).
Xs = [], Ys = [a,b,c].                          % succeeds deterministically

?- list_prefix_n_suffix([a,b,c], Xs, 4, Ys).
false.                                          % OK: too big

?- list_prefix_n_suffix([a,b,c], Xs, N, Ys).
   Xs = []     , N = 0, Ys = [a,b,c]
;  Xs = [a]    , N = 1, Ys =   [b,c]
;  Xs = [a,b]  , N = 2, Ys =     [c]
;  Xs = [a,b,c], N = 3, Ys =      []
;  false.                                       % terminates universally

根据上面list_prefix_n_suffix/4我们定义list_rows_width/3:

list_rows_width([], [], _N).
list_rows_width([E|Es0], [[R|Rs]|Rss], N) :-
   list_prefix_n_suffix([E|Es0], [R|Rs], N, Es),
   list_rows_width(Es, Rss, N).

示例查询使用 list_rows_width/3:

?- list_rows_width([a,b,c,d,e,f], Rows, 4).
false.                                          % OK: 6 is not divisible by 4

?- list_rows_width([a,b,c,d,e,f], Rows, 3).
Rows = [[a,b,c],[d,e,f]].                       % succeeds deterministically

?- list_rows_width([a,b,c,d,e,f,g,h,i,j,k,l], Rows, N).
   N =  1, Rows = [[a],[b],[c],[d],[e],[f],[g],[h],[i],[j],[k],[l]]
;  N =  2, Rows = [[a,  b],[c,  d],[e,  f],[g,  h],[i,  j],[k,  l]]
;  N =  3, Rows = [[a,  b,  c],[d,  e,  f],[g,  h,  i],[j,  k,  l]]
;  N =  4, Rows = [[a,  b,  c,  d],[e,  f,  g,  h],[i,  j,  k,  l]]
;  N =  6, Rows = [[a,  b,  c,  d,  e,  f],[g,  h,  i,  j,  k,  l]]
;  N = 12, Rows = [[a,  b,  c,  d,  e,  f,  g,  h,  i,  j,  k,  l]]
;  false.                                       % terminates universally

工作正常！

^{脚注 1：不求助于使用替代 control-flow 机制，如 prolog-coroutining。}

Prolog：将列表拆分为 N 个列表的列表，每个列表包含 N 个项目

Prolog: split a list into a list of N lists containing N items each

list

prolog

sudoku

declarative