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=0
F(2,1)=V[F(1,1)]=V=4
F(3,1)=V[F(2,1)]=V=2
F(4,1)=V[F(3,1)]=V=5
F(5,1)=V[F(4,1)]=V=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=0
> F(2,1)=V[F(1,1)]=V=4
> F(3,1)=V[F(2,1)]=V=2
> F(4,1)=V[F(3,1)]=V=5
> F(5,1)=V[F(4,1)]=V=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

 Page 1 of 1 [ 4 post ]

Relevant Pages