Flavius Joseph Algorithm

I'm trying to find Josephus algorithm and haven't done so. Please I need help with this.
desperadoAsked:
Who is Participating?

[Webinar] Streamline your web hosting managementRegister Today

x
 
the_bikemanConnect With a Mentor Commented:
Here is the function.  Remember to:  #include <stdio.h>


/**************
   The Josephus algorithm.
   This function will return the last man standing.  :)
   n is the amount of people in the circle in the beginning,
   while m is the mth person you delete each time.
**************/
int jos(int n, int m)  {
  int data[n], i, q, curr_pos = 0, curr_size = n;
  for(i = 1; i <= n; i++) data[i-1] = i;
  for(;;)  {
    if(curr_size == 1)  
      return data[0];
    curr_pos = (curr_pos-1+m)%(curr_size);
    for(q = curr_pos; q < curr_size; q++)
      data[q] = data[q+1];
    --curr_size;
  }
}                                                      


Hope this works for you!

the_bikeman
0
 
brandtsCommented:
I've never heard of the Josephus algorithm, but this website seems to have something about it:

http://www.auto.tuwien.ac.at/~blieb/woop/welcome.html
0
 
sthungCommented:
What topic does this algorithm related?
0
Firewall Management 201 with Professor Wool

In this whiteboard video, Professor Wool highlights the challenges, benefits and trade-offs of utilizing zero-touch automation for security policy change management. Watch and Learn!

 
desperadoAuthor Commented:
josephus problem is related to the following. Begining with n people arranged in a circle. Starting with the first person, count continuosly around the circle removing every m-th person until only one remains.Example n=7 and m=4

           1,2,3,4,5,6,7
            1,2,3,5,6,7
             2,3,5,6,7
              2,3,5,7
               2,3,7
                2,3
                 2

the winner is # 3. I'm trying to develop an algorithm for a function
Jos(n,m)
0
 
desperadoAuthor Commented:
I mean winner is #2
0
 
desperadoAuthor Commented:
Adjusted points to 50
0
 
ozoCommented:
Please post the code for your function and explain what difficulty you are having with it.
0
 
mbormannCommented:
>>>I'm trying to develop an algorithm for a function              Jos(n,m)

two algorithms are in simple words
http://cut-the-knot.com/recurrence/j_solution.html
http://cut-the-knot.com/recurrence/r_solution.html

from
http://cut-the-knot.com/recurrence/flavius.html

I have the Java Applet Source Code for this if you are interested ...
0
 
desperadoAuthor Commented:
ozo...... I'm learning by myself and I'm trying to do the function but have no idea where to start.
0
 
desperadoAuthor Commented:
I just need to find and algorithm that I can make into a function...or some help with it
0
 
desperadoAuthor Commented:
mbormann....that code would be interesting
0
 
mbormannCommented:
I have seen that code and I cant do it myself ,am immersed in work,I mean the real algo is quite short and all the rest of the GUI stuff is heavy ,anyway mail me at my profile ID and I will sendi t to you all zipped up.
0
 
desperadoAuthor Commented:
n //number of person in circle
m //place of person that would be gone

for a[i]=1 to n do
  {
   if a[m]found
     a[i]=a[1+1]}
0
 
redpirkCommented:
0
 
desperadoAuthor Commented:
Thata code is in ADA and I don't understand it
0
 
IsacCommented:
#include <stdio.h>
#include <stdlib.h>

int josef(int num, int skip)
{
char *vec;
int i;
int curPtr;
int numLive = num;

vec = (char *)malloc(num+1);
for(i=1 ; i<=num ; i++)
   vec[i] = 1;

curPtr = 1;
while(numLive > 1)
{
   i = 1;
   while(i<skip)
   {
      curPtr++;
      if(curPtr > num)
         curPtr = 1;

      if(vec[curPtr])
         i++;
   }

   vec[curPtr] = 0;  /* KILL him*/

   curPtr++;
   if(curPtr > num)
      curPtr = 1;


   numLive--;
}

/* Find the one LIVE */
for(i=1 ; i<=num ; i++)
   if(vec[i])
      return(i);

return(-1);
}
0
 
