How can I remove the nth member in the Josephus Problem using C++?

[Kingyou123]

I'm trying to write a program that plays the Josephus Problem.
I'm running into a problem in the remove_nth_member part:

string Cqueue2::remove_nth_member(int n)             //for Josephus problem to remove a member
    {
        string name;
        int i;
        int index;
        int start;

        name = Queue[(n - 1) % Size];
        //we'll be deleteing the soldier at index n%Size
        //subtract 1 to account for the fact that indexing starts at 0

        start = n%Size;
        string * TempQ = new string[Size - 1];
        //some looping has to go on here, to move stuff in current queue to temp queue that is smaller
        for (i = 0; i < Size; i++)
        {
            index(Start++i) % Max;
            tempQ[i] = Queue[index];
        }
        //refresh Queue with the member who is kicked out gone
        //Change its size
        //delete Queue
        for (int j = 0; j < Size; j++)
        {

            Size--;
        }
        //create a new Queue with new Size
        //iterate and move things from tempQ into Queue
        //deduct from the Max variable
        return name;
    }

I can't seem to figure out how to write the code so that it refreshes the queue without the member who gets kicked out.
My pseudocode:
1.Move all the names in a temp queue.( did this)
2.Delete the nth member and downsizes the original queue. (stuck on this part)
3.Delete the temp queue
4.Do this till the queue size is 1 and the last name is the survivor.

Links to the full code:
main.cpp = https://gist.github.com/anonymous/862bdd9b679ef03c25df99b7b4cd00eb
queue2.cpp= https://gist.github.com/anonymous/f00c910da6c6cd90859ae234855566a3
queue2.h= https://gist.github.com/anonymous/a90f03aa6d0f56a6fd7601bccb66e40b

 

[Mark44]

I'm trying to write a program that plays the Josephus Problem.
I'm running into a problem in the remove_nth_member part:

string Cqueue2::remove_nth_member(int n)             //for Josephus problem to remove a member
    {
        string name;
        int i;
        int index;
        int start;

        name = Queue[(n - 1) % Size];
        //we'll be deleteing the soldier at index n%Size
        //subtract 1 to account for the fact that indexing starts at 0

        start = n%Size;
        string * TempQ = new string[Size - 1];
        //some looping has to go on here, to move stuff in current queue to temp queue that is smaller
        for (i = 0; i < Size; i++)
        {
            index(Start++i) % Max;
            tempQ[i] = Queue[index];
        }
        //refresh Queue with the member who is kicked out gone
        //Change its size
        //delete Queue
        for (int j = 0; j < Size; j++)
        {

            Size--;
        }
        //create a new Queue with new Size
        //iterate and move things from tempQ into Queue
        //deduct from the Max variable
        return name;
    }

I can't seem to figure out how to write the code so that it refreshes the queue without the member who gets kicked out.
My pseudocode:
1.Move all the names in a temp queue.( did this)
2.Delete the nth member and downsizes the original queue. (stuck on this part)
3.Delete the temp queue
4.Do this till the queue size is 1 and the last name is the survivor.

Links to the full code:
main.cpp = https://gist.github.com/anonymous/862bdd9b679ef03c25df99b7b4cd00eb
queue2.cpp= https://gist.github.com/anonymous/f00c910da6c6cd90859ae234855566a3
queue2.h= https://gist.github.com/anonymous/a90f03aa6d0f56a6fd7601bccb66e40b

A queue is probably not the right type of container for you. You can add (push) an element to the end of the queue, and you can remove (pop) and element from the front, but that's about it. A type of container that might be better suited is a deque (double-ended queue). You can push elements onto either end, pop elements from either end, and insert or remove elements from anywhere in the deque.

 

[Kingyou123]

A queue is probably not the right type of container for you. You can add (push) an element to the end of the queue, and you can remove (pop) and element from the front, but that's about it. A type of container that might be better suited is a deque (double-ended queue). You can push elements onto either end, pop elements from either end, and insert or remove elements from anywhere in the deque.

I was hoping on using a circle queue:
For example if it counted down by 3 to select the the member of group, 0, 1,2, .Removes the 2rd person and then 3 is the next starting point, 3 ,4,5, removes 5 and then 6 is the new starting point.Eventually it would end up with one element in the queue. This is what I'm trying to recreate.

 

[Mark44]

I'm assuming you are coding in C++ and are using STL containers.

The problem with the queue STL type is that it doesn't give you random access. You can only add new elements at the end, and remove them from the front. What you're proposing is to remove elements from the middle of the queue, which isn't supported.

You could use the STL array type, which does support random access, and use modular arithmetic to identify a particular item in the array to remove. The circular structure you show has 8 elements, with indexes ranging from 0 through 7. If you're at index 6 and want to get to an index 3 higher, the calculation would be (6 + 3) % 8, which is 1, so you would remove person[1] from the array. Each time you remove a person, you need to change the modular base, so the next index calculation would have to be modulo 7, and so on, after each person is removed. When the size of the array is 1, you're finished.

 

[Kingyou123]

I'm assuming you are coding in C++ and are using STL containers.

