Faça uma permutação sem dois inteiros consecutivos próximos um do outro

18

Desafio

Dado um número inteiro n ≥ 4 , imprima uma permutação dos números inteiros [0, n-1] com a propriedade de que não há dois números inteiros consecutivos (números inteiros com diferença absoluta 1) próximos um do outro.

Exemplos

  • 4[1, 3, 0, 2]
  • 5[0, 2, 4, 1, 3]
  • 6[0, 2, 4, 1, 3, 5]
  • 7[0, 2, 4, 1, 5, 3, 6]

Você pode usar a indexação 1 em vez disso (usando números inteiros [1, n] em vez de [0, n-1] ).

Seu código deve ser executado no tempo polinomial em n , para que você não possa tentar todas as permutações e testar cada uma.

Anush
fonte
Quando você diz "gerar uma permutação", você quer dizer uma lista? Ou podemos produzir uma função que implemente o próprio mapeamento de permutação?
Xnor
@xnor Deve ser produzido de alguma forma legível por humanos. Eu não ligo exatamente como.
Anush
Seria [[1,3],[0,2]]um formato de saída aceitável?
Salsicha
@ Shaggy Não é ótimo. Isso significa 1,3,0,2?
Anush
Relacionado
Peter Taylor

Respostas:

31

Geléia , 3 2 bytes

ḂÞ

Classifica os números inteiros em [1, ..., n] por seus LSB.

Experimente online!

Dennis
fonte
Uau! Isso é incrível.
Anush
2
“Classificar por LSB” significa que todos os outros se mudam para o início, mas a definição de Jelly exige que os números em cada metade permaneçam em sua ordem original? Caso contrário, 100 (4) pode estar próximo a 101 (5) e ainda ser "classificado por LSB". Não está com defeito no seu código, mas talvez o comentário descritivo não esteja completo?
WGroleau
1
@WGroleau Sim, Þclassificação estável, porque é implementada usando a sortedfunção Python , que é garantida como estável .
User202729
3
O algoritmo é mais impressionante para mim do que o tamanho pequeno, em sua esperteza. Suponho que você também poderia inverter a ordem dos bits, classificar e inverter novamente.
WGroleau
4
Só pode haver 65536 programas diferentes de dois bytes de geléia. É incrível que muitos deles sejam respostas aos desafios do ppcg.
Anush 15/05/19
8

Python 3 , 40 , 38 bytes

lambda n:[*range(1,n,2),*range(0,n,2)]

Experimente online!

Isso corre no O(n)tempo.

Agradecimentos a Dennis por economizar 2 bytes!

DJMcMayhem
fonte
Vencedor do prêmio mais rápido! :)
Anush
Execução mais rápida ou publicado pela primeira vez?
WGroleau
2
@WGroleau Publicado pela primeira vez.
User202729 de
6

Haskell, 22 bytes

f é uma função de n que retorna uma lista ordenada adequadamente. Estou usando a opção de indexação 1.

f n=[2,4..n]++[1,3..n]
Penguino
fonte
6

Oitava , 17 bytes

@(x)[2:2:x,1:2:x]

Experimente online!

Isso usa a mesma abordagem que muitas outras. Concatene dois vetores, um com todo o número par no intervalo inclusivo 2 ... x e todos os números ímpares no intervalo inclusivo 1 ... x . A sintaxe deve ser bastante óbvia, então não vou explicar isso.

Stewie Griffin
fonte
1
Não estão 3e 2um ao lado do outro f(4)?
Pajonk
Opa ... consertado. Contagem de mesmos bytes. :-)
Stewie Griffin
5

JavaScript (ES6), 40 bytes

f=
n=>[...Array(i=n)].map(_=>(i+--i)%(n|1))
<input type=number min=4 oninput=o.textContent=f(+this.value).join`\n`><pre id=o>

Editar: salvou 1 byte graças a @Arnauld.

Neil
fonte
5

Gaia , 2 bytes

r∫

Experimente online!

