Josephus Sequence on large k

Question

In the Josephus problem we have n people numbered from 1 to n. Each turn you skip k people and kill the next one. Usually you print the last survivor put I am interested on the sequence of victims. I tried to do this with circular linked lists based on advice found online. My algorithm still isn't fast enough when inputs are large like n=123456; k=1000000000. My time goal is under a second. I think the time complexity is O(nk), since all the linked list operations are O(1) and for each person I have to print their value and possibly move k steps. Should I find some different strategy are am I missing some obvious optimization techniques?

#include <vector>
using namespace std;
 
struct Node {
    int value;
    struct Node* next;
};
 
Node* insertToEmpty(struct Node* last, int x) {
    Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->value = x;
    last = temp;
    last->next = last;
    return last;
}
 
Node* insert(struct Node* last, int x) {
    if (last == NULL) {
        return insertToEmpty(last, x);
    }
    Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->value = x;
    temp->next = last->next;
    last->next = temp;
    last = temp;
    return last;
}
 
Node* delete2(struct Node* prev, struct Node* current) {
    prev->next = current->next;
    return current->next;
}
 
int main() {
    int n;
    int k;
    cin >> n;
    cin >> k;
    if (n == 1) {
        cout << 1;
    }
    else {
        struct Node* curr;
        struct Node* prev;
        struct Node* last = NULL;
        for (int i = 1; i <= n; i++) {
            last = insert(last, i);
        }
        curr = last->next;
        prev = curr;
        for (int i = 1; i <= k%n; i++) {
            prev = curr;
            curr = curr->next;
        }
        do {
            cout << curr->value << " ";
            curr = delete2(prev, curr);
            n--;
            for (int j = 0; j < k%n; j++) {
                prev = curr;
                curr = curr->next;
            }
        } while (n > 1);
        cout << curr->value << endl;
 
    }
 
}

Answer 1

We can gain independence from k by using a treap with a size decoration. O(n log n).

Sample input, output:

stdin:   10 5
stdout:  4 9 5 1 8 7 0 3 6 

C++ adapted from code by Kimiyuki Onaka:

#include <iostream>
#include <tuple>
#include <random>
#include <memory>

using namespace std;

template <typename T>
struct treap {
    typedef T value_type;
    typedef double key_type;
    value_type v;
    key_type k;
    shared_ptr<treap> l, r;
    size_t m_size;
    treap(value_type v)
            : v(v)
            , k(generate())
            , l()
            , r()
            , m_size(1) {
    }
    static shared_ptr<treap> update(shared_ptr<treap> const & t) {
        if (t) {
            t->m_size = 1 + size(t->l) + size(t->r);
        }
        return t;
    }
    static key_type generate() {
        static random_device device;
        static default_random_engine engine(device());
        static uniform_real_distribution<double> dist;
        return dist(engine);
    }
    static size_t size(shared_ptr<treap> const & t) {
        return t ? t->m_size : 0;
    }
    static shared_ptr<treap> merge(shared_ptr<treap> const & a, shared_ptr<treap> const & b) { // destructive
        if (not a) return b;
        if (not b) return a;
        if (a->k > b->k) {
            a->r = merge(a->r, b);
            return update(a);
        } else {
            b->l = merge(a, b->l);
            return update(b);
        }
    }
    static pair<shared_ptr<treap>, shared_ptr<treap> > split(shared_ptr<treap> const & t, size_t i) { // [0, i) [i, n), destructive
        if (not t) return { shared_ptr<treap>(), shared_ptr<treap>() };
        if (i <= size(t->l)) {
            shared_ptr<treap> u; tie(u, t->l) = split(t->l, i);
            return { u, update(t) };
        } else {
            shared_ptr<treap> u; tie(t->r, u) = split(t->r, i - size(t->l) - 1);
            return { update(t), u };
        }
    }
    static shared_ptr<treap> insert(shared_ptr<treap> const & t, size_t i, value_type v) { // destructive
        shared_ptr<treap> l, r; tie(l, r) = split(t, i);
        shared_ptr<treap> u = make_shared<treap>(v);
        return merge(merge(l, u), r);
    }
    static pair<shared_ptr<treap>,shared_ptr<treap> > erase(shared_ptr<treap> const & t, size_t i) { // (t \ t_i, t_t), destructive
        shared_ptr<treap> l, u, r;
        tie(l, r) = split(t, i+1);
        tie(l, u) = split(l, i);
        return { merge(l, r), u };
    }
};

