Как создать перестановку?

Question

Мой вопрос: задан список L длины n и целое число i такое, что 0 <= i <n !, как вы можете написать функцию perm (L, n) для получения i-й перестановки L в O(п) время?Под i-й перестановкой я подразумеваю просто i-ю перестановку в некотором порядке, определенном реализацией, который должен иметь свойства: </p>

1. Для любых i и любых 2 списков 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-й элемент.

Answer 1

def perm(sequence, index):
    sequence = list(sequence)
    result = []
    for x in xrange(len(sequence)):
        idx = index % len(sequence)
        index /= len(sequence)
        result.append( sequence[idx] )
        # constant time non-order preserving removal
        sequence[idx] = sequence[-1]
        del sequence[-1]
    return result

Основан на алгоритме тасования, но каждый раз мы берем наименее значимую часть числа, чтобы решить, какой элемент взять вместо случайного числа.В качестве альтернативы рассмотрите это как проблему преобразования в некоторую произвольную базу, за исключением того, что базовое имя уменьшается для каждой дополнительной цифры.

Answer 2

Не могли бы вы использовать factoradics ?Вы можете найти иллюстрацию в этой статье MSDN .

Обновление: я написал расширение алгоритма MSDN , которое находит i-ю перестановку из n вещей, взятых ввремя, даже если n! = r.

Answer 3

Вычислительный минималистический подход (написанный на псевдокоде в стиле C):

function perm(list,i){
    for(a=list.length;a;a--){
        list.switch(a-1,i mod a);
        i=i/a;
    }
    return list;
}

Обратите внимание, что реализации, основанные на удалении элементов из исходного списка, как правило, выполняются за O (n ^ 2) времени, в лучшем случае O (n * log (n)), учитывая специальную реализацию списка стилей дерева, предназначенную для быстрой вставки и удаления элементы списка.

Приведенный выше код, вместо того, чтобы сжимать исходный список и поддерживать его в порядке, просто перемещает элемент из конца в вакантное место, по-прежнему создает идеальное отображение 1: 1 между индексом и перестановкой, чуть более скремблированный, но в чистое время O (n).

Answer 4

Итак, я думаю, что наконец решил это.Прежде чем читать какие-либо ответы, я опубликую свои собственные здесь.

def perm(L, i):
  n = len(L)
  if (n == 1):
    return L
  else:
    split = i%n
    return [L[split]] + perm(L[:split] + L[split+1:], i/n)

Answer 5

Есть n! Перестановки. Первый символ может быть выбран из L n способов. Каждый из этих вариантов оставляет (n-1)! перестановки среди них. Так что этой идеи достаточно для установления порядка. В общем, вы выясните, в какой части вы находитесь, выберите соответствующий элемент, а затем выполните рекурсивный цикл на меньшем L.

Аргумент, что это работает правильно, является индукцией по длине последовательности. (эскиз) Для длины 1 это тривиально. Для длины n вы используете вышеприведенное наблюдение, чтобы разбить задачу на n частей, каждая с вопросом о L 'с длиной (n-1). По индукции все L построены правильно (и за линейное время). Тогда ясно, что мы можем использовать IH для построения решения для длины n.