tags:

views:

254

answers:

1

Question source: SPOJ.. ORDERS

def swap(ary,idx1,idx2):
    tmp = ary[idx1]
    ary[idx1] = ary[idx2]
    ary[idx2] = tmp

def mkranks(size):
    tmp = []
    for i in range(1, size + 1):
        tmp = tmp + [i]
    return tmp

def permutations(ordered, movements):
    size = len(ordered)
    for i in range(1, size): # The leftmost one never moves
        for j in range(0, int(movements[i])):
            swap(ordered, i-j, i-j-1)
    return ordered

numberofcases = input()
for i in range(0, numberofcases):
    sizeofcase = input()
    tmp = raw_input()
    movements = ""
    for i in range(0, len(tmp)):
        if i % 2 != 1:
            movements = movements + tmp[i]
    ordered = mkranks(sizeofcase)
    ordered = permutations(ordered, movements)
    output = ""
    for i in range(0, sizeofcase - 1):
        output = output + str(ordered[i]) + " "
    output = output + str(ordered[sizeofcase - 1])
    print output
+1  A: 

Having made your code a bit more Pythonic (but without altering its flow/algorithm):

def swap(ary, idx1, idx2):
    ary[idx1], ary[idx2] = [ary[i] for i in (idx2, idx1)]

def permutations(ordered, movements):
    size = len(ordered)
    for i in range(1, len(ordered)):
        for j in range(movements[i]):
            swap(ordered, i-j, i-j-1)
    return ordered

numberofcases = input()
for i in range(numberofcases):
    sizeofcase = input()
    movements = [int(s) for s in raw_input().split()]
    ordered = [str(i) for i in range(1, sizeofcase+1)]
    ordered = permutations(ordered, movements)
    output = " ".join(ordered)
    print output

I see it runs correctly in the sample case given at the SPOJ URL you indicate. What is your failing case?

Alex Martelli
its giving "time limit exceeded".. i think i hv to rethink my logic to this problem..
vaibhav
Yeah, for some inputs I'm sure it WILL take more than the 13 sec allotted, this is really a terrible algorithm (my rewrite eliminates many of the incredible time wastes you had, such as building up lists by repeated addition of single-item lists, but I didn't change your underlying algorithm at all as I figured you're trying to flex your brain muscles, not to get a pre-chewed meal;-).
Alex Martelli