Как сгенерировать перестановку?

Мой вопрос: учитывая список L длины n и целое число i такое, что 0 <= i

1. Для любого i и любых двух списков A и B, perm (A, i) и perm (B, i) должны оба отображают j-й элемент A и B в элемент в той же позиции для обоих A и B.

2. Для любых входов (A, i), (A, j) perm (A, i) == perm (A , j) тогда и только тогда, когда i == j.

ПРИМЕЧАНИЕ: это не домашнее задание. На самом деле я решил это 2 года назад, но совершенно забыл, как это сделать, и это меня убивает. Кроме того, вот неудачная попытка решения, которую я предпринял:

def perm(s, i):
  n = len(s)
  perm = [0]*n
  itCount = 0
  for elem in s:
    perm[i%n + itCount] = elem
    i = i / n
    n -= 1
    itCount+=1
  return perm

ТАКЖЕ ПРИМЕЧАНИЕ: требование O (n) очень важно. В противном случае вы могли бы просто сгенерировать n! размер списка всех перестановок и просто вернуть его i-й элемент.