Skip to main content

programming - How to correct my code for solving the Josephus problem?


Problem Description


Recently, I have been reading the book Schaum's Outline of Mathematica (2nd Edition), where I encountered the problem:




Flavius Josephus was a Jewish historian of the first century. He wrote about a group of ten Jews in a cave who, rather than surrender to the Romans, chose to commit suicide, one by one. They formed a circle and every other one was killed. Who was the lone survivor?



The author's solution:


list = Range[10];
While[Length[list] > 1, list = Rest[RotateLeft[list]]];
list


{5}




However, I know it is not efficient to use the procedural methods such as Do, While, etc. Rather, I want to use a functional method like NestWhile, Nest, or FixedPoint to solve the problem.


My solutions:


Method 1:


list = Range @ 10; 
NestList[Rest @ RotateLeft[#] &, list, 9]


 {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 
{3, 4, 5, 6, 7, 8, 9, 10, 1},

{5, 6, 7, 8, 9, 10, 1, 3},
{7, 8, 9, 10, 1, 3, 5},
{9, 10, 1, 3, 5, 7},
{1, 3, 5, 7, 9},
{5, 7, 9, 1},
{9, 1, 5},
{5, 9},
{5}}

Furthermore, this method has the flaw that I must give the number of iterations. In fact, sometimes that is unknown.



Method 2:


list = Range @10;
FixedPoint[If[Length@# != 1 &, Rest @ RotateLeft[#] &], list]

Unfortunately, method 2 doesn't work.


Method 3:


 list = Range @ 10;
NestWhileList[Rest @ RotateLeft[#] &, list, Length@list != 1]



{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}

So my question is: what is a good way to do it?



Answer



NestWhile[Rest @ RotateLeft @ # &, Range @ 10, Length @ # > 1 &]


{5}



FixedPoint[If[Length @ # > 1, Rest @ RotateLeft[#], #] &, Range @ 10]


Edit


Historical note: As far as I can remember, Josephus roulette (a plain treason to his companions) consisted of killing every third person.


FixedPoint[If[Length@# != 1, Rest@RotateLeft[#, 2], #] &, Range@10]


{4}



Note: The direction is important. RotateRight[] will select another victim.


Comments

Popular posts from this blog

front end - keyboard shortcut to invoke Insert new matrix

I frequently need to type in some matrices, and the menu command Insert > Table/Matrix > New... allows matrices with lines drawn between columns and rows, which is very helpful. I would like to make a keyboard shortcut for it, but cannot find the relevant frontend token command (4209405) for it. Since the FullForm[] and InputForm[] of matrices with lines drawn between rows and columns is the same as those without lines, it's hard to do this via 3rd party system-wide text expanders (e.g. autohotkey or atext on mac). How does one assign a keyboard shortcut for the menu item Insert > Table/Matrix > New... , preferably using only mathematica? Thanks! Answer In the MenuSetup.tr (for linux located in the $InstallationDirectory/SystemFiles/FrontEnd/TextResources/X/ directory), I changed the line MenuItem["&New...", "CreateGridBoxDialog"] to read MenuItem["&New...", "CreateGridBoxDialog", MenuKey["m", Modifiers-...

How to thread a list

I have data in format data = {{a1, a2}, {b1, b2}, {c1, c2}, {d1, d2}} Tableform: I want to thread it to : tdata = {{{a1, b1}, {a2, b2}}, {{a1, c1}, {a2, c2}}, {{a1, d1}, {a2, d2}}} Tableform: And I would like to do better then pseudofunction[n_] := Transpose[{data2[[1]], data2[[n]]}]; SetAttributes[pseudofunction, Listable]; Range[2, 4] // pseudofunction Here is my benchmark data, where data3 is normal sample of real data. data3 = Drop[ExcelWorkBook[[Column1 ;; Column4]], None, 1]; data2 = {a #, b #, c #, d #} & /@ Range[1, 10^5]; data = RandomReal[{0, 1}, {10^6, 4}]; Here is my benchmark code kptnw[list_] := Transpose[{Table[First@#, {Length@# - 1}], Rest@#}, {3, 1, 2}] &@list kptnw2[list_] := Transpose[{ConstantArray[First@#, Length@# - 1], Rest@#}, {3, 1, 2}] &@list OleksandrR[list_] := Flatten[Outer[List, List@First[list], Rest[list], 1], {{2}, {1, 4}}] paradox2[list_] := Partition[Riffle[list[[1]], #], 2] & /@ Drop[list, 1] RM[list_] := FoldList[Transpose[{First@li...

mathematical optimization - Minimizing using indices, error: Part::pkspec1: The expression cannot be used as a part specification

I want to use Minimize where the variables to minimize are indices pointing into an array. Here a MWE that hopefully shows what my problem is. vars = u@# & /@ Range[3]; cons = Flatten@ { Table[(u[j] != #) & /@ vars[[j + 1 ;; -1]], {j, 1, 3 - 1}], 1 vec1 = {1, 2, 3}; vec2 = {1, 2, 3}; Minimize[{Total@((vec1[[#]] - vec2[[u[#]]])^2 & /@ Range[1, 3]), cons}, vars, Integers] The error I get: Part::pkspec1: The expression u[1] cannot be used as a part specification. >> Answer Ok, it seems that one can get around Mathematica trying to evaluate vec2[[u[1]]] too early by using the function Indexed[vec2,u[1]] . The working MWE would then look like the following: vars = u@# & /@ Range[3]; cons = Flatten@{ Table[(u[j] != #) & /@ vars[[j + 1 ;; -1]], {j, 1, 3 - 1}], 1 vec1 = {1, 2, 3}; vec2 = {1, 2, 3}; NMinimize[ {Total@((vec1[[#]] - Indexed[vec2, u[#]])^2 & /@ R...