Beautiful Permutation II

Explicación

Podemos resolver este problema de forma recursiva. En cada índice, buscamos el número más pequeño que cumple la condición pedida (es decir, no hay elementos adyacentes cuya diferencia sea 1) y, si la cumple, lo añadimos a nuestra permutación.

Para $n = 2$ y $n = 3$ , sabemos que ninguna permutación cumple la condición pedida.

Implementación

Complejidad temporal: $\mathcal{O}(N)$

C++Python


#include <iostream>
#include <vector>
 
std::vector<int> res;
std::vector<int> ele;
 
void backtrack() {
 
	if (ele.empty()) {
		for (int x : res) { std::cout << x << " \n"[x == res.back()]; }
		exit(0);
	}
 
	for (int i = ele.size() - 1; i >= 0; --i) {
		int x = ele[i];
 
		if (res.empty() || std::abs(res.back() - x) != 1) {
			ele.erase(ele.begin() + i);
			res.push_back(x);
			backtrack();
			res.pop_back();
			ele.insert(ele.begin() + i, x);
		}
	}
}
 
int main() {
	int n;
	std::cin >> n;
 
	if (n == 2 || n == 3) {
		std::cout << "NO SOLUTION" << '\n';
		return 0;
	}
 
	for (int i = n; i >= 1; i--) { ele.push_back(i); }
 
	backtrack();
}


import sys
 
sys.setrecursionlimit(10**7)
 
res = []
ele = []
 
 
def backtrack():
 
	if not ele:  # comprueba si la lista está vacía
		for i in res:
			print(i)
		exit(0)
 
	for i in range(len(ele) - 1, -1, -1):
		x = ele[i]
 
		if not res or abs(res[-1] - x) != 1:
			del ele[i]
			res.append(x)
			backtrack()
			res.pop()
			ele.insert(i, x)
 
 
n = int(input())
 
if n == 2 or n == 3:
	print("NO SOLUTION")
	exit(0)
 
for i in range(n, 0, -1):
	ele.append(i)
 
backtrack()