This sounds and almost feels like a job for Prolog, but I want to do
it in Common Lisp without having to dive into a Prolog implementation
if I can avoid it.
Here is what I need to do:
Given a database of pairings among various types of items, and given a
template for a combination of items of various types, I want to
generate (either one at a time or as a list) all the possible
combinations that match the template and all of the pairings.
For instance, consider this database:
Items:
(roast-chicken :type :entree)
(steak :type :entree)
(dinner-salad :type :salad)
(greek-salad :type :salad)
(cheesecake :type :dessert)
(creme-brulee :type :dessert)
(pinot-noir :type :wine)
(chardonnay :type :wine)
Pairings:
(roast-chicken . dinner-salad)
(roast-chicken . greek-salad)
(roast-chicken . cheesecake)
(roast-chicken . chardonnay)
(steak . dinner-salad)
(steak . creme-brulee)
(steak . pinot-noir)
Template (there could be other templates):
(entree wine &optional salad dessert)
Results:
(roast-chicken chardonnay)
(roast-chicken chardonnay dinner-salad)
(roast-chicken chardonnay dinner-salad cheesecake)
(roast-chicken chardonnay greek-salad)
(roast-chicken chardonnay greek-salad cheesecake)
(roast-chicken chardonnay cheesecake)
(steak pinot-noir)
(steak pinot-noir dinner-salad)
(steak pinot-noir dinner-salad creme-brulee)
(steak pinot-noir creme-brulee)
Has anyone solved this problem already (preferably without Prolog)?
Do you have any recommendations for how to store the various parts of
the database and how to generate the results? I would also like to be
able to generate the results after manually filling in one or more
parts of the template (such as telling the system I want to eat
chicken and cheesecake and asking it what else I can use).
Thanks!
what you need is to group the items of the various types, according to
the template, and generate the cross-product of the resulting sets:
ex:
CL-USER> (-x-prod '((roast-chicken steak) (pinot-noir chardonnay)
(dinner-salad greek-salad) (cheesecake creme-brulee)))
((ROAST-CHICKEN PINOT-NOIR DINNER-SALAD CHEESECAKE)
(ROAST-CHICKEN PINOT-NOIR DINNER-SALAD CREME-BRULEE)
(ROAST-CHICKEN PINOT-NOIR GREEK-SALAD CHEESECAKE)
(ROAST-CHICKEN PINOT-NOIR GREEK-SALAD CREME-BRULEE)
(ROAST-CHICKEN CHARDONNAY DINNER-SALAD CHEESECAKE)
(ROAST-CHICKEN CHARDONNAY DINNER-SALAD CREME-BRULEE)
(ROAST-CHICKEN CHARDONNAY GREEK-SALAD CHEESECAKE)
(ROAST-CHICKEN CHARDONNAY GREEK-SALAD CREME-BRULEE)
(STEAK PINOT-NOIR DINNER-SALAD CHEESECAKE)
(STEAK PINOT-NOIR DINNER-SALAD CREME-BRULEE) ...)
here is a tail-recursive cross-product generator:
(defun x-prod (lsts)
(labels ((rec (n acc)
(cond ((< n 0) acc)
(t (rec (1- n)
(mapcan #'(lambda (e)
(mapcar #'(lambda (x-prod)
(cons e x-prod))
acc))
(nth n lsts)))))))
(if (null (cdr lsts))
lsts
(rec (- (length lsts) 2)
(mapcar #'list (car (last lsts)))))))
Ari Johnson wrote:
> This sounds and almost feels like a job for Prolog, but I want to do
> it in Common Lisp without having to dive into a Prolog implementation
> if I can avoid it.
>
> Here is what I need to do:
>
> Given a database of pairings among various types of items, and given a
> template for a combination of items of various types, I want to
> generate (either one at a time or as a list) all the possible
> combinations that match the template and all of the pairings.
>
> For instance, consider this database:
>
> Items:
> (roast-chicken :type :entree)
> (steak :type :entree)
> (dinner-salad :type :salad)
> (greek-salad :type :salad)
> (cheesecake :type :dessert)
> (creme-brulee :type :dessert)
> (pinot-noir :type :wine)
> (chardonnay :type :wine)
>
> Pairings:
> (roast-chicken . dinner-salad)
> (roast-chicken . greek-salad)
> (roast-chicken . cheesecake)
> (roast-chicken . chardonnay)
> (steak . dinner-salad)
> (steak . creme-brulee)
> (steak . pinot-noir)
>
> Template (there could be other templates):
> (entree wine &optional salad dessert)
>
> Results:
> (roast-chicken chardonnay)
> (roast-chicken chardonnay dinner-salad)
> (roast-chicken chardonnay dinner-salad cheesecake)
> (roast-chicken chardonnay greek-salad)
> (roast-chicken chardonnay greek-salad cheesecake)
> (roast-chicken chardonnay cheesecake)
> (steak pinot-noir)
> (steak pinot-noir dinner-salad)
> (steak pinot-noir dinner-salad creme-brulee)
> (steak pinot-noir creme-brulee)
>
>
>
> Has anyone solved this problem already (preferably without Prolog)?
> Do you have any recommendations for how to store the various parts of
> the database and how to generate the results? I would also like to be
> able to generate the results after manually filling in one or more
> parts of the template (such as telling the system I want to eat
> chicken and cheesecake and asking it what else I can use).
>
> Thanks!
·········@gmail.com writes:
> what you need is to group the items of the various types, according to
> the template, and generate the cross-product of the resulting sets:
>
> ex:
> CL-USER> (-x-prod '((roast-chicken steak) (pinot-noir chardonnay)
> (dinner-salad greek-salad) (cheesecake creme-brulee)))
>
> ((ROAST-CHICKEN PINOT-NOIR DINNER-SALAD CHEESECAKE)
> (ROAST-CHICKEN PINOT-NOIR DINNER-SALAD CREME-BRULEE)
> (ROAST-CHICKEN PINOT-NOIR GREEK-SALAD CHEESECAKE)
> (ROAST-CHICKEN PINOT-NOIR GREEK-SALAD CREME-BRULEE)
> (ROAST-CHICKEN CHARDONNAY DINNER-SALAD CHEESECAKE)
> (ROAST-CHICKEN CHARDONNAY DINNER-SALAD CREME-BRULEE)
> (ROAST-CHICKEN CHARDONNAY GREEK-SALAD CHEESECAKE)
> (ROAST-CHICKEN CHARDONNAY GREEK-SALAD CREME-BRULEE)
> (STEAK PINOT-NOIR DINNER-SALAD CHEESECAKE)
> (STEAK PINOT-NOIR DINNER-SALAD CREME-BRULEE) ...)
>
> here is a tail-recursive cross-product generator:
>
> (defun x-prod (lsts)
> (labels ((rec (n acc)
> (cond ((< n 0) acc)
> (t (rec (1- n)
> (mapcan #'(lambda (e)
> (mapcar #'(lambda (x-prod)
> (cons e x-prod))
> acc))
> (nth n lsts)))))))
> (if (null (cdr lsts))
> lsts
> (rec (- (length lsts) 2)
> (mapcar #'list (car (last lsts)))))))
The problem is that I don't really want just the cross-product. I
want to only have groupings that satisfy the constraints defined by
item pairings. For instance, there should not be roast chicken being
served with pinot noir. Also, a cross product ignores the template in
another way. Specifically, a cross product does not take into account
optional items, unless you use multiple templates (either
programmer-generated or program-generated) to represent the template
with each combination of optional items omitted.
It really feels like a Prolog problem, but it's not so complex that I
feel justified in bringing in all the might of Prolog and then trying
to interface the Prolog logic to the user interface.
Ari Johnson wrote:
>
> The problem is that I don't really want just the cross-product. I
> want to only have groupings that satisfy the constraints defined by
> item pairings. For instance, there should not be roast chicken being
> served with pinot noir. Also, a cross product ignores the template in
> another way. Specifically, a cross product does not take into account
> optional items, unless you use multiple templates (either
> programmer-generated or program-generated) to represent the template
> with each combination of optional items omitted.
>
> It really feels like a Prolog problem, but it's not so complex that I
> feel justified in bringing in all the might of Prolog and then trying
> to interface the Prolog logic to the user interface.
you can solve it by using the cross-product utility and filtering out
the results according to the contraints, or you can write a pattern
matching tool and a query compiler. See "On Lisp" chapter 19.
Ari Johnson <················@gmail.com> writes:
>
> Given a database of pairings among various types of items, and given a
> template for a combination of items of various types, I want to
> generate (either one at a time or as a list) all the possible
> combinations that match the template and all of the pairings.
>
> For instance, consider this database:
>
> Items:
> (roast-chicken :type :entree)
> (steak :type :entree)
> (dinner-salad :type :salad)
> (greek-salad :type :salad)
> (cheesecake :type :dessert)
> (creme-brulee :type :dessert)
> (pinot-noir :type :wine)
> (chardonnay :type :wine)
>
> Pairings:
> (roast-chicken . dinner-salad)
> (roast-chicken . greek-salad)
> (roast-chicken . cheesecake)
> (roast-chicken . chardonnay)
> (steak . dinner-salad)
> (steak . creme-brulee)
> (steak . pinot-noir)
>
> Template (there could be other templates):
> (entree wine &optional salad dessert)
>
> Results:
> (roast-chicken chardonnay)
> (roast-chicken chardonnay dinner-salad)
> (roast-chicken chardonnay dinner-salad cheesecake)
> (roast-chicken chardonnay greek-salad)
> (roast-chicken chardonnay greek-salad cheesecake)
> (roast-chicken chardonnay cheesecake)
> (steak pinot-noir)
> (steak pinot-noir dinner-salad)
> (steak pinot-noir dinner-salad creme-brulee)
> (steak pinot-noir creme-brulee)
Well, it seems that all of the pairings are based on the entree. If you
can guarantee a specific key, then you can come up with a pre-processing
algorithm that will restrict the choices. That would let you make a
new, augmented data structure from which to generate the results.
So, taking the example template, one would use the first template entry
as the key, and generate potential values as list items. For optional
items, I would make a list that also contains NIL as a marker for the
optional items. The type categories are used to map the elements from
the pairings unto template items.
So the intermediate structure for the template
(entree wine &optional salad dessert)
I would want would be:
(roast-chicken (chardonnay) (() dinner-salad greek-salad) (() cheesecake))
(steak (pinot-noir) (() dinner-salad) (() creme-brulee))
And then just use a cross-product generator on this augmented data structure.
If you have constraints that are not as simple (i.e., if the wine is
constrained by the entree, and the dessert by entree and wine, then you
would need to go to a more complicated constraint solver)
--
Thomas A. Russ, USC/Information Sciences Institute
···@sevak.isi.edu (Thomas A. Russ) writes:
> Ari Johnson <················@gmail.com> writes:
>
>>
>> Given a database of pairings among various types of items, and given a
>> template for a combination of items of various types, I want to
>> generate (either one at a time or as a list) all the possible
>> combinations that match the template and all of the pairings.
>>
>> For instance, consider this database:
>>
>> Items:
>> (roast-chicken :type :entree)
>> (steak :type :entree)
>> (dinner-salad :type :salad)
>> (greek-salad :type :salad)
>> (cheesecake :type :dessert)
>> (creme-brulee :type :dessert)
>> (pinot-noir :type :wine)
>> (chardonnay :type :wine)
>>
>> Pairings:
>> (roast-chicken . dinner-salad)
>> (roast-chicken . greek-salad)
>> (roast-chicken . cheesecake)
>> (roast-chicken . chardonnay)
>> (steak . dinner-salad)
>> (steak . creme-brulee)
>> (steak . pinot-noir)
>>
>> Template (there could be other templates):
>> (entree wine &optional salad dessert)
>>
>> Results:
>> (roast-chicken chardonnay)
>> (roast-chicken chardonnay dinner-salad)
>> (roast-chicken chardonnay dinner-salad cheesecake)
>> (roast-chicken chardonnay greek-salad)
>> (roast-chicken chardonnay greek-salad cheesecake)
>> (roast-chicken chardonnay cheesecake)
>> (steak pinot-noir)
>> (steak pinot-noir dinner-salad)
>> (steak pinot-noir dinner-salad creme-brulee)
>> (steak pinot-noir creme-brulee)
>
> Well, it seems that all of the pairings are based on the entree. If you
> can guarantee a specific key, then you can come up with a pre-processing
> algorithm that will restrict the choices. That would let you make a
> new, augmented data structure from which to generate the results.
Actually, that may have been an oversight. The pairings are based on
any two items from any two categories. I should have included more
pairings, such as (chardonnay . creme-brulee), to make this clear.
> So, taking the example template, one would use the first template entry
> as the key, and generate potential values as list items. For optional
> items, I would make a list that also contains NIL as a marker for the
> optional items. The type categories are used to map the elements from
> the pairings unto template items.
I think the way I'm headed is a recursive function of the following form.
Anyone is more than welcome to let me know if I am missing a good Lisp
idiom that I should be applying more fluently here. Thanks!
Here goes...
(defun generator (required optional items fn)
"Given 'items' already matched, 'required' additional spots to fill,
and 'optional' slots that may or may not be filled in a given
result, call 'fn' for each complete completely-filled template."
(unless required
(funcall fn items)
(mapcar (lambda (add-slot)
(generator (list add-slot) (remove add-slot optional) items fn))
optional))
(let* ((slot (car required))
(rest (cdr required))
(add-items (find-items slot items)))
(mapcar (lambda (add-item)
(generator rest optional (cons add-item items) fn))
add-items)))
(defun find-items (slot items)
"Given 'slot' to fill and 'items' that are already matched, return
a list of items that will fill that slot while matching all existing
matches."
(remove-if-not (lambda (item)
(every #'identity
(mapcar (lambda (match-item)
(matchp item match-item))
items)))
(find-all-items slot)))
(defun find-all-items (slot)
"A self-explanatory function which finds all items which could fill
'slot'."
...)
(defun matchp (item-1 item-2)
"A self-explanatory function which determines whether 'item-1' and
'item-2' match."
...)