Puzzler: function of permutation vector 
Author Message
 Puzzler: function of permutation vector

Hi there,
yesterday I read an article called "A Block-sorting Lossless
Data Compression Algorithm" by M.Burrows and D.J.Wheeler. You can find it
at
http://www.*-*-*.com/ :/pub/DEC/SRC/research-reports/SRC-124.ps.Z

At one stage of the algorithm we have a permutation vector V of the
integers from 0 to N-1. Then we define the function F for integers I and
X each in the range from 0 to N-1 as follows:

F(I,X) := X              if I=0,
          V[F(I-1,X)]    if 0 < I

(Note: we use bracket indexing and QUAD_IO=0)

We want to compute F(I,X) for all 0 <= I < N.

For example: Let V=4 0 5 1 2 3 and X=1, then
F(0,1)=1
F(1,1)=V[F(0,1)]=V[1]=0
F(2,1)=V[F(1,1)]=V[0]=4
F(3,1)=V[F(2,1)]=V[4]=2
F(4,1)=V[F(3,1)]=V[2]=5
F(5,1)=V[F(4,1)]=V[5]=3

Now, a recursive function in APL or J is immediate, of course. I am
looking for an other way...

Bernhard



Mon, 28 Sep 1998 03:00:00 GMT  
 Puzzler: function of permutation vector
Bernhard Strohmeier writes on Thursday, April 11:

Quote:
> ...
> At one stage of the algorithm we have a permutation vector V of the
> integers from 0 to N-1. Then we define the function F for integers I and
> X each in the range from 0 to N-1 as follows:

> F(I,X) := X              if I=0,
>           V[F(I-1,X)]    if 0 < I

> (Note: we use bracket indexing and QUAD_IO=0)

> We want to compute F(I,X) for all 0 <= I < N.

> For example: Let V=4 0 5 1 2 3 and X=1, then
> F(0,1)=1
> F(1,1)=V[F(0,1)]=V[1]=0
> F(2,1)=V[F(1,1)]=V[0]=4
> F(3,1)=V[F(2,1)]=V[4]=2
> F(4,1)=V[F(3,1)]=V[2]=5
> F(5,1)=V[F(4,1)]=V[5]=3

> Now, a recursive function in APL or J is immediate, of course. I am
> looking for an other way...

   f=: 4 : 'if. {.x. do. ((x.-1 0) f y.){y. else. {:x. end.' " 1
   v=: 4 0 5 1 2 3

   0 1 f v
1
   1 1 f v
0
   ((i.#v),.1) f v
1 0 4 2 5 3

   (0,.i.#v) f v
0 1 2 3 4 5
   (1,.i.#v) f v
4 0 5 1 2 3
   (2,.i.#v) f v
2 4 3 0 5 1


   0 f1 v
0 1 2 3 4 5
   1 f1 v
4 0 5 1 2 3
   2 f1 v
2 4 3 0 5 1

   (i.10) f1 v
0 1 2 3 4 5
4 0 5 1 2 3
2 4 3 0 5 1
5 2 1 4 3 0
3 5 0 2 1 4
1 3 4 5 0 2
0 1 2 3 4 5
4 0 5 1 2 3
2 4 3 0 5 1
5 2 1 4 3 0

The i,j entry of this table is F(i,j,v).  Staring at this table,
one soon realizes that the rows of the table are i.n, v{i.n,
v{v{i.n, v{v{v{i.n, etc.  Therefore, the rows of the table can be
computed via {/\(m,n)$v, and are distinct up to the order of v
(and repeats cyclically thereafter).  The order of a permutation
is the LCM of its cycle lengths.  Thus:



   [ p=. 18 ? 18
15 4 8 7 10 12 3 11 0 5 13 1 17 16 6 9 14 2
   C. p
+------------------------+------------------+
|16 14 6 3 7 11 1 4 10 13|17 2 8 0 15 9 5 12|
+------------------------+------------------+
   #&> C. p
10 8
   *./ #&> C. p
40
   ord p
40

   (f2 p) -: (i.40) f1 p
1

1

   m=.f2 p
   $m
40 18
   ?40 18
28 13
   ((<28 13){m) -: 28 13 f p
1

   test=: (< { m"_) -: [ f p"_  
   test ?$m
1
   test"1 ?3 10 2$$m
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

Finally, the original formulation specifies that in F(I,X,V),
I and X are each in the range 0 to _1+N=.#V, but the function
is well-defined for any non-negative I.  Moreover, for a
permutation whose order is greater than its length (as in the
example above), F needs to be evaluated on I greater than N to
capture its complete behaviour.



Mon, 28 Sep 1998 03:00:00 GMT  
 Puzzler: function of permutation vector
Roger Hui writes on Thursday, April 11:

Quote:
> The i,j entry of this table is F(i,j,v).  Staring at this table,
> one soon realizes that the rows of the table are i.n, v{i.n,
> v{v{i.n, v{v{v{i.n, etc.  Therefore, the rows of the table can be
> computed via {/\(m,n)$v, and are distinct up to the order of v
> (and repeats cyclically thereafter).  The order of a permutation
> is the LCM of its cycle lengths.  Thus:




Given that the computation is i.n, v{i.n, v{v{i.n, v{v{v{i.n,
there is a more direct and shorter expression of it, using the
power operator ^: .  Thus:


   [ p=. 18 ? 18
15 4 8 7 10 12 3 11 0 5 13 1 17 16 6 9 14 2
   (f2 -: f3) p
1

1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1



Mon, 28 Sep 1998 03:00:00 GMT  
 Puzzler: function of permutation vector
Roger Hui writes on Thursday, April 11:

Quote:

> f  =: 4 : 'if. {.x. do. ((x.-1 0) f y.){y. else. {:x. end.' " 1




In other words, the computation is the subgroup generated by p.
I had previously solved this problem in a different way in my
APL87 paper, "Some Uses of { and }", Section 4.4.  (I am
pleased to note that I can express the computation more neatly
in J in 1996 than in dictionary APL in 1987.)


with the identity permutation as the first row, computes its
verb table with the group operation {"1, and produces a new
matrix of the unique permutations resulting therefrom, in order.  
Thus:

   [ p=: 18?18
15 4 8 7 10 12 3 11 0 5 13 1 17 16 6 9 14 2
   [ m=: (i.#p),: p
 0 1 2 3  4  5 6  7 8 9 10 11 12 13 14 15 16 17
15 4 8 7 10 12 3 11 0 5 13  1 17 16  6  9 14  2


   $m
2 18
   $g m
3 18
   $g g m
5 18
   $g g g m
9 18
   $g^:3 m
9 18
   $g^:4 m
17 18
   $g^:5 m
33 18
   $g^:6 m
40 18
   $g^:7 m
40 18
   $g^:_ m
40 18
   ord p
40



1
   (f4 -: f2) p
1
   (f4 -: f3) p
1



Tue, 29 Sep 1998 03:00:00 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Fwd: re: Puzzler: Permutations and Anagrams

2. Puzzler: Permutations and Anagrams

3. Puzzler: Permutations and Anagrams

4. Puzzler: Permutations and Anagrams

5. Linked list to Permutation vector

6. Puzzler: Comparing Functions

7. no vector = vector*vector in BLAS?

8. all-permutations is faster than permutation

9. A permutation on permutations

10. Permutations function need

11. composing functions and permutations

12. a question on math functions re points/vectors

 

 
Powered by phpBB® Forum Software