D'un a ena (3) P69756

Feu un programa que escrigui totes les permutacions de $\{ 1, \dots, n \}$ amb $k$ inversions, per a una $n$ i una $k$ donades. Una inversió és una parella d’elements $x$ i $y$ tals que $x > y$ i tals que $x$ apareix a la permutació abans que $y$.

Entrada

L’entrada consisteix en dos naturals $n$ i $k$, tals que $n \ge 1$ i $0 \le k \le n(n - 1)/2$.

Sortida

Escriviu totes les permutacions de $\{ 1, \dots, n \}$ amb $k$ inversions.

Informació sobre el corrector

Podeu escriure les solucions d’aquest exercici en qualsevol ordre.

Pista

Aquí, un algorisme molt simple pot ser massa lent.