Lab_RatCommented:
Linked list?
0
 
desperadoAuthor Commented:
circular link list
0
 
Lab_RatCommented:
Yes, but my software would have an important feature ;)
0
 
SunBowCommented:
Linked List !
0
 
hillelCommented:
Hello Desperado.

Your question is a matter of interest
as a theoretic problem.
Erecting a function that finds out the number that remains at last, is a matter of practical programming routine.

Do you know who was Josephus Flavius?
+++++++++++++++++++++++++++++++++++++
On the 1st century the Jews rebeled
against the Romans that ruled their territory. Joseph Ben-Matitiahu was
the Chief commander of the rebel at the
Galilee front (The northen part of Israel). The Jews defeated and found a sheleter at the fortress of Yodfat (which is about 30 Km. away from my place...) , surrouded by the Roman army.
As a last desperate step , they decided to commit a collective suicide.

I remeber a story describing the way how they choose the candidate to be killed next, in a 'round robin algorithm' as you present in your question.

Later on - Joseph Ben-Matitiahu crossed the lines , joined to the Romans , changed his genuine Hebrew name to  Josephus Flavius and became the "official" documentator of the "Great rebel". His "The wars of the Jews" is the main source from which one can study the history of that period.
0
 
SunBowCommented:
Yes, Thanks for reminding me on the name change, I'd forgotten that as a 'survivor' he romanized it. I think the Flavius part was for fealty to earthly lord there at the time.  He appears to be the top historian for what went on and what life was like in the first century AD. Including the offbeat religious zealots, religious groups, prophets and the like in and around that neighborhood, many of whom get mentioned in NT.

I think his caring for his people has oft been underated, and value underestimated.  As an educated thinker, he tried to tell his people NOT to rebel against Rome due to probable outcome, not due to desire to become Roman. He had seen their armed forces while the zealots had not. They were certain they could handle the local police force (of Rome). Yet he tried to do his part, even if it meant in the military (filling a talent vacuum there). If it was going to be war, he'd help fortify what he could, even help them fight. But not to die without cause, for where would the culture be if everyone killed themselves off?  

(altho in my mind the group in the cave were fanatical zealots, I may not recall whether there were any members of the group of people known as Zealots, but surely there was a fanaticism to first take on the Roman horde, then choose group suicide as the solution to a battle loss that does not involve having to be seen in defeat by others)

I doubt we can say he actually joined Romans, though it was thought he did at the time (a traitor, no less), being seen in their company more like he's an advisor rather than in a member of a chain gang; but at least it shows that he found a way to keep them from killing him and also get out of being a POW.  This certainly excluded his capability of hanging out with any zealots remaining for any length of time.  As a survivor, he also made the transition from one emporer to another, at a time when many Roman chieftains did not make the cut.  The result, or end to his means are a legacy of historical work (in his eye) that vastly surpasses alternatives.

hillel,
If in that neighborhood and/or interested in those old times, how's about a visit to lounge someday when there is the time?

desperado,
I need some clarification here before I can get close to trying to pitch in for you. First are you still interested in something, and does it require C, or Visual C or what.

I thought I'd seen a couple of other threads on this issue, and that you may be handiling this problem one-on-one for another. So, what is your status?

It is also not clear to me what kind of program you want to do.  Do you want to compute where to stand?  Or would you like a display that just kills them off until only one is left? Or two?  Do you just want to predict the positions of the ### survivors?

On my own, I'd be tempted to run linked list on original participants. Same length.  But after clicking on some links on the topic and following them, it seems like an interesting simplification may be available by adding each person passed over to the end of the line.

But maybe you are aware and want to do something different.  Adding at end of line obviously increases the length requirements, size of array if used, etc.

My assumption is also that you are only dealing with the fixed numbers of the Josephus problem, not a larger world of possibilities.

Have you tried any of the recommended solutions, any of the code available on the web, if so, with what effect? What went right or wrong, and where do you want to take this now?
0
 
hillelCommented:
Hello everybody
I was very fond of the historical session that we had... It is very interesting indeed.
But - Let's switch back to our original
agenda...