The problem with the queue STL type is that it doesn't give you random access. You can only add new elements at the end, and remove them from the front. What you're proposing is to remove elements from the middle of the queue, which isn't supported.

You could use the STL array type, which does support random access, and use modular arithmetic to identify a particular item in the array to remove. The circular structure you show has 8 elements, with indexes ranging from 0 through 7. If you're at index 6 and want to get to an index 3 higher, the calculation would be (6 + 3) % 8, which is 1, so you would remove person[1] from the array. Each time you remove a person, you need to change the modular base, so the next index calculation would have to be modulo 7, and so on, after each person is removed. When the size of the array is 1, you're finished.

index(n - 1) % Size;
name = Queue[index];
        std::string *newQueue = new std::string[Size - 1];
    for (size_t i = 0; i < index; i++) {
            newQueue[i] = queue[i];
        }
       
  
        for (size_t i = index + 1; i < Size; i++) {
            newQueue[i - 1] = queue[i];
        }
        delete[] queue;
        queue = newQueue;

        Size--;
   
        return Name;
    }

Ignore the weird formatting, I tried translating your pseudo code into C++. Is this the correct way?

 

[Mark44]

I was thinking more along the lines of a STD array template class, although a string (i.e., basic_string class) might work. You could initialize the string with the characters '0' through '9' if you start with no more than 10 soldiers in the boat. Or you could initialize it to 'A' through 'Z' if there are no more than 26 i the boat.

I can't tell what you are doing in your code. Your first line doesn't do anything - index(n - 1) % Size; - this just calculates a value, but doesn't store it anywhere.

If you can describe in words what you code is supposed to do in one iteration, that would be helpful.

 

[Kingyou123]

I was thinking more along the lines of a STD array template class, although a string (i.e., basic_string class) might work. You could initialize the string with the characters '0' through '9' if you start with no more than 10 soldiers in the boat. Or you could initialize it to 'A' through 'Z' if there are no more than 26 i the boat.

I can't tell what you are doing in your code. Your first line doesn't do anything - index(n - 1) % Size; - this just calculates a value, but doesn't store it anywhere.

If you can describe in words what you code is supposed to do in one iteration, that would be helpful.

std::string *newQueue = new std::string[Size - 1];

//Transfer all before removed index, even if index will be 0 then this loop won't fire
for(size_t i = 0; i < index; i++){
  newQueue[i] = queue[i];      
}

//Transfer all after index, if index will be last element of array this loop won't fire
for(size_t i = index + 1; i < Size; i++){
  newQueue[i - 1] = queue[i]; // i - 1 cause we skip one and new array has one space less.
}

delete[] queue; // free memory of old queue.
queue = newQueue; // assign pointer of new queue to queue.

Size--; //Reduce Size counter.

Is this better? I'm trying to make sure my logic is correct.

 

[Mark44]

Instead of working with two strings, queue and newQueue, and copying the contets, why not work with just one? Also, you're second for loop is, IMO, more complicated than it needs to be, and I'm not sure it works the way you want it to. Instead of all that copying, just use basic_string::erase() to get rid of an character in your string.

The following code initializes str to "Hello there". The call to str.erase(6, 1) deletes one character at index 6, so that the string is now "Hello here". It moves all of the characters after the one that is removed -- you don't have to do any copying like you're doing in your second for loop.

#include <string>
using std::cout;
using std::endl;

int main()
{
   std::string str = "Hello there";
   str.erase(6, 1);
   cout << str << endl;

   return 0;
}

 

[Mark44]

@Kingyou123, did you ever figure this out? I see that you have now started a new thread on a different problem.

 

[Kingyou123]

@Kingyou123, did you ever figure this out? I see that you have now started a new thread on a different problem.

Yes, i did. However I used a completely different method. I can post it if you like

 

[Mark44]

Sure, but there's no rush. Please post it when you get a chance.

 

[Kingyou123]

Sure, but there's no rush. Please post it when you get a chance.

string Cqueue2::remove_nth_member(int n)             //for Josephus problem to remove a member
{
    string name;
    int i;
    int index;
    int start;

    name = Queue[(n - 1) % Size];
    start = n%Size;
    //we'll be deleteing the soldier at index n%Size
    //subtract 1 to account for the fact that indexing starts at 0
    start=n%Size;
    string * TempQ=new string [Size-1];
    //some looping has to go on here, to move stuff in current queue to temp queue that is smaller
    for (int i = 0; i < (Size - 1); i++) {
        index = (start + i) % Max; // finds the guy we have to remove
        TempQ[i] = Queue[index];// moves the queue to a tempqueue
    }
    Size--;
    delete[] Queue;
    Queue = new string[Size];
    for (int i = 0; i < Size; i++) {
        Queue[i] = TempQ[i];//moves temp queue to queue
    }
    Max--;
    delete[] TempQ;
   

    //refresh Queue with the member who is kicked out gone
    //Change its size
    //delete Quieue
    //create a new Queue with new Size
    //iterate and move things from tempQ into Queue
    //deduct from the Max variable
    return name;
}