-2
\$\begingroup\$

The problem is basically this: Return the permutation of the set of the first n natural numbers which satisfies the following property:

|pos(i) - i| = k
∀ i ∈ (1,n)
where pos(i) is the ith number in the permutation

If no such permutation exists, return -1.

Note: the input is the integer n.

The full problem is on HackerRank.

The code for the main algorithm:

try:
    for y in g.keys():
        g[y] = [y-k,y+k]
        if y - k <=0:
            g[y].remove(y-k)
        if y + k > n:
            g[y].remove(y+k)

    d = []
    for y in range(1,n+1):
        if len(g[y]) == 1:
            if g[y][0] not in d:
                d.append(g[y][0])
        if len(g[y]) == 2:
            if g[y][0] not in d:
                d.append(g[y][0])
                   
        
    if len(set(d)) == len(d) and len(d) == n:
        return d
    else:
        return [-1]
except:
    return [-1]

g is a previously defined dictionary containing the first n natural numbers as keys with each key initially being assigned a value of 0

the first block changes the value of the key y to the possible numbers that could be at position y in the permutation, namely, y - k or y + k

d is the list that will contain the final permutation. If the value for i in g has only one number, then that number is added to d. If it contains 2 numbers, the first number is added by default. If the first number is already in d, the second number is added. d is printed if, finally, d contains n elements and there are no repeating elements.

On hackerrank, 9 of the 13 test cases are successful, but the last 4 return a timeout error. I've run through the code step by step and it's clear that the second block is taking way too long for larger numbers. I know using list comprehension would make it faster, but I have no idea how to convert that into list comprehension.

How do I make this code more efficient?

\$\endgroup\$
5
  • \$\begingroup\$ There are 2 "if" that are doing same thing. Why don't you use only 1 "if"? if len<=2 then add once. \$\endgroup\$ Mar 11, 2021 at 18:33
  • \$\begingroup\$ If I don't include the if len == 1 statement then I get an index error when checking if g[y][1] is in d. \$\endgroup\$
    – MNIShaurya
    Mar 11, 2021 at 18:46
  • \$\begingroup\$ Where are you checking if g[y][1] is in d? \$\endgroup\$ Mar 11, 2021 at 19:03
  • \$\begingroup\$ Why do you say "the input is the integer n" when in reality it's n and k? And better show the whole absolutePermutation(n, k) function. \$\endgroup\$
    – Manuel
    Mar 11, 2021 at 21:03
  • \$\begingroup\$ "On hackerrank, 9 of the 13 test cases are successful" - I tried it and got "Wrong Answer" for 6 of the test cases. \$\endgroup\$ Mar 11, 2021 at 23:29

2 Answers 2

1
\$\begingroup\$

You test not in d, where d is a list. That's slow. Use an additional set for those membership tests.

Simpler way: Note that the number 1 must go to position 1+k. It has nowhere else to go. Also, the only number that can go to position 1 is the number 1+k. So numbers 1 and 1+k must switch places. Similarly, the numbers 2 and 2+k must switch places (unless k<2). And so on. The entire first k numbers must switch with the next k numbers.

After that, the reasoning repeats, numbers (2k+1) and (2k+1)+k must switch. The entire third chunk of k numbers must switch with the fourth chunk of k numbers. And so on.

In other words, numbers in the first, third, fifth, etc chunk of k numbers must move k positions to the right and numbers in the other chunks of k numbers must move k positions to the left. In yet other words, add k to the odd-numbered chunks and subtract k from the even-numbered chunks.

A solution that tries to build it and discards it if it's invalid:

def absolutePermutation(n, k):
    p = [i+1 + (-k if k and i//k%2 else k) for i in range(n)]
    return p if max(p) == n else [-1]

Shorter but slower (still accepted):

def absolutePermutation(n, k):
    p = [i+1 + k*(-1)**(k and i//k) for i in range(n)]
    return p if max(p) == n else [-1]

Alternatively, check whether it'll work and build it only if it will. It will iff there's an even number of complete k-chunks, i.e., if n is divisible by 2k:

def absolutePermutation(n, k):
    if k == 0:
        return range(1, n+1)
    if n % (2*k):
        return [-1]
    return [i+1 + k*(-1)**(k and i//k) for i in range(n)]

Yet another, starting with the identity permutation and then swapping slices:

def absolutePermutation(n, k):
    K = 2 * k
    if k and n % K:
        return [-1]
    p = list(range(1, n+1))
    for i in range(k):
        p[i::K], p[i+k::K] = p[i+k::K], p[i::K]
    return p

A longer but quite nice version using the grouper recipe to give us the chunks:

def absolutePermutation(n, k):
    numbers = range(1, n+1)
    if k == 0:
        yield from numbers
    elif n % (2*k):
        yield -1
    else:
        chunks = grouper(numbers, k)
        for chunk in chunks:
            yield from next(chunks)
            yield from chunk
\$\endgroup\$
0
\$\begingroup\$

Many programming puzzles of this sort can be solved without brute-force computations if you can figure out the pattern. Rather than trying to implement a solution to the puzzle, it's often helpful to write some temporary code just to explore. The small script below does that. For each list size from 1 through max_n, we find the permutations having valid solutions, along with the corresponding k values.

Some patterns jump about pretty quickly. Odd-sized lists appear to support only k=0. Even-sized lists are interesting: take a close look, for example, at sizes 6 and 8.

import sys
from itertools import permutations

def main():
    max_n = int(sys.argv[1])
    fmt = '{:<6} {:<4} {}'
    div = '-' * 40
    print(fmt.format('SIZE', 'K', 'PERM'))
    for size in range(1, max_n + 1):
        print(div)
        for tup in permutations(range(1, size + 1)):
            diffs = [abs(j + 1 - x) for j, x in enumerate(tup)]
            ds = sorted(set(diffs))
            if len(ds) == 1:
                k = ds[0]
                print(fmt.format(size, k, tup))

main()

Output for max_n=9:

SIZE   K    PERM
----------------------------------------
1      0    (1,)
----------------------------------------
2      0    (1, 2)
2      1    (2, 1)
----------------------------------------
3      0    (1, 2, 3)
----------------------------------------
4      0    (1, 2, 3, 4)
4      1    (2, 1, 4, 3)
4      2    (3, 4, 1, 2)
----------------------------------------
5      0    (1, 2, 3, 4, 5)
----------------------------------------
6      0    (1, 2, 3, 4, 5, 6)
6      1    (2, 1, 4, 3, 6, 5)
6      3    (4, 5, 6, 1, 2, 3)
----------------------------------------
7      0    (1, 2, 3, 4, 5, 6, 7)
----------------------------------------
8      0    (1, 2, 3, 4, 5, 6, 7, 8)
8      1    (2, 1, 4, 3, 6, 5, 8, 7)
8      2    (3, 4, 1, 2, 7, 8, 5, 6)
8      4    (5, 6, 7, 8, 1, 2, 3, 4)
----------------------------------------
9      0    (1, 2, 3, 4, 5, 6, 7, 8, 9)
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.