Quadrados latinos seguros para rotação

12

Um quadrado latino é um quadrado que não tenha repetido em símbolos X ou Y colunas . Por exemplo:

ABCD    
DABC
CDAB
BCDA

é um desses quadrados. Observe como cada coluna e linha contém uma permutação das mesmas 4 letras.

No entanto, nosso quadrado latino tem um problema: se eu girasse a segunda linha ( DABC) 1 para a esquerda, terminaria com ABCD, que é idêntico à permutação acima dela. Se for impossível girar uma coluna / linha e obter outra coluna / linha, consideraremos o quadrado como seguro para rotação .

Por exemplo:

ABCD
BDAC
CADB
DCBA

é rotação segura. A grade possui as seguintes propriedades:

  1. O ponto [0, N] usa o enésimo símbolo
  2. Os pontos [0, N] e [N, 0] são sempre o mesmo símbolo . (Gostaria de dizer também que [x, y] e [y, x] também são sempre a mesma letra, mas não posso provar)

Sua tarefa é imprimir um quadrado latino seguro para rotação, quando for aprovado com N. Não me importo se você imprimir letras, números, uma lista ou uma matriz 2D. Se você usar números, a coluna e a linha superiores deverão estar 0,1,2,3,...(nessa ordem). Se você usar letras, deve serA,B,C,D,....

Por exemplo, se sua entrada foi 4, você deve imprimir:

0,1,2,3            0,1,2,3
1,3,0,2     or     1,0,3,2
2,0,3,1            2,3,1,0
3,2,1,0            3,2,0,1

Não há quadrados latinos seguros para rotação com tamanho menor que 4. Não me importo com o que seu programa faz se N for menor que 4. Para os curiosos, o número de quadrados seguros para rotação é (começando em 4): 2,5,5906,(too long to calculate)

Este é um , então tente fazer as respostas o mais curtas possível no seu idioma favorito!

Nathan Merrill
fonte
Existe limite de tempo? (Relacionado: Os métodos de Monte Carlo são permitidos se tecnicamente não houver garantia de término para valores altos Ndevido à qualidade insuficiente do número aleatório?)
Maçaneta da porta
Não há limite de tempo, mas sua solução deve ser garantida para terminar.
Nathan Merrill
1
Para idiomas indexados em 1, a primeira linha pode ser 1,2,3,...?
milhas
@miles sim, tudo bem #
Nathan Merrill

Respostas:

2

Sqlserver 2012 - 918 bytes

Na minha caixa, isso é executado para @k = 5, embora demore 16 segundos.

Este é um código de construção de código (cuidado com a Skynet, você tem concorrência)

Existe um preço para o script mais longo?

DECLARE @k int = 4;

DECLARE @t VARCHAR(max)='WITH C as(SELECT
top '+left(@k,1)+'row_number()over(order by 1/0)n
FROM sys.messages),D(nÆ)as(SELECT
concat(~),~
FROM Ø
WHERE |)SELECT top 1~ FROM Å
WHERE 1=1',@
varchar(999)=''SELECT @+=','+CHAR(x+65)FROM(values(0),(1),(2),(3),(4),(5))x(x)WHERE x<@k
SELECT
@t=REPLACE(REPLACE(REPLACE(REPLACE(@t,'Æ',@),'Ø',STUFF(REPLACE(@,',',',C '),1,1,'')),'Å',STUFF(REPLACE(@,',',',D
'),1,1,'')),'~',STUFF(REPLACE(@,',','.n,'),1,3,'')+'.n'),@='';WITH C as(SELECT top(@k)x
FROM(values(0),(1),(2),(3),(4),(5))x(x))SELECT @+=' AND
'+char(65+C.x)+'.n<>'+char(65+D.x)+'.n'FROM c,c d WHERE C.x<D.x
SELECT @t=REPLACE(@t,'|',STUFF(@,1,4,''));WITH A
as(SELECT top(@k)x
FROM(values(65),(66),(67),(68),(69),(70))x(x))SELECT @t+='AND
'+char(A.x)+'.'+char(C.x)+'<>'+CHAR(B.x)+'.'+char(C.x)+' AND
'+char(A.x)+'.n+'+char(A.x)+'.n'+'
not like''%''+'+char(B.x)+'.n+''%'''FROM A,A B,A C
WHERE A.x<>B.x and C.x<>B.x
EXEC(@t)

Experimente online!

t-clausen.dk
fonte