Я полный любитель Пролога, поэтому мой вопрос может быть очень простым. Я хочу автоматически сгенерировать список от 1 до N, а затем разделить его на четные и нечетные только из одного целочисленного ввода (поэтому я не ввожу список вручную). Допустим, я ввожу 5, тогда результат должен быть таким: Х = [1,3,5] Y = [2,4] Неважно, кто из них X, кто Y.
Как мне решить эту проблему?
Я знаю, что встроенная функция для создания списка numlist(1,5,L).
Я также нашел ответ о том, как разделить список здесь
Я пытался объединить эти два вот так
separate_even_odd(N) :- numlist(1,N,L), separate_even_odd(L, X, Y).
Затем вызовите функцию separate_even_odd(5).
Все, что у меня есть, это правда.
В конце концов, я хочу добавить нечетный список к четному, но давайте перенесем это в другую историю. А пока я просто хочу, чтобы это было разделено.
@TessellationHeckler, ты прав. Этот момент на самом деле является самым важным, что я узнал из этого вопроса и ответов. Я рад, что спрашиваю здесь.
SWI-Prolog имеет библиотечный предикат раздела/4, который, кажется, сделан для удовлетворения ваших потребностей:
separate_even_odd(Integers, Even, Odd) :-
partition(integer_is_even, Integers, Even, Odd).
integer_is_even(I) :- I mod 2 =:= 0.
Вместо предиката службы integer_is_even
/1 мы могли бы также использовать лямбда-библиотеку (yall):
separate_even_odd(Integers, Even, Odd) :-
partition([I] >> (I mod 2 =:= 0), Integers, Even, Odd).
и мы получаем
?- numlist(1,5,L), separate_even_odd(L, Even, Odd).
L = [1, 2, 3, 4, 5],
Even = [2, 4],
Odd = [1, 3,
Чтобы проиллюстрировать некоторые необычные конструкции Пролога (унификация и if/then/else), взгляните на простую реализацию в процедурном стиле без библиотечных предикатов:
list_with_separate_even_odd(IntegerLow, IntegerHigh, Even, Odd) :-
( IntegerLow > IntegerHigh
-> Even = [], Odd = []
; ( IntegerLow mod 2 =:= 0
-> Even = [IntegerLow|RestEven], Odd = RestOdd
; Even = RestEven, Odd = [IntegerLow|RestOdd]
),
LowSucc is IntegerLow + 1,
list_with_separate_even_odd(LowSucc, IntegerHigh, RestEven, RestOdd)
).
Обратите особое внимание на то, как =/2 выполняет объединение, а не присвоение.
Альтернативный метод с введением в списки различий из-за «В конечном итоге я хочу добавить нечетный список в четный список»:
between_evens_odds(Upper, Evens, EvensTail, Odds) :-
integer(Upper),
Upper @>= 1,
between_evens_odds_(1, Upper, Evens, EvensTail, Odds).
between_evens_odds_(Upto, Upper, Evens, EvensTail, Odds) :-
compare(Comp, Upper, Upto),
between_evens_odds_comp_(Comp, Upto, Upper, Evens, EvensTail, Odds).
between_evens_odds_comp_(<, _Upto, _Upper, EvensTail, EvensTail, []).
% Started with 1, so final number will also be odd
between_evens_odds_comp_(=, Upto, _Upper, EvensTail, EvensTail, [Upto]).
between_evens_odds_comp_(>, Upto, Upper, [Upto1|Evens], EvensTail, [Upto|Odds]) :-
Upto1 is Upto + 1,
Upto2 is Upto + 2,
between_evens_odds_(Upto2, Upper, Evens, EvensTail, Odds).
Результаты в swi-прологе:
% Using 0 as an example - it of course fails
?- between(0, 6, Upper), between_evens_odds(Upper, Ev, EvT, Od).
Upper = 1,
Ev = EvT,
Od = [1] ;
Upper = 2,
Ev = [2|EvT],
Od = [1] ;
Upper = 3,
Ev = [2|EvT],
Od = [1, 3] ;
Upper = 4,
Ev = [2, 4|EvT],
Od = [1, 3] ;
Upper = 5,
Ev = [2, 4|EvT],
Od = [1, 3, 5] ;
Upper = 6,
Ev = [2, 4, 6|EvT],
Od = [1, 3, 5].
Вот волшебство списков различий — поскольку мы уже перебрали список эвенов до конца, мы можем захватить хвост эвенов, а не перебирать все эвены еще раз, используя append
, для производительности:
?- between_evens_odds(5, Ev, EvT, Od), EvT = Od.
Ev = [2, 4, 1, 3, 5],
EvT = Od, Od = [1, 3, 5].
Простая и эффективная реализация:
separate_odd_even(N, Odd, Even) :-
odd_even_loop(1, N, Odd, Even).
odd_even_loop(M, N, Odd, Even) :-
Bool is sign(abs(N-M)), % reify equality between M and N to avoid non-determinism
odd_even_case(Bool, M, N, Odd, Even).
odd_even_case(0, M, _, [M], []). % M and N are equal
odd_even_case(1, M, N, [M|Odd], Even) :- % M and N are different
M1 is M + 1,
odd_even_loop(M1, N, Even, Odd).
Примеры:
?- separate_odd_even(8, O, E).
O = [1, 3, 5, 7],
E = [2, 4, 6, 8].
?- separate_odd_even(9, O, E).
O = [1, 3, 5, 7, 9],
E = [2, 4, 6, 8].
?- separate_odd_even(3, [1,3], E).
E = [2].
?- separate_odd_even(3, O, [2]).
O = [1, 3].
?- separate_odd_even(3, [1,3], [2]).
true.
?- separate_odd_even(3, [1,2], [3]).
false.
?- time(separate_odd_even(1000000, O, E)).
% 3,000,001 inferences, 0.313 CPU in 0.312 seconds (100% CPU, 9600003 Lips)
O = [1, 3, 5, 7, 9, 11, 13, 15, 17|...],
E = [2, 4, 6, 8, 10, 12, 14, 16, 18|...].
Не нужно abs
, а лучше без, чтобы справиться, например. separate_odd_even(-1, O, E).
Использование compare/3
быстрее, чем Bool is sign(N-M)
, в swi-prolog.
@brebs Без использования abs
у вас действительно нет общего способа овеществить равенство между двумя целыми числами, поскольку вычитание даст три возможных результата (0
, -1
или +1
), а не только два (0
или 1
), как ожидается в предикате odd_even_case/5
. Во всяком случае, для конкретных случаев это может сработать.
@brebs Аналогично, используя compare/3
, вы получите =
, <
или >
в качестве возможных результатов, и это, как правило, может привести к избыточности в коде, которому нужно только знать, равны ли два целых числа или нет. Но в данном конкретном случае я согласен с вами, что использование этого предиката может сделать мой код быстрее, чем ваш.
«встроенная функция для создания списка —
numlist(1,5,L).
» — посмотрите, что там делаетL
. «Тогда вызовите функциюseparate_even_odd(5).
Все, что у меня есть, это True». - убедитесь, что у вас нетL
или чего-то подобного, чтобы использовать его для получения каких-либо других результатов.