Este simplesmente (estável) ORTS os inteiros no intervalo [1, entrada] por sua pa r dade.

Mr. Xcoder
fonte
O mesmo comentário de Jelly: o algoritmo ou a definição da linguagem garante que as duas metades permaneçam na sua ordem original?
WGroleau
@WGroleau Sim, em Gaia, o meta-operador de classificação é estável.
Sr. Xcoder
5

R , 39 36 35 bytes

function(x)c(seq(2,x,2),seq(1,x,2))

Experimente online!

ngm
fonte
Existe um NA à direita para números ímpares.
JayCe
Culpa da esposa. Tivemos que ir no nosso passeio de bicicleta antes que eu pudesse consertar isso. Mas você raspou alguns bytes também.
ngm
Sim, eu me senti mal pedindo para você adicionar bytes, então tive que encontrar uma maneira de remover alguns ... funcionou bem.
JayCe
4

Japonês, 4 bytes

Você também pode substituir uporv para obter um pedido diferente.

õ ñu

Tente

Ou, se pudermos produzir uma matriz de 2 matrizes:

õ ó

Tente

Shaggy
fonte
Tecnicamente, o segundo gera uma lista de números separados por vírgulas ;-) Ambos falham 4, infelizmente; você pode corrigir o primeiro alterando upara vou opara õ.
ETHproductions
3

Mathematica, 50 -> 47 -> 42 bytes

p = Join[Range[2, #, 2], Range[1, #, 2]] &

Experimente online!

Agradecemos a user202729 por apontar o potencial de otimização duplo Join [] instalado do Flatten [] e usar funções puras.

Eu gostaria de acrescentar duas observações.

1) É bastante simples construir uma permutação específica sem sucessão decrescente ou crescente para n> = 4, conforme solicitado no PO.

Consiste em duas listas consecutivas.

Para n
iguais, são: list1 = (2,4, ..., n / 2)
list2 = (1,3, ..., n / 2-1)

Para o número ímpar n, temos:
list1 = (2,4, ..., andar [n / 2])
list2 = (1,3, ..., andar [n / 2])

Para esse "algoritmo", apenas uma decisão deve ser tomada (n par ou ímpar), o resto é apenas escrever n números.

Uma possível solução Mathematica é fornecida na parte superior.

2) Uma questão relacionada é quantas dessas permutas existem em função de n.

Mathematica, 124 bytes

a[0] = a[1] = 1; a[2] = a[3] = 0;
a[n_] := a[n] = (n + 1)*a[n - 1] - (n - 2)*a[n - 2] - (n - 5)*a[n - 3] + (n - 3)*a[n - 4]

Experimente online!

Exemplo:

a[#] & /@ Range[4, 12]

{2, 14, 90, 646, 5242, 47622, ​​479306, 5296790, 63779034}

Contar o número de tais permutações é um problema padrão.

Para n = 4, existem 2: {{2,4,1,3}, {3,1,4,2}}

Para n = 5, existem 14: {{1,3,5,2,4}, {1,4,2,5,3}, {2,4,1,3,5}, {2,4, 1,5,3}, {2,5,3,1,4}, {3,1,4,2,5}, {3,1,5,2,4}, {3,5,1, 4,2}, {3,5,2,4,1}, {4,1,3,5,2}, {4,2,5,1,3}, {4,2,5,3, 1}, {5,2,4,1,3}, {5,3,1,4,2}}

O número a (n) dessas permutações aumenta rapidamente: 2, 14, 90, 646, 5242, 47622, ​​479306, 5296790, 63779034, ...

Para n grande, a razão a (n) / n! parece se aproximar do limite 1 / e ^ 2 = 0,135335 ... Não tenho prova estrita, mas é apenas uma conjectura da evidência numérica. Você pode testar isso tentando executar o programa online.

O programa acima (com base na referência fornecida abaixo) calcula esses números.

Você pode encontrar mais informações na sequência relevante em OEIS: A002464 . O problema de Hertzsprung: maneiras de organizar n reis não atacantes em um tabuleiro n X n, com 1 em cada linha e coluna. Também número de permutações de comprimento n sem sucessões crescentes ou decrescentes.

Dr. Wolfgang Hintze
fonte
@ Stewie Griffin Como sou novo aqui, explique com mais detalhes o que você quer dizer. Na minha primeira observação, forneci um algoritmo e um código que resolve o problema no tempo polinomial. Por isso, deve ser considerado uma solução para o desafio. A segunda parte estende o problema interessante. Por isso, deve ser considerado como um comentário.
Dr. Wolfgang Hintze
Tomei a liberdade de modificar levemente sua submissão para que seu código Mathematica esteja no topo. Com os desafios do código-golfe, é obrigatório fornecer o código real (o menor possível). A forma como eu a formatei, torna-se uma resposta do Mathematica, como você provavelmente pretendia, e ainda tem sua explicação original abaixo. Se você sentir que algo está faltando ou se eu editei incorretamente sua resposta inicial, sinta-se à vontade para editá-la novamente. Bem-vindo ao PPCG! :)
Kevin Cruijssen
@ Kevin Cruijssen Muito obrigado pela calorosa recepção e pela edição da minha ingênua submissão. Agora adicionei um programa Mathematica para a segunda observação. O que provavelmente não é lege artis. Acima de tudo, não sei como criar o belo link "experimente online".
Dr. Wolfgang Hintze
Qualquer link pode ser criado usando [some text](the_link). Quanto ao link "Experimente online", em particular, o site https://tio.run/ que está sendo hospedado por nosso próprio @Dennis contém links para todos os tipos de linguagens de programação. A Wolfram Language (Mathematica) é uma delas. Na parte superior, você pode clicar no botão de reprodução para executar o código ou no botão de hiperlink para copiar "Experimente online". links (marcação). E você pode dividir seu código em "Código" (seu envio) real, com um cabeçalho / rodapé opcional para (bonita) impressão de um ou vários casos de teste.
Kevin Cruijssen 15/05/19
Desculpas pelo meu comentário um tanto franco e falta de resposta depois disso! A resposta apareceu na fila de revisão e não notei o código por causa da formatação. Não é incomum que novos usuários publiquem "observações interessantes" para os desafios, sem fornecer uma resposta real. Embora seja feito de boa fé, não é para isso que o site é. Eu pensei que isso fosse uma resposta. Eu deveria ter respondido ao seu comentário, mas estava com pressa e não consegui escrever um novo comentário; por isso, acabei de remover o antigo. Desculpas! E bem-vindo ao site! Espero que você fique por aqui! :)
Stewie Griffin
2

Ruby , 27 bytes

->n{[*2.step(n,2)]|[*1..n]}

Experimente online!

Usando indexação 1

GB
fonte
2

Espaço em branco , 161 bytes

Aqui está o envio oficial e não comentado: Experimente online!

push_0   
read_n	
		push_0   
retreive_n			push_1  		
subtract	   dup_and_out[ 
 	
 	]label_s'
   
'push_2  		 
subtract	   dup[ 
 ]jump_next_if_neg:
		  
:dup_and_out[ 
 	
 	]else_jump_back:
 
 
:label_ss'
    
'push_0   
retreive_n			push_2  		 
subtract	   dup_and_out[ 
 	
 	]dup[ 
 ]jump_next:
 
    
:label_ssss'
      
'push_2  		 
subtract	   dup[ 
 ]jump_end_if_neg:
		   
:dup_and_out[ 
 	
 	]else_jump_back:
 
    
:label_sss'
     
'end



Experimente online!

Eu sacrifiquei alguns bytes para que o programa fosse executado sem erros, acredito que poderia perder cerca de 7-8 bytes, e ele ainda seria exibido corretamente, mas também enviaria mensagens de erro, e ninguém quer isso.

Explicação completa de bytes:

[Space][Space][Space][N]                   Push a 0 on the stack
[Tab][Tab][N][Tab][Tab][Tab][Tab]          Read input value and store in heap
[Space][Space][Space][N]                   Push a 0 on the stack again
[Tab][Tab][Tab]                            Retrieve the value from the heap
[Space][Space][Tab][Tab][N]                Push a -1 on the stack
[Tab][Space][Space][Space]                 Add -1 to value
[Space][N][Space]                          Duplicate 
[Tab][N][Space][Tab]                       Output
[N][Space][Space][Space][N]                Set First Label
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 Subtract 2 from value
[Space][N][Space]                          Duplicate
[N][Tab][Tab][Space][Space][N]             If negative, jump to second label
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[N][Space][N][Space][N]                    Jump back to first label
[N][Space][Space][Space][Space][N]         Set Second Label
[Space][Space][Space][N]                   Push a 0 on the stack
[Tab][Tab][Tab]                            Retrieve input value from heap again
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 This time, Add a -2 to the value
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[Space][N][Space]                          Duplicate
[N][Space][N][Space][Tab][N]               Jump to third label
[N][Space][Space][Space][Tab][N]           Set third label
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 Subtract 2 from value
[Space][N][Space]                          Duplicate
[N][Tab][Tab][Space][Space][Space][N]      Jump to end if negative
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[N][Space][N][Space][Tab][N]               Jump back to third label
[N][Space][Space][Space][Space][Space][N]  Set fourth label/end
[N][N][N]                                  Terminate
X1M4L
fonte
Algumas coisas para o golfe: push_0, read_STDIN_as_int, push_0, retrievepode ser push_0, duplicate_0, read_STDIN_as_int, retrievepara salvar um byte. E o primeiro rótulo pode ser vazio com em NSSNvez de NSSSN(e o segundo rótulo pode ser NSSSN; terceiro NSSTN; e quarto NSSSSN). Isso deve economizar 8 bytes também. Além disso, você pode remover o primeiro Jump_to_third_labelporque já tem o Set_third_labeldireito abaixo. No total: 140 bytes ; (ou com comentários: experimente online .) -3 bytes se você remover a NNNsaída.
Kevin Cruijssen 15/05/19
1

Gol> <> , 14 bytes

FL:2%Z}:3=?$|B

Experimente online!

Exemplo de programa completo e como funciona

1AGIE;GDlR~
FL:2%Z}:3=?$|B

1AG          Register row 1 as function G
   IE;       Take number input; halt on EOF
      GD     Call G and print the stack
        lR~  Empty the stack
             Repeat indefinitely

F           |   Repeat n times...
 L              Push loop counter (0..n-1)
  :2%Z}         If even, move to bottom of the stack
       :3=?$    If top == 3, swap top two
                  This is activated only once to make [2 0 3 1]
             B  Return
Bubbler
fonte
1

J , 10 bytes

i./:2|1+i.

Experimente online!

Explicação:

  /:          sort
i.            the numbers in the range 0..n-1 
    2|        according the remainder mod 2 of 
      1+i.    the numbers in the range 1..n   
Galen Ivanov
fonte
1

Java 8, 56 bytes

n->{for(int i=n;i>0;)System.out.println((i+--i)%(n|1));}

Porta da resposta JavaScript (ES6) do @Neil .

Experimente online.


Resposta antiga de 66 bytes:

n->{String[]r={"",""};for(;n-->0;)r[n%2]+=n+" ";return r[0]+r[1];}

Experimente online.

Explicação:

n->{                  // Method with integer parameter and String return-type
  String[]r={"",""};  //  Result-Strings, both starting empty
  for(;n-->0;)        //  Loop in the range (n, 0]
    r[i%2]+=i+" ";    //   Append `i` and a space to one of the two result-Strings,
                      //   depending on if it is even (first) or odd (second)
  return r[0]+r[1];}  //  Return the two result-Strings appended to each other
Kevin Cruijssen
fonte
1

Ruby, 27 bytes

->n{(1..n).sort_by{|i|i&1}}

Como nesta resposta , os nprimeiros números inteiros são classificados pelo seu bit menos significativo.

Experimente online!

Eric Duminil
fonte