I'm interested in the analytical aspect
of the problem.
The algorithmic aspect seems quite simple and not really chalanging....

Strictly speaking - Is there a "closed
function" or a "Generating function"
or something that yields "directly"
the value of Jos(N,M)?
A very well known equivalent is the analytical solution of difference equations (like the "immortal" Fibbonaci sequence...) where you get the N_th element by simple computation.
One does not need to generate the whole sequence in order to get the N_th element.
Does anybody have any clue...?

0
 
SunBowCommented:
Sounds like a math q:, perhaps EE needs a math topic.  In following the links leading to "an interesting simplification may be available by adding each person passed over to the end of the line."

I'd like to think that once the multiline solution is presented for that method, that knowing the technique would enable a mathematical simplification to a function. Have you pursued the links?I am not that deep in math or use of summations or even fibonacci, so my ignorance has this method appear as a "generating function", being less familiar with names and terms.
0
 
sylpheCommented:
Hello everybody,

First i want to precise that i'm not a native english speaker, and i'm new to this site, so i apologize for all my mistakes.
I think there could be an iterative solution, for your problem, and i will think on it when i will be less busy, and maybe there is a direct method to find the last one.
Here is a program in C implemanting a naive version of the solution, if something is not clear please ask, i hope it will be readable.

PS : Take care that the first person is the 0-th in this code

/*
 *      Josephus (naive)
 */

#include <stdio.h>
#include <stdlib.h>

int josephus(int,int);

void main(void)
{
      fprintf(stdout,"The last one is the %d th \n",josephus(7,4));
}

int josephus(int m,int n)
{
      int i,r,s=0;
      int *str=(int *)calloc(m,sizeof(int));      /* Allocate memory and put 0 in it */
      
      for(i=0;i<m-1;i++)                  /* Till it remain just one person */
      {
            r=n-1;
            
            while(r)                  /* Till we don't reach the n-th person next to the last removed */
            {
                  if(!str[s])            /* The one we consider still there ? */
                  {
                        r--;            /* Yes, so if needed continue to find the next one */
                        s=(++s)%m;
                  }
                  
                  while(str[s])            /* Jump to the next one till the one we consider have been removed */
                  {
                        s=(++s)%m;
                  }
            }
            
            str[s]++;                  /* Remove him */
            
            fprintf(stderr,"%d\n",s+1);      /* To keep trace */
      }
      
      /* Find the last one */
      
      for(i=0;i<m;i++)
      {
            if(!str[i])
            {
                  free(str);
                  return(++i);
            }
      }
}
0
 
SunBowCommented:
I'd like to read this C better tomorrow with more time. Just stopped by today for history trivia I ran across as fyi. Josephus claimed he met 40 people in pit in ground, not cave. One of them, a female got caught. That leaves 40 total. She is mentioned in context of turning them in to the romans. The romans then offered him freedom. He was not sure he could trust at first, but his compatriots were too prepared for death as their way out. He convinced them to use more honor for the otherwise suicide pact. He said they drew lots, and since he too drew, they were more the happy for it. The one who's number was up was killed by the next who's number was up, etc. He did not admit to rigging it to his being among the last two. Be he alluded to that he should not admit to his method other than he did not want to either die or execute any companion himself.  In his treatment of it, He did not mention the 2nd survivor by name, who yet indeed could have provided the background for the present puzzle. Only two people had the living knowledge, and it is apparent Josephus (known as Joseph then)  felt it inadvisable to give away any incriminating details himself. Even when called Josephus many years later. But I think the total number dead for the problem may be off by at least one. If interested in that.
0
 
the_bikemanCommented:
Uh....this sounds like a very simple problem.  Some of the solutions posted here have been insane in length!  Are you still interested in a solution, Desperado?  If so, I'll write the funtion for you, with the following prototype:

int jos(int n, int m);  /*where n is the number of people originally,
                                    and m is the person removed each time.
                                    Function returns the number of the person who
                                    was left over.  */

the_bikeman
                                 
             
0
All Courses

From novice to tech pro — start learning today.