Пролог: сортировать подсписок в списке

Как это сделать? Мне нужно что-то вроде этого:

?- elsort([d,s,a,[r,t,h]],X). 
X = [a, d, s, [h, r, t]].

Но я получаю:

?- elsort([d,s,a,[r,t,h]],X).
X = [a, d, s, [r, t, h]].

Мой код:

elsort([],[]).
elsort([A|B],C):-
    elsort(B,D),
    elsortx(A,D,C).

elsortx(A,[X|B],[X|C]):-
    order(X,A),
    !,
    elsortx(A,B,C).
elsortx(A,B,[A|B]).

order(A,A2):-
    A @< A2.

Спасибо за помощь.


list prolog sublist
person Darja    schedule 05.11.2014    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Я бы, наверное, сделал сортировку подсписков двухэтапной операцией. Сначала выполните итерацию по исходному списку, отсортировав каждый найденный подсписок. Когда это будет сделано, отсортируйте окончательный список. Смысл в том, чтобы избежать повторной сортировки подсписков.

Что-то вроде этого:

my_sort( Unsorted , Sorted ) :-  % to sort a list of lists...
  sort_sublists( Unsorted, U ) , % - 1st pass: sort any sublists
  merge_sort( U , Sorted )       % - 2nd pass: actually sort the results
  .                              %

sort_sublists( [] , [] ) .          % an empty list has no sublists to sort
sort_sublists( [X|Xs] , [Y|Ys] ) :- % otherwise...
  list(X) ,                         % - if the head is a list
  !,                                % - eliminate the choice point
  my_sort(X,Y)                      % - and sort the head (along with its sublists)
  .                                 %
sort_sublists( [X|Xs] , [X|Ys] ).   % otherwise (the head is not a list)

merge_sort( []       , [] ) .       % an empty list is sorted.
merge_sort( [A]      , [A] ) .      % list of 1 item is sorted.
merge_sort( [A,B|Cs] , Sorted ) :-  % otherwise, to sort a list of 2 or more items...
  partition([A,B|Cs] , L , R ) ,    % - partition it into two halves.
  merge_sort( L , L1 ) ,            % - then recursively sort the left half
  merge_sort( R , R1 ) ,            % - and recursively sort the right half
  merge( L1 , R1 , Sorted )         % - then merge the two now-order halves together
  .                                 % producing the final, sorted list

partition( []       , []     , []     ) .
partition( [L]      , [L]    , []     ) .
partition( [L,R|Xs] , [L|Ls] , [R|Rs] ) :- partition(Xs,Ls,Rs) .

merge( []     , []     , []  ) .
merge( [L]    , []     , [L] ) .
merge( []     , [R]    , [R] ) .
merge( [L|Ls] , [R|Rs] , [R,L|Xs] ) :-
  compare(CC,L,R) ,
  swap(CC,L,R,Lo,Hi),
  merge(Ls,Rs,Xs)
  .

swap( < , L , R , L , R ) .
swap( > , L , R , R , L ) .
swap( = , L , R , L , R ) .

list( X     ) :- var(X) , ! , fail .
list( []    ) .
list( [_|_] ) .

Обратите внимание, что compare/3 — это встроенный предикат, который сравнивает два термина в стандартном порядке вещей и возвращает атом, один из <, =, >, каждый из которых имеет очевидное значение. Вы можете свернуть свой собственный, если хотите:

compare(<,X,Y) :- X @< Y .
compare(>,X,Y) :- X @> Y .
compare(=,X,Y) :- X == Y .
person Nicholas Carey    schedule 05.11.2014

arrow_upward
1
arrow_downward

Вам нужно будет отсортировать сам элемент, если это список, например:

elsort([A|B],C):-
  elsort(B,D),
  (is_list(A)->elsort(A, SA);SA=A),
  elsortx(SA,D,C).

Пример ввода:

 ?- elsort([d,s,a,[r,t,h]],X).
X = [a, d, s, [h, r, t]].
person gusbro    schedule 05.11.2014