我需要编写一个turbo prolog程序，它将从列表中删除所有回文

Question

我需要做一个 Turbo prolog 程序，从列表中删除所有回文（包括交叉回文，如 1 2 1 3 1）。

我尝试使用以下算法编写一个程序：

例如：1 2 1 3 1 4 5 1

1. 创建原始列表的所有前缀的列表。看起来像 [[1], [1,2], [1,2,1],…]

2. 创建从所有前缀列表中删除的回文列表。这意味着我们检查每个前缀是否是回文以及是否 > 1。对于这个特定的例子。它看起来像 [[1,2,1][1,3,1]]

3. 根据回文列表删除原列表中的每个元素。这意味着如果元素存在于回文列表中，它将被删除。 （有错误）与这个前任。它会输出 [4,5]，但应该是 [4,5,1]

昨天我和我的教授交谈，他说我们可以索引列表中的每个元素，然后索引回文的每个元素，删除索引的重复项，然后根据该索引从原始列表中删除元素。但我不知道该怎么做。

所以，如果你们能够帮助我，我会很高兴🥺

这是我的代码：

domains
int = integer
intl = int*
intll = intl*

predicates
read_list(intl)
reverse(intl, intl)
append(intll, intll, intll)
app(intl, intl, intl)
length(intl, int)
cut(intl, int, intl)
subseq(intl, int, int, intl)
prefixes(intl, int, intll)
all_sublists(intl, intll)
is_pal(intl)
all_pals(intll, intll)
all_palindroms(intl, intll)
belongs_to_sublist(int, intll)
filter_elements(intll, intl, intl)
member(int, intl)

clauses
read_list([Head|Tail]) :-
    readint(Head), !,
    read_list(Tail).
read_list([]).

reverse([], []).
reverse([H|T], X) :- reverse(T, Rt), app(Rt, [H], X).

append([], X, X).
append([H|T], X, [H|R]) :- append(T, X, R).

app([], X, X).
app([H|T], X, [H|R]) :- app(T, X, R).

length([], 0).
length([_|T], N) :- length(T, N1), N = N1 + 1.

cut(_, 0, []) :- !.
cut([H|T], L, [H|R]) :- L1 = L - 1, cut(T, L1, R).

subseq(X, 0, L, R) :- cut(X, L, R), !.
subseq([_|X], P, L, R) :- P1 = P - 1, subseq(X, P1, L, R).

prefixes(X, L, []) :- length(X, LX), L > LX, !.
prefixes(X, L, [R|T]) :- subseq(X, 0, L, R), L1 = L + 1, prefixes(X, L1, T).

all_sublists([], []).
all_sublists([H|T], Q) :- prefixes([H|T], 1, R), all_sublists(T, Z), append(R, Z, Q).

is_pal(X) :- reverse(X, Rx), X = Rx.

all_pals([], []).
all_pals([H|T], [H|R]) :- length(H, L), L > 1, is_pal(H), all_pals(T, R), !.
all_pals([_|T], R) :- all_pals(T, R).

all_palindroms(X, U) :- all_sublists(X, Sx), all_pals(Sx, U).

belongs_to_sublist(Element, [Sublist|_]) :-
    member(Element, Sublist).
belongs_to_sublist(Element, [_|Sublists]) :-
    belongs_to_sublist(Element, Sublists).

filter_elements(_, [], []).
filter_elements(Sublists, [H|T], [H|Filtered]) :-
    not(belongs_to_sublist(H, Sublists)),
    filter_elements(Sublists, T, Filtered).
filter_elements(Sublists, [H|T], Filtered) :-
    belongs_to_sublist(H, Sublists),
    filter_elements(Sublists, T, Filtered).

member(X, [X|_]).
member(X, [_|Tail]) :- member(X, Tail).

goal
write("Elements of list:"), nl,
read_list(List),
write("list:"), write(List), nl,
all_palindroms(List, Q), write("all palindromes in list: "), write(Q), nl,
filter_elements(Q, List, Res), write("without palindromes: "), write(Res).

Answer 1

由于我的电脑上没有Turbo-Prolog，所以我使用SWI-Prolog解决了这个问题。我想您可以轻松地将这段代码改编为 Turbo-Prolog。

palindromic_prefix(List, Prefix) :-
    Prefix = [_,_|_],
    append(Prefix, _, List),
    reverse(Prefix, Prefix).

collect_palindromic_ranges([], _, []).
collect_palindromic_ranges([X|Xs], Index, Ranges) :-
    (   palindromic_prefix([X|Xs], Prefix)
    ->  length(Prefix, Length),
        End is Index + Length - 1,
        Ranges = [Index-End|Rest]
    ;   Ranges = Rest),
    Next is Index + 1,
    collect_palindromic_ranges(Xs, Next, Rest).

exclude_palindromic_ranges([], _, _, []).
exclude_palindromic_ranges([X|Xs], Index, Ranges, Rest) :-
    (   member(Begin-End, Ranges),
        between(Begin, End, Index)
    ->  Rest = Rest0
    ;   Rest = [X|Rest0] ),
    NextIndex is Index + 1,
    exclude_palindromic_ranges(Xs, NextIndex, Ranges, Rest0).

remove_palindromic_sublists(List, Rest) :-
    collect_palindromic_ranges(List, 1, Ranges),
    exclude_palindromic_ranges(List, 1, Ranges, Rest).

示例：

?- remove_palindromic_sublists([1,2,1,3,1,4,5,1], Rest).
Rest = [4, 5, 1].

?- remove_palindromic_sublists([0,1,2,1,3,3,1,4,5,1,5,6], Rest).
Rest = [0, 4, 6].

?- remove_palindromic_sublists([1,2,3,2,1], Rest).
Rest = [].

?- remove_palindromic_sublists([1,1,1], Rest).
Rest = [].

?- remove_palindromic_sublists([1,2,3], Rest).
Rest = [1, 2, 3].

谓词

palindromic_prefix(+List, -Prefix)

成功当且仅当

List

具有回文数

Prefix

:

?- palindromic_prefix([1,2,1,3,1,4,5,1], Prefix).
Prefix = [1, 2, 1] .

?- palindromic_prefix([2,1,3,1,4,5,1], Prefix).
false.

谓词

collect_palindromic_ranges(+List, +Index, -Ranges)

收集

Ranges

中的所有

List

，从

Index

索引，其中包含回文子列表：

?- collect_palindromic_ranges([1,2,1,3,1,4,5,1], 1, Ranges).
Ranges = [1-3, 3-5].

谓词

exclude_palindromic_ranges(+List, +Index, +Ranges, -Rest)

排除

List

中位于

Ranges

之一的所有元素，从

Index

索引：

?- List = [1,2,1,3,1,4,5,1], collect_palindromic_ranges(List, 1, Ranges), exclude_palindromic_ranges(List, 1, Ranges, Rest).
List = [1, 2, 1, 3, 1, 4, 5, 1],
Ranges = [1-3, 3-5],
Rest = [4, 5, 1].