Вступление

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

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

Задание

Ваша задача - написать именованную функцию (или ближайший эквивалент), f которая принимает в качестве входных данных положительное целое число nи перестановку pпервых nцелых чисел, используя индексацию на основе 0 или 1. Его вывод - перестановка p. Однако вам не разрешен pпрямой доступ к перестановке . Единственное, что вы можете сделать с ним, это применить его к любому вектору nбитов. Для этой цели вы должны использовать вспомогательную функцию, Pкоторая принимает перестановку pи вектор битов vи возвращает переставленный вектор, в чьей p[i]координате которого содержится бит v[i]. Например:

P([1,2,3,4,0], [1,1,0,0,0]) == [0,1,1,0,0]

Вы можете заменить «биты» любыми двумя различными значениями, такими как 3и -4, или 'a'и 'b', и они не должны быть фиксированными, так что вы можете вызывать Pоба [-4,3,3,-4]и [2,2,2,1]в одном вызове f. Определение Pне засчитывается в ваш счет.

счет

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

В этом репозитории вы найдете файл с именем, permutations.txtкоторый содержит 505 перестановок, по 5 каждой длины от 50 до 150 включительно, с использованием индексации на основе 0 (увеличивайте каждое число в случае на основе 1). Каждая перестановка находится на отдельной строке, а ее номера разделены пробелами. Ваша оценка - количество байтов f+ средняя сложность запроса на этих входных данных . Самый низкий балл побеждает.

Дополнительные правила

Код с пояснениями предпочтителен, а стандартные лазейки запрещены. В частности, отдельные биты неразличимы (поэтому вы не можете задавать вектор Integerобъектов Pи сравнивать их идентичности), и функция Pвсегда возвращает новый вектор, а не переупорядочивает свои входные данные. Вы можете свободно изменять имена fи P, и порядок, в котором они принимают свои аргументы.

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

def f(n,p):
    pass # Your submission goes here

num_calls = 0

def P(permutation, bit_vector):
    global num_calls
    num_calls += 1
    permuted_vector = [0]*len(bit_vector)
    for i in range(len(bit_vector)):
        permuted_vector[permutation[i]] = bit_vector[i]
    return permuted_vector

num_lines = 0
file_stream = open("permutations.txt")
for line in file_stream:
    num_lines += 1
    perm = [int(n) for n in line.split()]
    guess = f(len(perm), perm)
    if guess != perm:
        print("Wrong output\n %s\n given for input\n %s"%(str(guess), str(perm)))
        break
else:
    print("Done. Average query complexity: %g"%(num_calls/num_lines,))
file_stream.close()

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

J 44,0693 22,0693 = 37 15 + 7,06931

Если мы не можем назвать Pна i. n, мы можем по крайней мере вызова Pна каждый бит i. nотдельно. Количество вызовов Pявляется >. 2 ^. n(⌈log ₂  n ⌉). Я считаю, что это оптимально.

f=:P&.|:&.#:@i.

Вот реализация функции, Pкоторая использует вектор перестановки pи сохраняет количество вызовов в Pinv.

P =: 3 : 0"1
 Pinv =: Pinv + 1
 assert 3 > # ~. y    NB. make sure y is binary
 p { y
)

Вот тестирование, которое получает перестановку и возвращает количество вызовов p:

harness =: 3 : 0
 Pinv =: 0
 p =: y
 assert y = f # y     NB. make sure f computed the right permutation
 Pinv
)

И вот как вы можете использовать его в файле permutations.txt:

