Re: Rearranging based on permutation of indices
- From: Pascal Bourguignon <pjb@xxxxxxxxxxxxxxxxx>
- Date: Tue, 03 Oct 2006 01:56:27 +0200
mailto.anand.hariharan@xxxxxxxxx writes:
Yes, in the context of the actual real world problem, it should be
possible for me to have N-bits for house-keeping. I believe I
understood Pascal's solution that used the additional bits, while I
confess I could not understand how the two strictly O(1) solutions
worked. I will ruminate on those further before I revert back to the
group asking for clarifications.
When you have a permutation, you can see it as a bunch of disjoint
looping strings that pass thru each position.
For example, three cycles of two nodes:
1 2 3 4 5 6
4 3 2 1 6 5
*<----------+
| |
| *<--+ | *<--+
| | | | | |
| +-->* | +-->*
| |
+---------->*
There could be longer cycles, here with two cycles of three nodes:
1 2 3 4 5 6
3 1 2 5 6 4
*-->*-->* *<--*<--*
^ | | ^
| | | |
+-------+ +-------+
Now, when we process a permutation, with the index i and B[i]:
i: 1 2 3 4 5 6
B[i]: 3 1 2 5 6 4
the idea is that all the cycles that have some node before i have
already been permuted and mustn't be processed again, while cycles
that have all their node after i need to be permuted.
So the first error I had was in cycle-aready-used-p. Let's use
instead cycle-already-seen-p which finds the minimum index in the
cycle and compares it with the current 'base' index:
(defun cycle-already-seen-p (permutation base)
(/= base
(loop ; this loop returns the minimum i
:for i = (aref permutation base) :then (aref permutation i)
:minimize i
:while (/= base i))))
The second error I had, was in the permutation of the cycle. In the
O(n) in space version, we could permute by swapping each element in
turn, but the idea was to rotate the whole cycle at once. This is
where we use O(1), the temporary storage for an element of the cycle
while we permute it:
(defun permute-cycle (vector permutation cycle)
(loop
:with temp = (aref vector cycle)
:for i = cycle :then j
:for j = (aref permutation i)
:until (= j cycle)
:do (setf (aref vector i) (aref vector j))
:finally (setf (aref vector i) temp))
(format t "~% ~D ~S ~S" cycle vector permutation))
Finally, we can permute the vector, cycle per cycle for each cycle
that hasn't already been permuted:
(defun permute-vector (vector permutation)
(format t "~% ~S ~S" vector permutation)
(loop
:for i :from 1 :below (length permutation)
:unless (cycle-already-seen-p permutation i)
:do (permute-cycle vector permutation i)))
PERMUTE[461]> (let ((vector (vector 0 'a 'b 'c 'd 'e 'f))
(permutation (vector 0 3 1 2 5 6 4)))
(permute-vector vector permutation)
(values vector permutation))
#(0 A B C D E F) #(0 3 1 2 5 6 4)
1 #(0 C A B D E F) #(0 3 1 2 5 6 4)
4 #(0 C A B E F D) #(0 3 1 2 5 6 4)
#(0 C A B E F D) ;
#(0 3 1 2 5 6 4)
PERMUTE[462]> (let ((vector (vector 0 'a 'b 'c 'd 'e 'f 'g 'h))
(permutation (vector 0 4 1 6 2 7 3 8 5)))
(permute-vector vector permutation)
(values vector permutation))
#(0 A B C D E F G H) #(0 4 1 6 2 7 3 8 5)
1 #(0 D A C B E F G H) #(0 4 1 6 2 7 3 8 5)
3 #(0 D A F B E C G H) #(0 4 1 6 2 7 3 8 5)
5 #(0 D A F B G C H E) #(0 4 1 6 2 7 3 8 5)
#(0 D A F B G C H E) ;
#(0 4 1 6 2 7 3 8 5)
--
__Pascal Bourguignon__ http://www.informatimago.com/
"You cannot really appreciate Dilbert unless you read it in the
original Klingon"
.
- References:
- Rearranging based on permutation of indices
- From: mailto . anand . hariharan
- Re: Rearranging based on permutation of indices
- From: mailto . anand . hariharan
- Rearranging based on permutation of indices
- Prev by Date: Re: Donating programming [OT: reading between the lines]
- Next by Date: Re: Youthful managers, development, and methodology....a conundrum
- Previous by thread: Re: Rearranging based on permutation of indices
- Next by thread: Re: Hamberger Principle as a mind exercise
- Index(es):
Relevant Pages
|
