在 Prolog 中按位置对列表元素进行分组

Question

我找到了一个非常好的 Erlang 实现，用于按位置对列表成员进行分组。

everynth(List, N) ->
   [ lists:reverse(Y)
     || Y <- lists:foldl(
                     fun(X, [H|T]) -> T++[[X|H]] end,
                     lists:duplicate(N, []),
                     List)
   ].

这将提供的列表 (List) 按其索引位置分为 3 组：

everynth([1, 2, 3, 4, 5, 6, 7, 8, 9], 3).

给予

[[1,4,7],[2,5,8],[3,6,9]].

我想在 Prolog 中做同样的事情，但我不知道该怎么做。你能帮助我吗？谢谢。

Answer 1

不是很优雅，但应该可以。

getEveryNth([], _, [], _).
getEveryNth([H|Ti], N, [H|To], N) :-
  getEveryNth(Ti, 1, To, N).
getEveryNth([_|Ti], M, Lo, N) :-
  M < N,
  Mp1 is M+1,
  getEveryNth(Ti, Mp1, Lo, N).

everyNthH(_, 0, [], _).
everyNthH([H|Ti], M, [[H|To] | Lo], N) :-
  M > 0,
  Mm1 is M-1,
  getEveryNth(Ti, 1, To, N),
  everyNthH(Ti, Mm1, Lo, N).

everyNth(L, N, LL) :-
  everyNthH(L, N, LL, N).

来自

everyNth([1, 2, 3, 4, 5, 6, 7, 8, 9], 3, L)

我得到（L统一）

[[1,4,7],[2,5,8],[3,6,9]]

Answer 2

直译

我们可以在 Prolog 中以与 Erlang 版本非常接近的方式实现它。

例如，使用 Ulrich Neumerkel 的 library(lambda):

everynth(Ls, N, Groups) :-
        findall([], between(1,N,_), Groups0),
        foldl(\L^[G0|Gs0]^Gs^append(Gs0,[[L|G0]],Gs), Ls, Groups0, Groups1),
        maplist(reverse, Groups1, Groups).

根据您的 Prolog 系统，您可能需要导入一两个库到运行 this.

在其他相似之处中，这带有一个非常不幸的缺点。练习：哪个？提示：Imeanapartfromthename.

替代版本

为了克服上述缺点，我还展示了一个替代解决方案。

积木

我将使用的关键构建块是 with_remainder_mod/5，定义为：

with_remainder_mod(N, L, R-L, I0, I) :-
        R #= I0 mod N,
        I #= I0 + 1.

本质上，这为每个元素配备了其索引的残基（mod N)。例如：

?- foldl(with_remainder_mod(3), [a,b,c,d,e,f], Rs, 0, _).
Rs = [0-a, 1-b, 2-c, 0-d, 1-e, 2-f].

我们几乎完成，因为我们现在可以使用 ISO 标准谓词 keysort/2，然后是广泛可用的 group_pairs_by_key/2 或类似的库谓词：

?- foldl(with_remainder_mod(3), [a,b,c,d,e,f], Rs0, 0, _),
   keysort(Rs0, Rs),
   group_pairs_by_key(Rs, Gs).
Rs0 = [0-a, 1-b, 2-c, 0-d, 1-e, 2-f],
Rs = [0-a, 0-d, 1-b, 1-e, 2-c, 2-f],
Gs = [0-[a, d], 1-[b, e], 2-[c, f]].

完整解决方案

总的来说，完整的解决方案可能如下所示：

with_remainder_mod(N, L, R-L, I0, I) :-
        R #= I0 mod N,
        I #= I0 + 1.

every_nth(Ls0, N, Groups) :-
        foldl(with_remainder_mod(N), Ls0, Rs0, 0, _),
        keysort(Rs0, Rs),
        group_pairs_by_key(Rs, KeyGroups),
        pairs_values(KeyGroups, Groups).

时间复杂度为Θ(n·log n)，其中n为列表长度

请注意，此解决方案使用：

声明性整数算法 通过 CLP(FD) 约束，使其在所有方向.
foldl/5 这是一个非常有用的 meta-predicate，它已经与几个 Prolog 系统一起提供。

同样，根据您的 Prolog 系统，您可能需要导入一两个库以使用这些工具和其他谓词，如 pairs_values/2 或等效的。

例子

您的示例查询和答案：

?- every_nth([1,2,3,4,5,6,7,8,9], 3, Ls).
Ls = [[1, 4, 7], [2, 5, 8], [3, 6, 9]].

当然也可以进行更一般的查询：

?- length(Es, _), every_nth(Es, 3, Ls).
Es = Ls, Ls = [] ;
Es = [X1],
Ls = [[X1]] ;
Es = [X1, X2],
Ls = [[X1], [X2]] ;
Es = [X1, X2, X3],
Ls = [[X1], [X2], [X3]] ;
Es = [X1, X2, X3, X4],
Ls = [[X1, X4], [X2], [X3]] ;
Es = [X1, X2, X3, X4, X5],
Ls = [[X1, X4], [X2, X5], [X3]] ;
etc.

请注意，基于 findall/3 的版本无法 执行此操作，因为 findall/3 会创建新的副本变量。

这是一个基准，可能对您在不同的解决方案之间做出决定很有用：

?- length(_, E),
   portray_clause(2^E),
   N #= 2^E, I #= N // 2,
   length(Ls, N),
   time(every_nth(Ls,I,_)),
   false.
2^0.
% 150 inferences, 0.000 CPU in 0.000 seconds (80% CPU, 4545455 Lips)
2^1.
% 34 inferences, 0.000 CPU in 0.000 seconds (78% CPU, 2428571 Lips)
2^2.
% 62 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 4428571 Lips)
2^3.
% 118 inferences, 0.000 CPU in 0.000 seconds (86% CPU, 6555556 Lips)
2^4.
% 230 inferences, 0.000 CPU in 0.000 seconds (93% CPU, 8214286 Lips)
2^5.
% 454 inferences, 0.000 CPU in 0.000 seconds (94% CPU, 9659574 Lips)
2^6.
% 902 inferences, 0.000 CPU in 0.000 seconds (96% CPU, 10488372 Lips)
2^7.
% 1,798 inferences, 0.000 CPU in 0.000 seconds (92% CPU, 9364583 Lips)
2^8.
% 3,590 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 10316092 Lips)
2^9.
% 7,174 inferences, 0.001 CPU in 0.001 seconds (99% CPU, 11297638 Lips)
2^10.
% 14,342 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 10491587 Lips)
etc.

Answer 3

我不得不做一些尝试和测试来找到索引之间的正确关系，你可以从变量的名称中看到 everynth_starting/4 已经 'uninlined' 以简化调试。

everynth(L, P, Gs) :-
    findall(G, (
        between(1, P, S),
        everynth_starting(L, P, S, G)
    ), Gs).
everynth_starting(L, P, S, G) :-
    findall(E, (nth1(I, L, E), S mod P=:=I mod P), G).

nth1/3 作为对 index/element

的生成器

在 Prolog 中按位置对列表元素进行分组

Grouping list elements by position in Prolog

list

sorting

prolog

grouping

declarative

直译

替代版本

积木

完整解决方案

例子