NB. average P invocation count
(+/ % #) harness@".;._2 fread 'permutations.txt'

объяснение

Краткое объяснение уже приведено выше, но вот более подробное. Во-первых, fс вставленными пробелами и в качестве явной функции:

f =: P&.|:&.#:@i.
f =: 3 : 'P&.|:&.#: i. y'

Читать:

Позволять f будет P при транспонировании в base-2 представления первых y целых чисел.

где у - формальный параметр для f. в J параметры функции (функции) называются x и y, если глагол двоичный (имеет два параметра), и y, если он монадический (имеет один параметр).

Вместо того, чтобы ссылаться Pнаi. n (т.е. 0 1 2 ... (n - 1)), мы вызываем Pна каждой битовой позиции чисел в i. n. Поскольку все перестановки переставляются одинаково, мы можем собрать переставленные биты в числа, чтобы получить вектор перестановки:

• i. yЦелые числа от 0до y - 1.

• #: y- yпредставлен в базе 2. Это распространяется на векторы чисел естественным образом. Например, #: i. 16дает:

  0 0 0 0
  0 0 0 1
  0 0 1 0
  0 0 1 1
  0 1 0 0
  0 1 0 1
  0 1 1 0
  0 1 1 1
  1 0 0 0
  1 0 0 1
  1 0 1 0
  1 0 1 1
  1 1 0 0
  1 1 0 1
  1 1 1 0
  1 1 1 1
  

• #. y - y интерпретируется как базовое число 2 Примечательно, что это обратное к #:; y ~: #. #:всегда держит.

• |: y- yтранспонирован.

• u&.v y- uпод v, то есть vinv u v yгде vinvобратное v. Заметить, что|: это его собственная обратная сторона.

• P y- функция, Pпримененная к каждому вектору yпо определению.

Pyth 32 + 7,06931 = 37,06931

Я нашел следующий алгоритм полностью независимым. Но это более или менее то же самое, что и очень короткое J-решение FUZxxl (насколько я понимаю).

Сначала определение функции P, которая переставляет битовый массив в соответствии с неизвестной перестановкой.

D%GHJHVJ XJ@HN@GN)RJ

А затем код, который определяет перестановку.

Mmxmi_mbk2Cm%dHCm+_jk2*sltG]0GdG

Это определяет функцию g, которая принимает два аргумента. Вы можете позвонить по g5[4 2 1 3 0. Вот онлайн демонстрация . Никогда не использовал так много (5) вложенных карт.

Кстати, я на самом деле не сделал тестовый комплект. Также функция не Pсчитает, сколько раз я ее вызываю. Я потратил много времени на то, чтобы понять алгоритм. Но если вы прочитаете мое объяснение, то совершенно очевидно, что он использует int(log2(n-1)) + 1звонки ( = ceil(log2(n))). И sum(int(log2(n-1)) + 1 for n in range(50, 151)) / 101.0 = 7.069306930693069.

Объяснение:

На самом деле мне было довольно трудно найти этот алгоритм. Мне вообще было не ясно, как этого добиться log(n). Поэтому я начал проводить эксперименты с маленькими n.

Первое примечание: битовый массив собирает ту же информацию, что и битовый массив дополнения. Поэтому все битовые массивы в моем решении имеют максимально n/2активный бит.

n = 3:

Поскольку мы можем использовать только битовый массив с 1 активным битом, оптимальное решение зависит от двух вызовов. Например P([1, 0, 0])и P([0, 1, 0]). Результаты сообщают нам первое и второе число перестановок, косвенно мы получаем третий.

n = 4:

Здесь это немного интереснее. Теперь мы можем использовать два вида битовых массивов. Те с 1 активным битом и те с 2 активными битами. Если мы используем битовый массив с одним активным битом, мы собираем информацию только об одном номере перестановки и возвращаемся к нему n = 3, что приводит к 1 + 2 = 3вызовам P. Интересно то, что мы можем сделать то же самое только с двумя вызовами, если мы используем битовые массивы с двумя активными битами. Например P([1, 1, 0, 0])иP([1, 0, 1, 0]) .

Допустим, мы получаем результаты [1, 0, 0, 1]и [0, 0, 1, 1]. Мы видим, что бит 4 активен в обоих выходных массивах. Единственным битом, который был активен в обоих входных массивах, был бит номер 1, поэтому очевидно, что перестановка начинается с 4. Теперь легко видеть, что бит 2 был перемещен в бит 1 (первый вывод), а бит 3 был перемещен в бит 3 (второй вывод). Поэтому перестановка должна быть [4, 1, 3, 2].

n = 7:

Теперь что-то большее. Я покажу вызовы Pсразу. Это то, что я придумал после небольшого размышления и экспериментов. (Обратите внимание, что это не те, которые я использую в своем коде.)

P([1, 1, 1, 0, 0, 0, 0])
P([1, 0, 0, 1, 1, 0, 0])
P([0, 0, 1, 1, 0, 1, 0])

Если в первых двух выходных массивах (а не в третьем) бит 2 активен, мы знаем, что перестановка перемещает бит 1 в бит 2, поскольку бит один является единственным битом, который активен в первых двух входных массивах.

Важно то, что (интерпретируя входные данные как матрицу) каждый из столбцов уникален. Это запомнилось мне на кодах Хэмминга , где то же самое достигается. Они просто принимают числа от 1 до 7 и используют свое битовое представление в качестве столбцов. Я буду использовать числа от 0 до 6. Теперь хорошая часть, мы можем снова интерпретировать выходные данные (снова столбцы) как числа. Они говорят нам результат применения перестановки [0, 1, 2, 3, 4, 5, 6].

   0  1  2  3  4  5  6      1  3  6  4  5  0  2
P([0, 1, 0, 1, 0, 1, 0]) = [1, 1, 0, 0, 1, 0, 0]
P([0, 0, 1, 1, 0, 0, 1]) = [0, 1, 1, 0, 0, 0, 1]
P([0, 0, 0, 0, 1, 1, 1]) = [0, 0, 1, 1, 1, 0, 0]

Так что нам осталось только отследить числа. Бит 0 заканчивался битом 5, бит 1 заканчивался битом 0, бит 2 заканчивался битом 6, так что перестановка была [5, 0, 6, 1, 3, 4, 2].

Mmxmi_mbk2Cm%dHCm+_jk2*sltG]0GdG
M                                 define a function g(G, H), that will return
                                  the result of the following computation:
                                  G is n, and H is the permutation. 
                m            G     map each k in [0, 1, ..., Q-1] to:
                  _                   their inverse
                   jk2                binary representation (list of 1s and 0s)
                 +                    extended with 
                      *sltG]0         int(log2(Q - 1)) zeros
               C                   transpose matrix # rows that are longer 
                                                   # than others are shortened
           m%dH                    map each row (former column) d of 
                                   the matrix to the function P (here %)
          C                        transpose back
   m                              map each row k to:                         
    i    2                           the decimal number of the 
     _mbk                            inverse list(k) # C returns tuple :-(
