Message Boards Message Boards

GROUPS:

Josephus Problem: queue data structure as circular list

Posted 4 months ago
1380 Views
|
4 Replies
|
9 Total Likes
|

4 Replies

enter image description here -- you have earned Featured Contributor Badge enter image description here Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!

[Heavy sigh]

The parameters of the problem are n prisoners and every k-th is removed.

--- edit ---

Expunged: [We can moreover assume that k and n are coprime since otherwise the problem does not work.] That statement was simply wrong. My bad.

--- end edit ---

I quote note 1 on the Rosetta page.

"You can always play the executioner and follow the procedure exactly as described, walking around the circle, counting (and cutting off) heads along the way. This would yield the complete killing sequence and answer the above questions, with a complexity of probably O(kn). However, individually it takes no more than O(m) to find out which prisoner is the m-th to die."

Here is the issue. The Mathematica code on that Rosetta page is quite inefficient. It has complexity O(n^2).

The queue method you provide is far more reasonable, at least for k<<n. It has complexity O(k*n), which is as advertised on the Rosetta page. One can set up and sum a certain geometric series to show this.

--- edit ---

[Ack. I messed this up.] Extra credit (mine, not Rosetta's): Can this be done more efficiently, e.g. in O(n)? I thought I knew how to but what I had was flat-out wrong. Alternatively, maybe it is provably impossible to do better?

--- end edit ---

Having messed this up yesterday, I will offer a method of reasonable complexity, O(k*n) for deleting every kth from a list on size n. The k factor does not really kick in at smallish sizes, so that's a nice advantage.

The main part of the code is straightforward. Delete every kth element, keep track of where to restart, condense the list, rinse, repeat. The endgame is tricky. Once we get into the realm where #remaining elements < k, we need to take care of the indexing. Maybe there is a more clever way.

funcJ[{j_, ll_List}, k_Integer] := 
 Module[{q, r, delposns}, {q, r} = 
   QuotientRemainder[Length[ll] - j, k];
  delposns = j + k*Transpose[{Range@q}];
  {-r, Delete[ll, delposns]}]

solveJosephus[len_, k_, keep_ : 1] := Module[
  {ll = Range[len], posn, lllen},
  {posn, ll} = 
   NestWhile[funcJ[#, k] &, {0, ll}, (Length[#[[2]]] >= keep + k) &];
  lllen = Length[ll];
  While[lllen > keep,
   posn = posn + k;
   If[posn > Length[ll],
    posn = posn - Length[ll];
    ll = ll /. 0 -> Nothing;
    posn = Mod[posn, Length[ll], 1];
    ];
   ll[[posn]] = 0;
   lllen--];
  ll /. 0 -> Nothing
  ]

I show some examples that compare to the Rosetta Stone Mathematica code.

In[435]:= 
solveJosephusRosetta[len_, k_, keep_] := 
 Nest[Most[RotateLeft[#, k]] &, Range[len], len - keep]

In[479]:=

 Table[Timing[solveJosephusRosetta[2^j, 3, 1]], {j, 15, 17}]

Out[479]= {{0.593449, {6136}}, {2.3729, {58355}}, {9.5988, {82145}}}

In[489]:= Table[Timing[solveJosephus[2^j, 3, 1]], {j, 15, 17}]

Out[489]= {{0.002549, {6136}}, {0.004045, {58355}}, {0.008657, \
{82145}}}

One sees the quadratic complexity in that Rosetta code.

If we increase the step size k we begin to see the effect that has on the O(k*n) method.

In[548]:= Table[Timing[solveJosephusRosetta[2^j, 103, 6]], {j, 15, 17}]

Out[548]= {{0.587146, {31404, 2231, 7602, 15710, 15912, 
   16352}}, {2.42677, {291, 7505, 18244, 34452, 34851, 
   35734}}, {9.69498, {6724, 21141, 42610, 75014, 75807, 77576}}}

In[546]:= Table[Timing[solveJosephus[2^j, 103, 6]], {j, 15, 17}]

Out[546]= {{0.021644, {2231, 7602, 15710, 15912, 16352, 
   31404}}, {0.016242, {291, 7505, 18244, 34452, 34851, 
   35734}}, {0.022995, {6724, 21141, 42610, 75014, 75807, 77576}}}
Posted 4 months ago

There is a typo in the original poster text here:

"Use Real and Sow to collect visualizations during the computation"

That Real wants to be Reap.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract