Solução por Lúcio Figueiredo
Conhecimento prévio necessário:
Perceba que não existem permutações bonitas para $$n = 2$$ e $$n = 3$$. Para $$n = 1$$, a permutação $${1}$$ é uma resposta válida.
Para todo $$n > 3$$, existe uma permutação válida com $$n$$ elementos. Para demonstrar isso, basta utilizar a seguinte construção:
- Inicialmente, inisira o valor $$2$$ como primeiro elemento da permutação.
- Em seguida, insira todos os números pares maiores que $$2$$ e menores ou iguais a $$n$$.
- Por fim, insira em seguida os números ímpares menores ou iguais a $$n$$.
É fácil ver que a construção acima gera uma permutação bonita, já que não há nenhum par de elementos consecutivos com diferença igual a $$1$$.
Portanto, basta imprimir as três sequências indicadas acima utilizando um loop for. A complexidade final é $$O(n)$$. Confira o código abaixo para melhor entendimento: