0

我有一个代表二维列表 x 的给定列表。该表包含两个 1 的“点”，如下例所示：

xxxxxxxxxxxxxxxx
xx1111xxxx111xxx
xxx1111xxxx11xxx
x1111xxxxxx111xx

我只需要将第二个点从 1 更改为 2，如下例所示：

xxxxxxxxxxxxxxxx
xx1111xxxx222xxx
xxx1111xxxx22xxx
x1111xxxxxx222xx

我需要一个谓词separate(L,M)，它将采用第一个列表 L 并生成第二个表 M

如果我们可以在不使用任何标准谓词（如“findall”等）的情况下解决这个问题，那就太好了......

4

3 回答 3

3

您可以使用定句语法 (DCG) 来实现有限状态转换器。尽管 DCG 在制作方面并没有提供太多的合成操作，但它们在识别方面的实现却相当出色。

因此，您要识别的是两种不同类型的 1 运行。所以基本上我猜输入行在扩展巴科斯瑙尔形式（EBNF）中如下所示：

line :== exs run1 exs run2 exs | exs.
exs  :== { "x" } "x".
run1 :== { "1" } "1".
run2 :== { "1" } "1".

对于识别问题，你可以写一个不带属性的DCG（下面是一段Prolog文本，你可以放在一个文件中或直接通过？- [user]查阅）：

line --> exs, run1, exs, run2, exs | exs.

run1 --> "1", run1.
run1 --> "1".

run2 --> "1", run2.
run2 --> "1".

exs --> "x", exs.
exs --> "x".

以下是一些示例运行：

?- phrase(line,"xxx").
Yes 
?- phrase(line,"xxx111xxx111xxx").
Yes 
?- phrase(line,"xxx111xxx"). 
No

对于生产问题，您只需将属性添加到 DCG。使用差异列表最简单：

line(I,O) --> exs(I,H), run1(H,J), exs(J,K), run2(K,L), exs(L,O) | exs(I,O).

run1([0'1|I],O) --> "1", run1(I,O).
run1([0'1|H],H) --> "1".

run2([0'2|I],O) --> "1", run2(I,O).
run2([0'2|H],H) --> "1".

exs([0'x|I],O) --> "x", exs(I,O).
exs([0'x|H],H) --> "x".

以下是一些示例运行：

?- phrase(line(R,[]),"xxx").
R = [120, 120, 120] 
?- phrase(line(R,[]),"xxx111xxx111xxx").
R = [120, 120, 120, 49, 49, 49, 120, 120, 120, 50, 50, 50, 120, 120, 120] 
?- phrase(line(R,[]),"xxx111xxx").
No

注意：0' 是字符代码的 Prolog 符号。在 ascii 中，我们有 0'x = 120, 0'1 = 49, 0'2 = 50，这解释了结果。以上应该可以在大多数 Prolog 系统上运行，因为它们支持 DCG。

再见

定从句语法
http://en.wikipedia.org/wiki/Definite_clause_grammar

有限状态传感器
http://en.wikipedia.org/wiki/Finite_state_transducer

于 2012-01-08T14:19:25.603 回答
1

我们可以应用临时音译（仅适用于“水平”列表）：

transliteration(Matrix, Translit) :-
  maplist(transliteration(not_seen), Matrix, Translit).

transliteration(_State, [], []).
transliteration(State, [X|Xs], [Y|Ys]) :-
  transliteration(State, X, NewState, Y),
  transliteration(NewState, Xs, Ys).

% handle only required state change
transliteration(not_seen, 0'1, seen_first, 0'1).
transliteration(seen_first, C, seen_last, C) :- C =\= 0'1.
transliteration(seen_last, 0'1, seen_last, 0'2).
% catch all, when no change required
transliteration(State, C, State, C).
于 2012-01-08T15:39:21.227 回答
0

类似于@chac 建议的解决方案，但更直接。

walk(L, R) :- walk(s0, L, R).
walk(_, [], []). % finish
walk(s0, [0'1|T], [0'1|R]) :- walk(s1, T, R).
walk(s1, [0'x|T], [0'x|R]) :- walk(s2, T, R).
walk(s2, [0'1|T], [0'2|R]) :- walk(s2, T, R).
walk(S, [H|T], [H|R]) :- walk(S, T, R). % keep state and do nothing
于 2012-01-08T16:10:52.897 回答