From one to en (3) P69756


Statement
 

pdf   zip

thehtml

Write a program that prints all the permutations of { 1, …, n } with k inversions, for a given n and k. An inversion is a pair of elements x and y such that x > y and such that x appears before y in the permutation.

Input

Input consists of two natural numbers n and k, such that n ≥ 1 and 0 ≤ kn(n − 1)/2.

Output

Print all the permutations of { 1, …, n } with k inversions.

Information about the checker

You can print the solutions to this exercise in any order.

Hint

Here, a very simple algorithm may be too slow.

Public test cases
  • Input

    5 2
    

    Output

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

    10 45
    

    Output

    (10,9,8,7,6,5,4,3,2,1)
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python