Introdução
As permutações lexicográficas de uma lista com n elementos podem ser numeradas de 0 a n ! - 1. Por exemplo, os 3! = 6 permutações de (1,2,3)
seria(1,2,3)
, (1,3,2)
, (2,1,3)
, (2,3,1)
, (3,1,2)
, (3,2,1)
.
Quando uma permutação é aplicada a uma lista, seus elementos são ordenados na mesma ordem que os números na permutação. Por exemplo, aplicando a permutação (2,3,1)
aos l = (a,b,c)
rendimentos (l[2],l[3],l[1]) = (b,c,a)
.
O inverso de uma permutação é definido como a permutação que reverte essa operação, ou seja, aplicar uma permutação e, em seguida, seu inverso (ou vice-versa) não modifica a matriz. Por exemplo, o inverso de(2,3,1)
é (3,1,2)
, uma vez que aplica isso a (b,c,a)
rendimentos (a,b,c)
.
Além disso, o inverso de uma permutação aplicado à própria permutação produz os números inteiros 1… n . Por exemplo, aplicando (3,1,2)
a (2,3,1)
rendimentos (1,2,3)
.
Agora, definimos a função revind ( x ) como o índice da permutação inversa da permutação com index x . (Este é o A056019 , se você estiver interessado.)
Como uma permutação com o índice i modifica apenas os últimos k itens da lista, se 0 ≤ i < k !, Podemos adicionar qualquer número de elementos ao início da lista sem afetar revind ( i ). Portanto, o comprimento da lista não afeta o resultado.
Desafio
Sua tarefa é implementar revind ( x ). Você escreverá um programa ou função completo que usa um único número inteiro não negativo x como entrada / argumento e gera / retorna o resultado como um único número inteiro não negativo.
A entrada e a saída podem ser indexadas em 0 ou 1, mas isso deve ser consistente entre elas.
Builtins que geram permutações por índice, retornam o índice de uma permutação ou descobrem que a permutação inversa são banidos. (Construções que geram todas as permutações ou a próxima permutação são permitidas.)
Aplicam-se as regras padrão de código de golfe .
Exemplos
Os exemplos abaixo são indexados em 0.
Input Output
0 0
1 1
2 2
3 4
4 3
5 5
6 6
13 10
42 51
100 41
1000 3628
2000 3974
10000 30593
100000 303016
Implementação de referência (Python 3)
def revind(n):
from math import factorial
from itertools import permutations, count
l = next(filter(lambda x: factorial(x) > n, count(1)))
pms = list(permutations(range(l)))
return [k for k in range(len(pms)) if tuple(pms[n][i] for i in pms[k]) == pms[0]][0]
fonte
(a,b,c)
extremamente claro. Inclua uma explicação adequada do que é uma permutação inversa.Ụ
(classificação acima) que classifica os índices de uma matriz pelos seus valores correspondentes. Isso acontece para inverter uma permutação de 1,…, n , mas não funciona para outras permutações. ÉỤ
um built-in proibido?Respostas:
Gelatina , 6 bytes
AE / S usa indexação baseada em 1. Muito lento e com fome de memória.
Verificação
Enquanto a entrada não exceder 8! = 40320 , é suficiente considerar todas as permutações da matriz [1,…, 8] . Para o último caso de teste, as permutações de [1,…, 9] são suficientes.
Com código ligeiramente modificado que considera apenas as permutações dos primeiros 8 ou 9 números inteiros positivos, você pode experimentar online!ou verifique todos os casos de teste restantes .
Como funciona
Abordagem alternativa, 6 bytes (inválido)
É tão longo e usa o proibido átomo de grau
Ụ
, mas é (sem dúvida) mais idiomático.Anexando 8 (ou 9 para o último caso de teste), podemos realmente experimentá-lo online!
Como funciona
fonte
Mathematica, 74 bytes
Usa indexação 1. Muito ineficiente. (usa ~ 11 GB de memória quando a entrada é
11
)Explicação
Gere uma lista de 1 a N. Armazene isso em
j
.Encontre todas as permutações de
j
. Armazene isso emi
.Armazenar a
Position
funçãok
. (para reduzir a contagem de bytes ao usarPosition
novamente)Encontre a permutação inversa da N-ésima permutação.
Encontre o
k
(Position
) da permutação inversa emi
(todas as permutações)Usando built-ins,
4643 bytes1 indexado.
fonte
MATL , 15 bytes
Entrada e saída são baseadas em 1.
Semelhante à resposta CJam do @ MartinEnder , mas encontra a permutação inversa compondo todas as permutações possíveis com a especificada pela entrada e vendo qual se tornou a permutação de identidade.
Ele fica sem memória no compilador online para entrada
10
.Experimente online!
Explicação
fonte
Pitão, 12 bytes
Suíte de teste
0 indexado.
Explicação:
fonte
05AB1E ,
1413 bytesMuito memória ineficiente.Agora, ainda mais memória ineficiente (mas 1 byte menor).Intervalo baseado em 0.
Usa a codificação CP-1252 .
Experimente online! ou como um conjunto de testes modificado
Explicação
fonte
CJam , 16 bytes
Os índices são baseados em 0.
Experimente online!
Eu não fico muito mais ineficiente do que isso ... fica sem memória com as configurações padrão do Java para entradas maiores que
8
(mas funciona em princípio para entradas arbitrárias, dado um número suficiente de universos de tempo e memória).Explicação
fonte
GAP , 108 bytes
1 indexado. Novas linhas não são contadas, não são necessárias. Eu realmente não tenho que atribuir a função final a um nome, mas ...
h
é uma função ao curry que pega uma lista de permutações e um índice nessa lista e retorna o índice da permeação inversa. Sem restrições, eu apenas fariaPosition(l,l[n]^-1)
.f
chama essa função com as permutações ordenadas de um grupo simétrico suficientemente grande e o dadon
.Eu poderia escrever
SymmetricGroup(n)
, então a função poderia ser calculada para valores até 9. Como já existem soluções muito menores, prefiro poder fazer isso:Uma solução realmente eficiente, indexada a 0, que funciona para argumentos abaixo de 99! (e pode funcionar para argumentos abaixo de 999! ao custo de um byte) é este:
Após excluir o espaço em branco, isso tem 255 bytes.
fonte
JavaScript (ES6),
163120110 bytesIndexado a 0. Funciona convertendo o índice em uma permutação, invertendo-o e convertendo-o novamente em um índice. Editar: economizou cerca de 25% ao
f
inverter e reverter a permutação e, em seguida,g
converter a permutação revertida em um índice. Economizou mais 10 bytes combinando as duas chamadas recursivas em uma única função. Ungolfed:fonte
f
inverter a permutação em vez deg
...J,
5550 bytesBaseado no ensaio J sobre Índice de Permutação .
Esse código requer apenas memória na ordem de,
n
mas usa mais tempo, pois classifica osn
tempos da lista e os pesquisan
por cada índice.Usando o built-in
/:
que é capaz de encontrar o grau de uma lista e o inverso de uma permutação, existe uma solução de 42 bytes que é mais eficiente.Esta versão requer apenas 44 segundos para calcular o último caso de teste quando comparado com o outro, que requer 105 segundos.
Uso
fonte
Geléia ,
14 139 bytes-4 bytes, graças ao @ Dennis (que ele jogou golfe usando ainda mais a rápida
⁺
em sua resposta )Outra implementação muito lenta.
Indexação baseada em 1 empregada aqui, portanto, os resultados esperados são:
Não faz sentido colocar um link IDE online, pois o TIO mata com uma entrada de
10
. Resultados locais (o último é muito lento e requer uma tonelada de memória!):Quão?
Nota: não há necessidade de classificar as permutações, pois estamos usando a mesma ordem para encontrar a permutação ee é inversa.
fonte
ÇịịÇ$iR
?R
antesŒ!
está implícito, por issoŒ!ịịŒ!$iR
deve fazer o trabalho.Python 2,
116114 bytesrepl.it
Baseado em 0. Lento e com fome de memória, mas com poucos bytes.
Usando nenhuma função de permutação; memória e tempo eficientes.
289285 bytes-4 bytes graças a @Christian Sievers (permutação total já formada)
Eu sei que é código de golfe, mas acho que @ Pietu1998 também está interessado em implementações eficientes.
Veja em ação em repl.it
Embora isso use mais bytes que a implementação de referência, comparando com
n=5000000
:f
é a função de índice reverso.f
primeiro obtém o próximo fatorial aciman
,t
e o número inteiro cujo fatorial,x
chamandoh(n)
e defineg=range(x)
os itens que compõem a permutação,o=g[:]
e o detentor da permutação,r=[]
A seguir constrói a permutação no índice
n
porpop
ing os índices da base de representação de fatorialn
por sua vez a partir dos itens,o
e anexando-os ar
. A representação da base fatorial é encontrada por div e mod den
comt
ondet
é div'd porx
ex
diminui para baixo1
.Finalmente, ele encontra o índice da permutação reversa chamando
i
com a permutação reversa,[r.index(v)for v in g]
h
é uma função de dupla finalidade para calcular um fatorial de um número inteiro não negativo ou calcular o próximo fatorial acima de um número inteiro não negativo e o número inteiro que faz esse fatorial.Em seu estado padrão
v=1
e faz o último multiplicandov
porx
(também inicialmente1
) e aumentandox
até quen
seja pelo menos tão grande, então ele retornav
ex-1
em uma tupla.Para calcular
n!
uma chamadah(n,0)
que multiplicax
(inicialmente1
) porn
e diminuin
atén
é0
quando ela retornax
.i
fornece o índice lexicográfico de uma permutação,p
dos itens[0,1,...n]
, somando os produtos do fatorial da base fatorial de cada índiceh(len(p)-j-1,0)
e quantos itens à direita do índice são menores que o valor nesse índicesum(k<p[j]for k in p[j+1:])
.fonte
t/=x
.(r+o)
porr
.Python 2,
130129 bytesfonte
Na verdade ,
1811 bytesEssa resposta usa o algoritmo da resposta de Dennis 'Jelly, mas é indexada em 0. Sugestões de golfe são bem-vindas! Experimente online!
Ungolfing
fonte