I have a puzzling problem, that it seems that I cannot handle:
given a list
(setq mylist '((1 2) (2 1 3 4) (3 2 4) (4 2 3 5) (5 4))
given that the list reflects relations of the
items 1 : (2) (with item 2)
2 : (1 3 4) (with items 1 3 & 4)
3 : (2 4) ... (A)
4 : (2 3 5) ...
and 5 : (4) ...
How could I expand this list into a one that expands all the respective
relations that each item will give?
If I do this expansion by hand it should be:
as follows
1st expansion:
1 : ( 1 3 4) when 1 could be ommited as it is itself to
become --> ( 3 4) }
2 : ( (2) (2 4) (2 3 5)) when 2 could be ommited
again --> ((4) (3 5)) }
3 : ( (1 3 4) (2 3 5)) when 3 could be
ommited --> ((1 4) (2 5)) } (B)
4 : ( (1 3 4) (2 4) (4) when 4
goes --> ((1 3) (2)) }
5 : ( (2 3 5) ) when 5
goes --> ((2 3)) }
2nd expansion:
1 : ((2 4) (2 3 5)) when 2 could be ommited because is a relation
allready recorded in (A)
2 : ((2 3 5) ((2 4) (4)) when 2 couldbe ommited as itself, 3 as has
been recorded in (A), 4 and 5 recorded in (B)
hence ((4) (3 5)) would be the ultimate expansion
3 : (((2) (2 3 5)) ((1 3 4) (4)) and for the same reasons expansion (B)
is the ultimate
4 : and for similar reasons here the previous is the ultimate expansion
5 : ((1 3 4) (2 4)) here this is the ultimate because the relation
with 1 has not been previously recorded.
Trying to solve a path proximity algorithm any algorith that would
calculate the shortest path recording how many steps
one takes to go from A to B would be apreciated...
thanks in advance.
please email any responce to ········@entasis.hellas.net
Mattheos Papavasiliou wrote:
>
> I have a puzzling problem, ... given a list ...
Here's one solution. Loop and standard tail recursion would also be
obvious implementations.
(defun transitive-neighbors (neighbors-alist)
;;neighbors-alist is an alist indicating for each node its
;;nearest neighbors. This function must return an alist of the
;;neighbors (non-circular) just one removed grouped by their
;;transitive but unmentioned jumping point. What's not clear in the
;;spec is whether there should be any further cleanup other than
;;strict circularity.
(mapcar
#'(lambda (entry)
(let ((this-node (car entry)))
(cons this-node
(delete nil
(mapcar
#'(lambda (neighbor)
(remove this-node
(cdr (assoc
neighbor
neighbors-alist))))
(cdr entry))))))
neighbors-alist))
(transitive-neighbors '((1 2) (2 1 3 4) (3 2 4) (4 2 3 5) (5 4)))
=> ((1 (3 4)) (2 (4) (3 5)) (3 (1 4) (2 5)) (4 (1 3) (2)) (5 (2 3)))
--
Donald H. Mitchell, PhD, PMP ··········@smartproject.com
Proactive Solutions, Inc. 412.835.2410
5858 Horseshoe Dr. 412.835.2411 (fax)
Bethel Park, PA 15102 http://home.earthlink.net/~smartproject