Some wisdom, please?
Suppose I have a list of lists of integers, say:
((0 3 1 2) (1 3 2 0) (1 2 0 3) ...)
The first and third items are circular permutations of one another.
For present purposes I want to regard circular permutations as
equivalent, and de-dup the list.
The obvious approach would seem to require, for each sublist, (1)
finding the position of the min (max) element, (2) applying the
permutation that rotates the min (max) element to a known (eg first)
position in the sublist.
Dumb Questions:
Is there some smart *recursive* way to apply a given permutation to a
list?
Is there a smarter way in general to do this de-dup?
Thanks.
In article <··········@snook.ccr-p.ida.org> ·······@ccr-p.ida.org (Frank Brickle) writes:
>Suppose I have a list of lists of integers, say:
>((0 3 1 2) (1 3 2 0) (1 2 0 3) ...)
>The first and third items are circular permutations of one another.
>For present purposes I want to regard circular permutations as
>equivalent, and de-dup the list.
>
>The obvious approach would seem to require, for each sublist, (1)
>finding the position of the min (max) element, (2) applying the
>permutation that rotates the min (max) element to a known (eg first)
>position in the sublist.
You don't need to find the min or max element -- if you're comparing two
lists, you can just use the first element of one list, and rotate that to
the beginning of the other.
(defun circular-permutation-p (list1 list2)
(let ((position (position (car list1) list2)))
(and position
(equal list1
(rotate-list (position (car list1) list2)
list2)))))
(defun rotate-list (position list)
(append (nthcdr position list) (butlast list position)))
--
Barry Margolin
System Manager, Thinking Machines Corp.
······@think.com {uunet,harvard}!think!barmar