Let's call the result X.  
 m                             G   map each d in [0, 1, ..., Q - 1] to:
  x         X                 d       the index of d in X

И код для функции перестановки:

D%GHJHVJ XJ@HN@GN)RJ
D%GH                     def %(G, H):  # the function is called %
    JH                     J = copy(H)
      VJ         )        for N in [0, 1, ..., len(J) - 1]: 
         XJ@HN@GN            J[H[N]] = G[N]           
                  RJ      return J

Mathematica, 63 + 100 = 163

Я использую перестановки на одной основе, поскольку именно так работает индексация в Mathematica.

Сначала тестовый жгут. Это функция запросаp (определяемые пользователем имена не должны быть в верхнем регистре в Mathematica):

p[perm_, vec_] := (
   i += 1;
   vec[[Ordering@perm]]
   );

И подготовка ввода вместе с тестовой петлей:

permutations = 
  ToExpression@StringSplit@# + 1 & /@ 
   StringSplit[Import[
     "https://raw.githubusercontent.com/iatorm/permutations/master/permutations.txt"
   ], "\n"];
total = 0;
(
    i = 0;
    result = f@#;
    If[# != result, 
      Print["Wrong result for ", #, ". Returned ," result ", instead."]
    ];
    total += i;
    ) & /@ permutations;
N[total/Length@permutations]

И, наконец, мое фактическое представление, которое пока использует наивный алгоритм:

f=(v=0q;v[[#]]=1;Position[q~p~v,1][[1,1]])&/@Range@Length[q=#]&

Или с отступом:

f = (
     v = 0 q;
     v[[#]] = 1;
     Position[q~p~v, 1][[1, 1]]
) & /@ Range@Length[q = #] &