查找任何给定列表中最长的回文

Question

我有一个分配给我的字符串，然后将其转换为字符串，我应该找到所述列表的最长回文，并输出为实现该目标我必须从列表中删除多少个字符。

我当前的代码如下：

solve(X) :-
    string2List(X).

string2List(Input) :-
        string_codes(Input,Output),
        palchecker(Output,0).

palchecker(Input,LengthRest):-
    palindrome(PermuteList),
    is_permutation(Input,PermuteList),
    write(LengthRest).

palindrome(L):- reverse(L, L).

is_permutation(Xs, Ys) :-
  msort(Xs, Sorted),
  msort(Ys, Sorted).

正如人们所看到的，我可以处理已经是回文的列表而没有问题。问题是当列表不是回文而是通过删除X数量的字符可以从中构造回文时如何进行处理。

我以前使用置换而不是is_permutation，并且设法使它起作用（使用一些附加代码）。但是，这种方法的问题在于它花费了太长时间。该算法应该能够在几秒钟内管理多达1000个字符的列表。

Answer 1

我将尝试使用select/3从输入列表（0..length_of_input中的N个）中删除N个项目，然后应用您的算法。

类似这样的东西：

string2List(Input, Output1, ToRemove) :-
        string_codes(Input,Input1),
        once(palchecker(Input1, Output, ToRemove)),
        string_codes(Output1, Output).

palchecker(Input, Output, ToRemove):-
  length(Input, Len),
  between(0, Len, ToRemove),
  Size is Len-ToRemove,
  length(Output, Size),
  remove_n(ToRemove, Input, Input1),
  palindrome(Output),
  permutation(Input1, Output).

remove_n(N, Input, Input2):-
  N > 0,
  succ(N1, N),
  select(_, Input, Input1),
  remove_n(N1, Input1, Input2).
remove_n(0, Input, Input).

使用once/1只能获得最大的回文解决方案（可能有许多具有相同长度的解决方案）。该算法将对许多输入产生相同解决方案的许多重复。我也将删除的项数作为参数添加到string2List。