Numberphile
has a very nice video about the classic Josephus problem. Please watch the video to understand the background of the problem first.

Queue and Counting-out Evolution

I asked my colleagues about which data structure fits best for in WL for this task because I do not see circular linked list available in the current DataStructure package.
John
pointed out that queue is quite helpful in this case. I really like his idea and find out Pop and Push can be served as looping structure. This could be a nice example about how to use data structure in WL since it is freshly introduced in V12.1.
From
Wiki
:
In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence
Initialize the abstract data structure:
In[]:=
Once[ds=CreateDataStructure["Queue"]]
Out[]=
DataStructure
Type:Queue

Assuming there are 41 members standing in circle. Starting from Number 1, every third person is killed and the weapon is passed to the next survivor. Keep doing this until there are only 2 survivors. What was there position in the beginning?
In[]:=
initial=41;​​kthKilled=3;​​survival=2;
Assign a number to each member in the group.
In[]:=
Do[ds["Push",i],{i,initial}]
The data structures in WL all carry visualization attribute so it is fairly simple to plot the diagram with the following command
In[]:=
ds["Visualization"]
Out[]=
For the member at the beginning (head of queue), if it survives, I remove the it (pop) and append to the tail of queue (push). Otherwise, only removal and no appending (just pop, no push). Repeating these steps with NestWhile until the length of my queue is no more than the survival count. The condition to save a diagram is simple: each time the process passes though all survivors in the current round, the smallest number moves back from right most to left most. Vice versa. By the nature of this data structure and my operation, if the first is less than second item in the queue, the sequence is guaranteed to be ascending. Then use Reap outside of the loop to collect each Sow’ed expression in each step to extract diagrams and still returns the computation result.
In[]:=
n=0;​​res=Reap[NestWhile[​​(n++;head=#["Pop"];​​If[Mod[n,kthKilled]!=0,#["Push",head]];​​If[head>ds["Peek"],Sow[ds["Visualization"]]];​​ds)&,ds,#["Length"]>survival&]["Visualization"]];
Use a column or grid function to organize the diagrams. This shows the evolution of between each round. Sometimes the last ascending queue and the result coincides, I want to show only one of them therefore the code is slightly lengthy to eliminate the duplication.
In[]:=
Framed[​​With[{diagrams=RotateLeft[Flatten[res],1]},​​If[diagrams[[-1]]===diagrams[[-2]],Most@diagrams,diagrams]]//GraphicsColumn[#,Dividers{None,{-2True}}]&​​]
Out[]=
The following result is the same as the wiki example except I stop at {16, 31} to show the case with 2 survivors.
Clear the data structure after the computation
In[]:=
ds["DropAll"];

Summary

◼
  • Use queue data structure as circular linked list
    • ◼
  • Use Visualization attribute to create a diagram for each data structure and their status
    • ◼
  • Use Reap and Sow to collect visualizations during the computation
    • For the most efficient implementation, use pure list manipulation and the linked code on Rosetta Code.
    I can wrap the code linked with Cases and Column to create a similar table like
    this
    In[]:=
    Column[Rest@Cases[NestList[Most[RotateLeft[#,3]]&,Range[41],40],_?(First[#]<=Last[#]&)]]
    Out[]=
    {2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26,28,29,31,32,34,35,37,38,40,41}
    {2,4,7,8,11,13,16,17,20,22,25,26,29,31,34,35,38,40}
    {2,4,8,11,16,17,22,25,29,31,35,38}
    {2,4,11,16,22,25,31,35}
    {4,16,22,31,35}
    {16,31,35}
    {16,31}
    {31}
    Because in WL list is very optimized for array like operation, it takes a fraction of second to generate result for large numbers from following example with 23482 member and killed at every 3343th position
    In[]:=
    Nest[Most[RotateLeft[#,3343]]&,Range[0,23482-1],23482-3]//Sort
    Out[]=
    {1087,1335,13317}