Как написать findall без перестановок?

Question

Я хочу написать программу, которая оценивает, какие комбинации предметов можно переносить в пределах определенной емкости мешка. Важная часть программы - выбить все перестановки возможностей. Программа должна выдавать каждую возможность один раз, а не их перестановки. Вот пример запрос:

?- place(Possibility, 2). 
Possibility = [water]; 
Possibility = [flower]; 
Possibility = [paper]; 
Possibility = [meat]; 
Possibility = [wood]; 
Possibility = [glass]; 
Possibility = [water, flower]; 
Possibility = [water, paper]; 
Possibility = [flower, paper]. 

Мой код до сих пор:

% item(Name, Space) 
item(water, 1). 
item(flower, 1). 
item(paper, 1). 
item(meat, 2). 
item(wood, 2). 
item(glass, 2). 
item(stone, 3). 
item(gold, 3). 
item(metal, 3). 
item(platin, 4). 

% maximum capacity of bag 
maxcapacity(10). 

place(Possibility, Capacity) :- 
    maxcapacity(MaxCapacity), 
    between(1, MaxCapacity, Capacity), 
    possibilities(Capacity, [], Possibility). 

possibilities(Capacity, Acc, Acc) :- 
    \+ (space(Possibility, [], 0, Capacity), sort(Possibility, SortedPossibility), \+ member(SortedPossibility, Acc)). 
possibilities(Capacity, Acc, PossibilityList) :- 
    space(Possibility, [], 0, Capacity), 
    sort(Possibility, SortedPossibility), 
    not(member(SortedPossibility, Acc)), 
    Acc1 = [SortedPossibility|Acc], 
    possibilities(Capacity, Acc1,PossibilityList). 

space(Acc, Acc, Space, MaxCapacity) :-    
    Space =< MaxCapacity, 
    Acc \= []. 
space(Possibility, Acc, Space, MaxCapacity) :- 
    item(Item, ItemSpace), 
    not(member(Item, Acc)), 
    NewSpace is Space + ItemSpace, 
    NewSpace =< MaxCapacity, 
    Acc1 = [Item|Acc], 
    space(Possibility, Acc1, NewSpace, MaxCapacity). 

Я пытался выгнать перестановки сортировки, но программа все еще дает мне все перестановки и помещает комбинацию записи как-то в список. Программа должна работать так же, как в примере выше.

Я бы очень признателен за любую помощь!

Answer 1

Ваша проблема заключается в том, что ваша программа создает списки возможностей, а не возможности. Вместо этого код ниже найдет возможность, затем отступит, чтобы найти следующую возможность.

possibilities(_, Current, Current)possibilities(_, Current, Current) объединяет текущую возможность работы с запросом, чтобы вернуть в результате текущую возможность. Current \= [] используется для устранения пустого мешка как возможности (исходя из ваших ожидаемых результатов).

После возврата, possibilities(Capacity, [], Possibility) используется для поиска начального элемента в сумке.Первый элемент, который помещается в сумке, будет выбран, и мы рекурсируем (сначала к пункту унификации выше, а затем к частично полной сумме ниже). Как только все возможности были исчерпаны этим предметом в сумке, мы возвращаемся назад и находим следующий предмет, который будет соответствовать.

possibilities(Capacity, [Current|Rest], Possibility) по существу работает так же, как possibilities(Capacity, [], Possibility), но с еще одной проверкой, чтобы гарантировать, что мы получаем только возможности в алфавитном порядке, чтобы исключить перестановки. Затем это повторяется, как указано выше.

(В качестве примечания стороны, если вы хотите, чтобы хранить, скажем, две воды в сумке, просто измените A @< Current на A @=< Current).

item(water, 1). 
item(flower, 1). 
item(paper, 1). 
item(meat, 2). 
item(wood, 2). 
item(glass, 2). 
item(stone, 3). 
item(gold, 3). 
item(metal, 3). 
item(platin, 4). 

% maximum capacity of bag 
maxcapacity(10). 

place(Possibility, Capacity) :- 
    maxcapacity(MaxCapacity), 
    between(1, MaxCapacity, Capacity), 
    possibilities(Capacity, [], Possibility). 

possibilities(_, Current, Current) :- 
    Current \= []. 

possibilities(Capacity, [], Possibility) :- 
    item(A, B), 
    B =< Capacity, 
    NewCapacity is Capacity - B, 
    possibilities(NewCapacity, [A], Possibility). 

possibilities(Capacity, [Current|Rest], Possibility) :- 
    item(A, B), 
    B =< Capacity, 
    NewCapacity is Capacity - B, 
    A @< Current, 
    possibilities(NewCapacity, [A,Current|Rest], Possibility). 

Answer 2

Вы уже в основном используете свой предикат space/4, но затем вы добавляете лишние вещи в possibilities/3, который «как-то помещает комбинации предметов в список», хотя вы этого не хотите.

Итак, давайте посмотрим на пример space/4 непосредственно:

?- space(Possibility, [], 0, 2). 
Possibility = [water] ; 
Possibility = [flower, water] ; 
Possibility = [paper, water] ; 
Possibility = [flower] ; 
Possibility = [water, flower] ; 
Possibility = [paper, flower] ; 
Possibility = [paper] ; 
Possibility = [water, paper] ; 
Possibility = [flower, paper] ; 
Possibility = [meat] ; 
Possibility = [wood] ; 
Possibility = [glass] ; 
false. 

Заметим, что вы получите решения емкости 1, а также решения емкости 2. Использование maxcapacity/1 и between/3 подсказывает мне, что вы бы только требуется решение емкости ровно 2 здесь. Вы можете изменить =< к = в первом пункте space/4, чтобы получить это:

?- space(Possibility, [], 0, 2). 
Possibility = [flower, water] ; 
Possibility = [paper, water] ; 
Possibility = [water, flower] ; 
Possibility = [paper, flower] ; 
Possibility = [water, paper] ; 
Possibility = [flower, paper] ; 
Possibility = [meat] ; 
Possibility = [wood] ; 
Possibility = [glass] ; 
false. 

Теперь мы можем исключить перестановки в каждый решение по отдельности, а не, как вы делали, собирать все решения в списке и попытаться работать с этим, что сложнее.

Устранение нежелательных перестановок означает выбор репрезентативной перестановки и игнорирование всех остальных. Например, можно выбрать строго возрастающую (то есть, в алфавитном порядке) перестановку в качестве представителя:

?- space(Possibility, [], 0, 2), increasing(Possibility). 
Possibility = [flower, water] ; 
Possibility = [paper, water] ; 
Possibility = [flower, paper] ; 
Possibility = [meat] ; 
Possibility = [wood] ; 
Possibility = [glass] ; 
false. 

increasing/1 предикат может быть определен следующим образом:

increasing([]). 
increasing([_]). 
increasing([X,Y|Xs]) :- 
    X @< Y, 
    increasing([Y|Xs]). 

С этим, вы можете выбросить ваш предикат possibilities/3 и обобщите запрос выше, чтобы ввести в ваше определение place/2.