About Josephus_problem

Question

I am trying to solve the Josephus problem, and I have working code.

def J(n,x):
    li=range(1,n+1)
    k = -1
    while li:
        print li
        k = (k+x) % len(li)
        li.pop(k)
        k =k- 1
J(10, 3)

Now I want rewrite it to get the result as follows:

1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 1 1
1 1 0 1 1 0 1 1 0 1
1 0 0 1 1 0 1 1 0 1
1 0 0 1 1 0 0 1 0 1
0 0 0 1 1 0 0 1 0 1
0 0 0 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 1 0 0 0 0 0 0

How can I do this?

def J(n,x):
    li=[1]*10
    k = -1
    while li.count(1)>0:
        print li
        k = (k+x) % len(li)
        li[k]=0
        k =k- 1

Emmanuel · Accepted Answer · 2012-09-18T14:53:24.360

>>> def J(n,x):
    li=range(1,n+1)
    k = -1
    while li:
        for i in xrange(1,n+1):
        if i in li:
            print 1,
        else:
            print 0,
    print
        k = (k+x) % len(li)
        li.pop(k)
        k =k- 1

>>> J(10, 3)
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 1 1
1 1 0 1 1 0 1 1 0 1
1 0 0 1 1 0 1 1 0 1
1 0 0 1 1 0 0 1 0 1
0 0 0 1 1 0 0 1 0 1
0 0 0 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 1 0 0 0 0 0 0

Even better (one-liner replacing your print li):

>>> def J(n,x):
    li=range(1,n+1)
    k = -1
    while li:
        print [1 if i in li else 0 for i in xrange(1,n+1)]
        k = (k+x) % len(li)
        li.pop(k)
        k =k- 1

>>> J(10, 3)
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 0, 1, 1, 0, 1, 1, 1, 1]
[1, 1, 0, 1, 1, 0, 1, 1, 0, 1]
[1, 0, 0, 1, 1, 0, 1, 1, 0, 1]
[1, 0, 0, 1, 1, 0, 0, 1, 0, 1]
[0, 0, 0, 1, 1, 0, 0, 1, 0, 1]
[0, 0, 0, 1, 1, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]

You can even use print ' '.join(['1' if i in li else '0' for i in xrange(1,n+1)]) to have exactly the output you want :-)

You could write `total = range(n)` before the `while` loop and print a string instead of a list with `print " ".join('1' if i+1 in li else '0' for i in total)` — sloth, Sep 18 '12 at 14:53
I already added the string part (see my previous edit), now for having the range outside the loop, you're totally true ! — Emmanuel, Sep 18 '12 at 14:55

About Josephus_problem

1 Answers1