Introdução
Suponha que você receba uma permutação aleatória de n
objetos. A permutação é selada em uma caixa; portanto, você não tem idéia de quais são as n!
possíveis. Se você conseguiu aplicar a permutação a n
objetos distintos, poderá deduzir imediatamente sua identidade. No entanto, você só pode aplicar a permutação a n
vetores binários longos , o que significa que precisará aplicá-la várias vezes para reconhecê-la. Claramente, aplicá-lo aos n
vetores com apenas um 1
faz o trabalho, mas se você for inteligente, poderá fazê-lo com log(n)
aplicativos. O código para esse método será mais longo, embora ...
Esse é um desafio experimental em que sua pontuação é uma combinação de tamanho do código e complexidade da consulta , significando o número de chamadas para um procedimento auxiliar. As especificações são um pouco longas, então tenha paciência comigo.
A tarefa
Sua tarefa é escrever uma função nomeada (ou equivalente mais próximo) f
que tome como entrada um número inteiro positivo n
e uma permutação p
dos primeiros n
números inteiros, usando a indexação com base em 0 ou em 1. Sua saída é a permutação p
. No entanto, você não tem permissão para acessar a permutação p
diretamente . A única coisa que você pode fazer com isso é aplicá-lo a qualquer vetor de n
bits. Para esse propósito, você deve usar uma função auxiliar P
que capte uma permutação p
e um vetor de bits v
e retorna o vetor permutado cuja p[i]
th coordenada contém o bit v[i]
. Por exemplo:
P([1,2,3,4,0], [1,1,0,0,0]) == [0,1,1,0,0]
Você pode substituir "bits" por quaisquer dois valores distintos, como 3
e -4
, ou 'a'
e 'b'
, e eles não precisam ser corrigidos, para que você possa chamar P
com os dois [-4,3,3,-4]
e [2,2,2,1]
na mesma chamada para f
. A definição de P
não é contada na sua pontuação.
Pontuação
A complexidade da consulta da sua solução em uma determinada entrada é o número de chamadas feitas para a função auxiliar P
. Para tornar essa medida inequívoca, sua solução deve ser determinística. Você pode usar números gerados pseudoaleatoriamente, mas também deve corrigir uma semente inicial para o gerador.
Em este repositório você encontrará um arquivo chamado permutations.txt
que contém 505 permutações, 5 de cada comprimento entre 50 e 150 inclusive, usando indexação baseada em 0 (incrementar cada número no caso base-1). Cada permutação está em sua própria linha e seus números são separados por espaços. Sua pontuação é a contagem de bytes de f
+ complexidade média da consulta nessas entradas . Menor pontuação ganha.
Regras Extra
O código com explicações é preferido e as brechas padrão não são permitidas. Em particular, os bits individuais são indistinguíveis (portanto, você não pode atribuir um vetor de Integer
objetos P
e comparar suas identidades), e a função P
sempre retorna um novo vetor em vez de reorganizar sua entrada. Você pode alterar livremente os nomes de f
e P
, e a ordem em que eles recebem seus argumentos.
Se você é a primeira pessoa a responder em sua linguagem de programação, é altamente recomendável incluir um equipamento de teste, incluindo uma implementação da função P
que também conta o número de vezes que foi chamada. Como exemplo, aqui está o chicote para o 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()
Em algumas línguas, é impossível escrever tal equipamento. Mais notavelmente, Haskell não permite que a função pura P
registre o número de vezes que é chamada. Por esse motivo, você tem permissão para reimplementar sua solução de forma que ela também calcule sua complexidade de consulta e a use no chicote.
abaaabababaa
e-4 3 3 3 -4 3
seria um vetor de bits.Respostas:
J,
44,069322,0693 =3715 + 7,06931Se não podemos chamar
P
emi. n
, pelo menos podemos chamadaP
em cada bit dei. n
separadamente. O número de invocações deP
é>. 2 ^. n
(log 2 n ). Eu acredito que isso é ótimo.Aqui está uma implementação da função
P
que usa o vetor de permutaçãop
e salva o número de invocaçõesPinv
.Aqui está um chicote de teste que recebe uma permutação e retorna o número de invocações de
p
:E aqui está como você pode usá-lo no arquivo
permutations.txt
:Explicação
A breve explicação já foi fornecida acima, mas aqui está uma mais detalhada. Primeiro,
f
com espaços inseridos e como uma função explícita:Ler:
onde y é o parâmetro formal para f. em J, os parâmetros para um (função) são chamados de x e y se o verbo é dyadic (tem dois parâmetros) e y se é monadic (tem um parâmetro).
Em vez de invocar
P
emi. n
(ou seja0 1 2 ... (n - 1)
), que invocarP
em cada posição dos números de bitsi. n
. Como todas as permutações permutam da mesma maneira, podemos remontar os bits permutados em números para obter um vetor de permutação:i. y
- inteiros de0
atéy - 1
.#: y
-y
representado na base 2. Isso é estendido aos vetores de números da maneira natural. Por exemplo,#: i. 16
produz:#. y
-y
interpretado como um número base 2. Notavelmente, esse é o inverso#:
;y ~: #. #:
sempre segura.|: y
-y
transposto.u&.v y
-u
embaixov
, évinv u v y
aí quevinv
está o inversov
. Observe que|:
é o seu próprio inverso.P y
- a funçãoP
aplicada a cada vetory
por definição.fonte
Pitão 32 + 7,06931 = 37,06931
Eu encontrei o seguinte algoritmo completamente independente. Mas é mais ou menos a mesma coisa que a solução J muito curta do FUZxxl (tanto quanto eu a entendo).
Primeiro, a definição da função
P
, que permite uma matriz de bits de acordo com uma permutação desconhecida.E então o código, que determina a permutação.
Isso define uma função
g
, que recebe dois argumentos. Você pode chamá-lo porg5[4 2 1 3 0
. Aqui está uma demonstração online . Nunca usei tantos (5) mapas aninhados.Btw eu realmente não fiz um equipamento de teste. A função também não
P
conta quantas vezes eu a chamo. Já gastei muito tempo já descobrindo o algoritmo. Mas se você ler minha explicação, é óbvio que ele usaint(log2(n-1)) + 1
calls (= ceil(log2(n))
). Esum(int(log2(n-1)) + 1 for n in range(50, 151)) / 101.0 = 7.069306930693069
.Explicação:
Na verdade, tive muita dificuldade em encontrar esse algoritmo. Não estava claro para mim, como alcançar
log(n)
. Então comecei a fazer algumas experiências com pequenasn
.Primeira nota: uma matriz de bits reúne as mesmas informações que a matriz de bits do complemento. Portanto, todas as matrizes de bits na minha solução têm no máximo
n/2
bit ativo.n = 3:
Como só podemos usar matriz de bits com 1 bit ativo, a solução ideal depende de duas chamadas. Por exemplo,
P([1, 0, 0])
eP([0, 1, 0])
. Os resultados nos dizem o primeiro e o segundo número da permutação, indiretamente, obtemos o terceiro.n = 4:
Aqui fica um pouco interessante. Agora podemos usar dois tipos de matriz de bits. Aqueles com 1 bit ativo e aqueles com 2 bits ativos. Se usarmos uma matriz de bits com um bit ativo, coletamos apenas informações sobre um número da permutação e voltamos a
n = 3
, resultando em1 + 2 = 3
chamadas deP
. A parte interessante é que podemos fazer a mesma coisa com apenas 2 chamadas, se usarmos matrizes de bits com 2 bits ativos. Por exemplo,P([1, 1, 0, 0])
eP([1, 0, 1, 0])
.Digamos que obtemos as saídas
[1, 0, 0, 1]
e[0, 0, 1, 1]
. Vemos que o número de bit 4 está ativo nas duas matrizes de saída. O único bit que estava ativo nas duas matrizes de entrada era o número 1, de modo que a permutação começa claramente4
. Agora é fácil ver que o bit 2 foi movido para o bit 1 (primeira saída) e o bit 3 foi movido para o bit 3 (segunda saída). Portanto, a permutação deve ser[4, 1, 3, 2]
.n = 7:
Agora algo maior. Vou mostrar as ligações
P
imediatamente. Eles são os únicos que eu inventei depois de pensar um pouco e experimentar. (Observe que não são esses que eu uso no meu código.)Se nas duas primeiras matrizes de saída (e não na terceira) o bit 2 estiver ativo, sabemos que a permutação move o bit 1 para o bit 2, já que o bit um é o único bit ativo nas duas primeiras matrizes de entrada.
O importante é que (interpretando as entradas como matriz) cada uma das colunas é única. Isso me lembrou dos códigos de Hamming , onde a mesma coisa é realizada. Eles simplesmente pegam os números de 1 a 7 e usam sua representação de bits como colunas. Vou usar os números de 0 a 6. Agora, a parte legal, podemos interpretar as saídas (novamente as colunas) como números novamente. Eles nos dizem o resultado da permutação aplicada
[0, 1, 2, 3, 4, 5, 6]
.Então, só precisamos rastrear os números. O bit 0 acabou no bit 5, o bit 1 acabou no bit 0, o bit 2 acabou no bit 6, ... Então a permutação foi
[5, 0, 6, 1, 3, 4, 2]
.E o código para a função de permutação:
fonte
*sltQ]0
porm0sltQ
, poderá ter 6 mapas aninhados no mesmo comprimento.f
embora outros nomes sejam permitidos. A tarefa conta para a sua pontuação.g
vez de ler em STDIN.Matemática, 63 + 100 = 163
Estou usando permutações baseadas em uma, já que é assim que a indexação funciona no Mathematica.
Primeiro, o chicote de teste. Esta é a função de consulta
p
(nomes definidos pelo usuário não devem estar em maiúsculas no Mathematica):E preparação de entrada junto com o loop de teste:
E, finalmente, minha submissão real, que usa o algoritmo ingênuo por enquanto:
Ou com recuo:
fonte