Skip,
for s r jose n,
s r ({:@[ < ]) n is to test whether n > r.
If n<=r, then no one need to be killed, so the answer is i.@{:@[ ( = i.r).
if n>r, s r jose n = (s + (s r jose (n-1)) mod n, which is (] | {.@[ + [ $: _1
+ ]).
It is like every time one get killed, we rebase the index 0 to the one just
after the one get killed, and try to figure out if that one was not killed,
what are their previous indices. see
http://en.wikipedia.org/wiki/Josephus_problem#The_general_case.
This is not tail recursion, so can get stack-overflow. BTW, does J has tail
recursion optimization?
When r = 1,there is a neat format of Josephus2 =: 4 : '(|x&+)/i.->:y', for 3
Josephus2 20,
this is like 20 (| 3&+) 19 (| 3&+) 18 ...... 1(| 3&+) 0.
for r >1, for 3 4 Josephus2 20, it could be something like 17 (| 3&+) 16 (|
3&+) 15 ...... 1(| 3&+) (0 1 2 3)
But I dont know how to write to to a simple formula,since (| 3&+) has to be
stopped before 0, and (0 1 2 3) has to be treated as a whole.
________________________________
From: Skip Cave <[email protected]>
To: [email protected]
Sent: Saturday, May 4, 2013 1:42 AM
Subject: Re: [Jprogramming] rosettacode
Very nice Elton and Jose! I had a bug in my explicit formula, as well as
having some extra variables I didn't need. So I simplified my formula and
changed the index to the "Mayan Way" (zero index).
jose1=: 4 : 0
k =. y - 1{x NB. k is the number of "kills"
L =. i. y NB. L is the position list
whilst. k =. k-1 do.
L =. (<:0{x) |. L NB. Rotate by the skip number
L =. }. L NB. Remove the dead index.
end.
)
So now my results match Jose and Elton's tacit versions.
3 4 jose1 20
19 1 7 12
5 1 jose1 200
112
7 10 jose1 345
283 287 295 319 72 92 93 137 175 224
Interestingly:
Ts '7 10 jose1 345'
0.0028602 6464
Ts '7 10 jose 345'
0.0010386 65664
Ts '3 7 jose1 10000'
0.0823621 133440
Ts '3 7 jose 10000'
|stack error: jose
| 3 7 jose 10000
Where jose1 is my explicit version, and jose is Elton's tacit version.
Elton, I'm trying to parse through your tacit version to understand how it
works. Could you break it appart, and explain what is going on in there?
Is it possible to implement my explicit algorithm in a tacit expression
that won't get a stack error with large numbers?
Skip
On Fri, May 3, 2013 at 7:13 PM, elton wang <[email protected]> wrote:
> modified from Jose's recursive form:
>
> jose =. i.@{:@[`(] | {.@[ + [ $: _1 + ])@.({:@[ < ])
>
>
--
Skip Cave
Cave Consulting LLC
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
