Josephus permutation problem
Solve Josephus permutation problem which is defined as: Suppose n people are arranged in a circle & we are given a positive integer m <= n. Beginning with a designated first person, we proceed around the circle removing mth person. After each person is removed, counting continues around the circle that remains. This continues until all n people have been removed. The order in which the people are removed from the circle defines (n,m) Josephus permutation. E.g. Josephus (7,3) is 3,6,2,7,5,1,4 .Suppose that n and m is a constant. Describe an O(n) time algorithm that given integers n,m outputs the (n,m) Josephus
Algorithm
Insert(curr,prev)//This algorithm inserts node in circular linked list. curr and prev are structure pointer variables which keep track of current and previous node resp. 1. [Input value] cin>>val; 2. Set temp->info:=val; 3. If(*curr==NULL) then a. Set *curr:=temp; 4. Els a. Set (*prev)->link:=temp; 5. Set *prev:=temp; 6. Set *prev->link:=*curr; 7. [End] Josephus(curr,prev,n)//Algorithm computes the node left on applying JP 1. Initialize ctr:=0; 2. If *curr==NULL then print “list is empty†and return NULL; 3. If (*curr==(*curr)->link) then: a. Set temp:=*curr; b. Set item:=temp->info; c. Free temp; d. Set *curr:=NULL; e. Set *prev:=NULL; f. Return item; 4. [end of if] 5. Else a. Repeat steps b and c for ctr=0 to n: b. Set *prev:=*curr; c. Set *curr:=(*curr)->link; d. Set temp:=*curr; e. Set item=temp->info; f. Set (*prev)->link=temp->link; g. Set (*curr):=(*curr)->link; h. Free temp; i. Return item; 6. [end of else] 7. [end] josephus_permuation(m,n)//Algorithm inputs number of elements in the list n then applies josephus permutation. Here n is the number of elements and m is the mth position from where element is to be deleted 1. For i=0 to n call insert(curr,prev); 2. For i=0 to m-1 Set num:=call josephus(curr,prev,n); 3. Return num;
Algorithm Description
C Code
//Implement JOSEPHUS Permutation Problem..
#include<stdio.h>
#include<conio.h>
struct node
{
int data;
struct node *link;
};
typedef struct node Node;
Node *start=NULL;
int main()
{
int n,m,i,count;
Node *n1,*ptr,*prev=NULL;
printf("Enter n ");
scanf("%d",&n);
printf("Enter m ");
scanf("%d",&m);
printf("Josephus permutation is :\n");
for(i=n;i>0;i--)
{
n1=(Node *)malloc(sizeof(Node));
n1->data=i;
n1->link=start;
start=n1;
}
ptr=start;
while(ptr->link!=NULL)
{
ptr=ptr->link;
}
ptr->link=start;
ptr=start;
while(1)
{
count=1;
while(count!=m)
{
prev=ptr;
ptr=ptr->link;
count++;
}
prev->link=ptr->link;
printf("%d ",ptr->data);
free(ptr);
if(ptr==prev)
break;
ptr=prev->link;
}
return 0;
}
C++ Code
#include <iostream>
#include <cstdio>
using namespace std;
int A[1000000];
int main()
{
int n,d;
while(1){
scanf(\"%d%d\",&n,&d);
if(n == 0 && d == 0 )
return 0;
// int *A = new int[n+1];
A[1] = 1;
for(int i=2;i<=n;i++){
A[i] = (A[i-1]+d)%i;
if(A[i] == 0)
A[i] = i;
}
printf(\"%d %d %d\\n\",n,d,A[n]);
}
return 0;
}
Java Code
import java.io.*;
class josephus
{
public static void main(String args[]) throws IOException
{
int n,m,m1,i;
System.out.println( "\n Enter the number of people in circle (n): ");
BufferedReader br= new BufferedReader (new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
System.out.println( "\n Enter the value of m (<=n): ");
m = Integer.parseInt(br.readLine());
while(m>n)
{
System.out.println("\n m should be less than n... Enter m again :") ;
m = Integer.parseInt(br.readLine());
}
int a[] = new int[10];
for(i=0;i<n;i++)
a[i] = 0;
m1 = m;
System.out.print ("\n Josephus (" + n + "," + m + ") is " + m);
a[m-1] = -1;
for(i=1;i<n;i++)
{
int count=0;
while(count<m)
{
if(m1==n)
m1 = 0;
m1++;
if(a[m1-1]==0)
count++;
}
System.out.print( "," );
System.out.print( m1);
a[m1-1] = -1;
}
}
}
