
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.