Проблема в основном такова: вернуть перестановку набора первого п натуральные числа, удовлетворяющие следующему свойству:
| pos (i) — i | = k
∀ i ∈ (1, n)
где pos (i) — это яое число в перестановке
Если такой перестановки не существует, верните -1.
Примечание: входными данными является целое число n.
Полная проблема на HackerRank.
Код основного алгоритма:
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 — это ранее определенный словарь, содержащий первые n натуральных чисел в качестве ключей, причем каждому ключу изначально присвоено значение 0
первый блок меняет значение ключа y к возможным числам, которые могут быть в позиции y в перестановке, а именно, y - k или же y + k
d это список, который будет содержать окончательную перестановку. Если значение для i в g имеет только одно число, то это число добавляется к d. Если он содержит 2 числа, по умолчанию добавляется первое число. Если первый номер уже в d, добавляется второе число. d печатается, если, наконец, d содержит n элементов и нет повторяющихся элементов.
В хакерранке 9 из 13 тестовых случаев успешны, но последние 4 возвращают ошибку тайм-аута. Я прогнал код шаг за шагом, и ясно, что второй блок занимает слишком много времени для больших чисел. Я знаю, что использование понимания списков сделало бы это быстрее, но я понятия не имею, как преобразовать это в понимание списка.
Как мне сделать этот код более эффективным?
2 ответа
Вы тестируете not in d, куда d это список. Это медленно. Используйте дополнительный набор для тех тестов на членство.
Более простой способ: обратите внимание, что цифра 1 должна перейти в позицию 1 + k. Ей больше некуда идти. Кроме того, единственное число, которое может перейти в позицию 1, — это число 1 + k. Значит, числа 1 и 1 + k должны поменяться местами. Аналогично, числа 2 и 2 + k должны поменяться местами (если k
После этого рассуждение повторяется, числа (2k + 1) и (2k + 1) + k должны поменяться местами. Весь третий фрагмент из k номеров должен переключиться на четвертый фрагмент из k номеров. И так далее.
Другими словами, числа в первом, третьем, пятом и т. Д. Блоке из k чисел должны перемещаться на k позиций вправо, а числа в других блоках из k чисел должны перемещаться на k позиций влево. Другими словами, добавьте k к фрагментам с нечетным номером и вычтите k из фрагментов с четным номером.
Решение, которое пытается построить его и отбрасывает, если оно недействительно:
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]
Короче, но медленнее (все еще принято):
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]
В качестве альтернативы проверьте, будет ли он работать, и создайте его, только если это будет. Это произойдет, если имеется четное количество полных k-фрагментов, т.е. если n делится на 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)]
Еще один, начиная с перестановки идентичности и затем меняя срезы местами:
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
Более длинная, но довольно приятная версия, использующая grouper рецепт приготовления чтобы дать нам куски:
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
Многие программные головоломки подобного рода можно решить без грубых вычислений, если вы сумеете выяснить закономерность. Вместо того, чтобы пытаться реализовать решение головоломки, часто бывает полезно написать временный код для изучения. Небольшой скрипт ниже делает это. Для каждого размера списка от 1 до max_n мы находим перестановки, имеющие допустимые решения, наряду с соответствующими значениями k.
Некоторые паттерны прыгают довольно быстро. Списки нечетного размера поддерживают только k = 0. Списки равного размера интересны: присмотритесь, например, к размерам 6 и 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()
Вывод для 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)