Permutacions i cicles (1) P93873


Statement
 

pdf   zip

thehtml

Feu un programa que escrigui totes les permutacions de {1, …, n} amb exactament k cicles, on 1 ≤ kn. Per exemple, considereu la permutació (4, 3, 2, 5, 1, 7, 6). A la posició 1 hi ha un 4, a la posició 4 hi ha un 5, i a la posició 5 hi ha un 1. Així doncs, un dels cicles és 1 → 4 → 5 → 1. Els altres dos cicles són 2 → 3 → 2 i 6 → 7 → 6. La permutació (3,2,1) té els dos cicles 1 → 3 → 1 i 2 → 2, mentre que la permutació (3,4,5,6,7,1,2) només té el cicle 1 → 3 → 5 → 7 → 2 → 4 → 6 → 1.

Entrada

L’entrada consisteix en n i k, amb 1 ≤ kn.

Sortida

Escriviu totes les permutacions de {1, …, n} amb k cicles.

Informació sobre el corrector

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

Pista

Un programa possible no crea les permutacions consecutivament d’esquerra a dreta, sinó saltant pel vector solució, usant una funció

void f(int i, int ini, int caselles, int cicles);

on i és la següent posició a omplir, ini és on comença el cicle actual encara no tancat, caselles és el nombre de caselles encara lliures, i cicles és el nombre de cicles que encara falta crear.

Public test cases
  • Input

    3 1
    

    Output

    (2, 3, 1)
    (3, 1, 2)
    
  • Input

    3 2
    

    Output

    (2, 1, 3)
    (1, 3, 2)
    (3, 2, 1)
    
  • Input

    3 3
    

    Output

    (1, 2, 3)
    
  • Information
    Author
    Enric Rodríguez
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++