typedef treap<int> T;
int main() {
    int n; cin >> n;
    int k; cin >> k;
    shared_ptr<T> t;
    for (int i=0; i<n; i++)
        t = T::insert(t, i, i);
    
    int size = n;
    int position = 0;
    for (int i=0; i<n-1; i++){
        position = (position - 1 + k) % size;
        size = size - 1;
        shared_ptr<T> u;
        tie(t, u) = T::erase(t, position);
        cout << u->v << " ";
    }
    cout << endl;
    return 0;
}

Answer 2

You are correct that using a simple linked list is O(nk) and you have to use a better data structure if you want to speed it up. I would recommend that you use a variant of a skip list for this problem.

A skip-list is a 2-dimensional structure. All of the values are at the bottom level. Each level up only has some of the values. It skips the others. If you want to move a fixed number of steps, you walk forward and up, skipping over elements, until you can walk forward and down to the exact right spot. All operations are logarithmic. In your case that will make the algorithm O(n (log(n) + log(k))

With this structure, a node will look something like this:

struct Node {
    int value;
    int count;
    struct Node* parent;
    struct Node* next;
    struct Node* first_child;
};

When you build it, your bottom layer will look like:

1 <-> 2 <-> 3 <-> ... <-> n

with first_child being null, parent being a pointer to the next level up, and count being 1.

Your second layer will look like:

1 <-> 3 <-> 5 <-> ... <-> (n-1 or n as appropriate)

with the first_child pointing to the same value in the layer below, your parent pointing to the next layer up, and count being 2.

Your third layer will look like:

1 <-> 5 <-> 9 <-> 13 <-> ... <-> (something from n-3 to n)

with the first_child pointing to the same value in the layer below, your parent pointing to the next layer up, and count being 4.

And so on until your very top layer just contains 1 and the next value is off the end of the array. There will be O(log(n)) levels.

OK, that is setup. How do we remove something? I'm going to just write untested code in a language I don't know, please pardon the syntax errors:

void remove (Node* node) {
    if (0 == --node->count) {
        /* Actually delete */
        if (node->prev != null) {
            node->prev->next = node->next;
        }
        if (node->next != null) {
            node->next.prev = node->prev;
        }
        if (node->parent != null && node = node->parent.first_child) {
            node->parent->first_child = node->next;
            node->parent->value = node->next->value;
        }
    }
    if (node->parent != null) {
        remove(node->parent);
    }
    if (0 == node->count) {
        free(node);
    }
}

This operation takes O(log(n)) time because that is how many levels there are.

Next we will need a small helper function to find the last node in a block. Which means that we want to travel down and right until we get to that node.

Node* last_in_block (Node* node) {
    if (node->next == null) {
        /* Slide down the end. */
        while (node->first_child != null) {
            node = node->first_child;
        }
    }
    else {
        while (node->first_child != null) {
            Node* child = node->first_child;
            while (child->next->parent == node) {
                child = child->next;
            }
            node = child;
        }
    }
    return node;
}

Now what about moving forward some number of steps? That's a little tricky.

First let's agree that being at a particular spot means "I just visited here and am moving on." So we can recursively define move as "look for node to step over, and then subtract its count from the block". But there are a few edge cases. Again untested code, but the following should give the general idea of what I mean.

Node* move (Node* node, int steps) {
    if (node->next == null) {
        /* We are at the end, go to the top */
        while (node->parent != null) {
            node = node->parent;
        }

        /* Go around the loop as many times as needed. */
        steps = steps % node->count;

        /* Travel down to the right level to continue our journey */
        while (steps < node->count) {
            node = node->first_child;
        }

        /* And step over this node */
        steps -= node->count;
    }

    if (steps <= 0) {
        /* EXIT HERE IF JOURNEY IS ENDED */
        return last_in_block(node);
    }

    /* Right now the following are true.

       1. We are not at the end.
       2. We are also not at the top level (because the node there is at the end).
       3. node->next is also not at the top level (because it is at our level).
       4. 0 < steps, so traveling down we will eventually find a doable step.
    */

    if (steps <= node->next->count) {
        /* travel forward, then down to the right level. */
        node = node->next;
        while (steps < node->count) {
            node = node->first_child;
        }
    }
    else if (node->parent != node->next->parent && node->next->parent->count < steps) {
        /* travel forward and then up */
        node = node->next;
        while (node->parent != null && node->parent->count < steps) {
            node = node->parent;
        }
    }
    else {
        /* just travel forward */
        node = node->next;
    }
    /* And now we step over the block represented by this node. */
    steps -= node->count;
    return move(node, steps);
}

And now with this data structure you can figure out how to move forward, remove the spot you are standing on, move forward again, etc.