3

数字のリストを取得して、順番に並べられた数字の最大シーケンスを取得できるようにしたいと考えています。例えば：

?- in_order([1,2,3,4,5],N).
N = 5.                              % expected result

?- in_order([1,2,5,6,7,8,4],N).
N = 4.                              % expected result

これまでのところ、一連の数字の長さをカウントアップする基本的なコードを作成しましたが、リストが空になると元に戻るため、N が返される数字はリストの最初の要素と同じです。バックトラッキングを停止する必要があることはわかっていますが、それができないようです。誰かが私を正しい方向に向けるのに十分親切でしょうか.

これまでの私のコード（すべて少しハックです）：

in_order([],_) :-
   !.
in_order([H|T],N):-
   (  var(N), 
      N is H 
   ;  true
   ),
   H = N,
   M is N+1,
   in_order(T,M).

私の現在の解決策は、与えられた2番目の例ではうまくいかないことを理解しています. SICStus Prolog を使用しています。

よろしくお願いします！

4

4 に答える 4

2

それをリレーションと呼びましょう。これはclpfdzs_maxInOrder/2に基づいており、具体化された制約 を使用しています。

:- use_module(library(clpfd)).

zs_maxInOrder([]    ,0).
zs_maxInOrder([Z|Zs],N) :-
    zs_prev_n_max0_max(Zs,Z,1,1,N).            % use "lagging" 

zs_prev_n_max0_max([]     ,_ ,_ ,M ,M).
zs_prev_n_max0_max([Z1|Zs],Z0,N0,M0,M) :-
    Z1 #= Z0 + 1 #<=> B,                       % with SWI-Prolog use `(#<==>)/2`
    N1 #= N0 * B + 1,
    M1 #= max(M0,N1),
    zs_prev_n_max0_max(Zs,Z1,N1,M1,M).

SICStus Prolog 4.3.1 を使用して動作を見てみましょう:

?- zs_maxInOrder([ 1,2,3,4,5 ],N)。
N = 5 ? ;
番号
?- zs_maxInOrder([1,2, 5,6,7,8,4 ] ,N)。
N = 4 ? ;
番号

コーナーケースはどうですか？

?- zs_maxInOrder([1],N).
N = 1 ? ;
no
?- zs_maxInOrder([],N).
N = 0 ? ;
no
于 2015-04-25T17:23:11.353 に答える
1

異なるものを混ぜているため、試みは失敗します。あなたが書くとき

N is H

基本的に、リストの要素の 1 つを出力しています。これは、いずれにしてもやりたくないことです。また、基本ケースが間違っています。「空のリストにはゼロの順序付けられたシーケンスがあります」である必要があります。

現在のヘッド H で終了する連続した要素を追跡する「アキュムレータ」引数を使用してみてください。

于 2012-12-04T17:10:03.750 に答える
1

これは、この問題に対するかなり強引な解決策です:P (批判されることはわかっていますが、高次の述語をいじることに抵抗できませんでした)。

my_prefix(List,Prefix) :- 
   append(Prefix,_,List).

my_suffix(List,Suffix) :- 
   append(_,Suffix,List).

my_sublist(List,Sublist) :-
   my_suffix(List,Suffix),
   my_prefix(Suffix,Sublist).

all_sublists(List,AllSublists) :- 
   findall(Sub,my_sublist(List,Sub),AllSublists).

good_list([]) :- 
   !.
good_list([H]) :- 
   !.
good_list([H1,H2|T]) :- 
   H1 is H2-1,
   good_list([H2|T]),
   !.

in_order(List,Length) :-
   all_sublists(List,AllSublists),
   findall(L,(member(Sublist,AllSublists),
              good_list(Sublist),
              length(Sublist,L)),
             InOrderSizes),
   max_list(InOrderSizes,Length).
于 2012-12-04T20:44:58.790 に答える
0

「空のリストには、ゼロの順序付きシーケンスがあります」。

ありがとうございます。それは私を正しい軌道に乗せました（私は思う）

これはこれまでの私の解決策です：

in_order([], _, 0).
in_order([H|T], Prev, N):-
  % Split the list
  in_order(T, H, M),
  % Increment the expected Head value
  H1 is Prev + 1,
    (
      H = H1,
      N is M + 1
    ;
      M1 is M + 1,
      format('M1 is ~w~n', [M1]),
      N is 0
  ).

最終段階で何が印刷されているかを確認できるようにフォーマットを追加しました。入力 [1,2,5,6,7,8,4] の値 1 と 4 を取得します。これは正しいです。述語は 2 (シーケンスの最後の長さ) を返しますが、バックトラックしてさらに回答を取得しようとすると、値 4 または 1 が得られません。回答にかなり近いと思います。追加の最終的なヘルプは感謝。

どうもありがとう

于 2012-12-05T13:27:18.640 に答える