Encuentre una array con k número de llamadas de clasificación de combinación

Dados dos números n y k, encuentre una array que contenga valores en [1, n] y requiera exactamente k llamadas de la función de clasificación de combinación recursiva .

Ejemplos: 

Input : n = 3
        k = 3
Output : a[] = {2, 1, 3}
Explanation:
Here, a[] = {2, 1, 3}
First of all, mergesort(0, 3) will be called,
which then sets mid = 1 and calls mergesort(0, 
1) and mergesort(1, 3), which do not perform
any recursive calls because segments (0, 1) 
and (1, 3) are sorted.
Hence, total mergesort calls are 3.
 
Input : n = 4
        k = 1
Output : a[] = {1, 2, 3, 4}
Explanation:
Here, a[] = {1, 2, 3, 4} then there will be
1 mergesort call — mergesort(0, 4), which 
will check that the array is sorted and then
end.

Si tenemos un valor de k par, entonces no hay solución ya que el número de llamadas siempre es impar (una llamada al principio y cada llamada hace 0 o 2 llamadas recursivas).
Si k es impar, intentemos comenzar con una permutación ordenada y tratemos de «desordenarla». Hagamos una función unsort(l, r) que lo haga. Cuando «desordenamos» un segmento, podemos mantenerlo ordenado (si ya hicimos suficientes llamadas), o dejarlo sin ordenar y luego llamar a unsort(l, mid) y unsort(mid, r), si necesitamos más llamadas Cuando hacemos un segmento sin ordenar, es mejor mantener ambas mitades ordenadas; una manera fácil de manejar esto es intercambiar dos elementos intermedios.
Es fácil ver que la cantidad de llamadas de ordenación es igual a la cantidad de llamadas de ordenación combinada para ordenar la permutación resultante, por lo que podemos usar este enfoque para tratar de obtener exactamente k llamadas.

A continuación se muestra el código para el problema anterior. 

// C++ program to find an array that can be
// sorted with k merge sort calls.
#include <iostream>
using namespace std;
 
void unsort(int l, int r, int a[], int& k)
{
    if (k < 1 || l + 1 == r)
        return;
 
    // We make two recursive calls, so
    // reduce k by 2.
    k -= 2;
 
    int mid = (l + r) / 2;
    swap(a[mid - 1], a[mid]);
    unsort(l, mid, a, k);
    unsort(mid, r, a, k);
}
 
void arrayWithKCalls(int n, int k)
{
    if (k % 2 == 0) {
        cout << " NO SOLUTION ";
        return;
    }
 
    // Create an array with values
    // in [1, n]
    int a[n+1];
    a[0] = 1;
    for (int i = 1; i < n; i++)
        a[i] = i + 1;
    k--;
 
    // calling unsort function
    unsort(0, n, a, k);
 
    for (int i = 0; i < n; ++i)
        cout << a[i] << ' ';
}
 
// Driver code
int main()
{
    int n = 10, k = 17;
    arrayWithKCalls(n, k);
    return 0;
}

// Java program to find an array that can be
// sorted with k merge sort calls.
class GFG {
     
    static void unsort(int l, int r, int a[], int k)
    {
         
        if (k < 1 || l + 1 == r)
            return;
 
        // We make two recursive calls, so
        // reduce k by 2.
        k -= 2;
 
        int mid = (l + r) / 2;
        int temp = a[mid - 1];
        a[mid - 1] = a[mid];
        a[mid] = temp;
         
        unsort(l, mid, a, k);
        unsort(mid, r, a, k);
    }
 
    static void arrayWithKCalls(int n, int k)
    {
        if (k % 2 == 0) {
            System.out.print("NO SOLUTION");
            return;
        }
 
        // Create an array with values
        // in [1, n]
        int a[] = new int[n + 1];
        a[0] = 1;
         
        for (int i = 1; i < n; i++)
            a[i] = i + 1;
        k--;
 
        // calling unsort function
        unsort(0, n, a, k);
 
        for (int i = 0; i < n; ++i)
            System.out.print(a[i] + " ");
    }
     
    // Driver code
    public static void main(String[] args)
    {
         
        int n = 10, k = 17;
         
        arrayWithKCalls(n, k);
    }
}
 
// This code is contributed by Anant Agarwal.

# Python program to find
# an array that can be
# sorted with k merge
# sort calls.
 
def unsort(l,r,a,k):
 
    if (k < 1 or l + 1 == r):
        return
  
    # We make two recursive calls, so
    # reduce k by 2.
    k -= 2
  
    mid = (l + r) // 2
    temp = a[mid - 1]
    a[mid-1] = a[mid]
    a[mid] = temp
 
    unsort(l, mid, a, k)
    unsort(mid, r, a, k)
 
def arrayWithKCalls(n,k):
 
    if (k % 2 == 0):
        print("NO SOLUTION")
        return
     
  
    # Create an array with values
    # in [1, n]
    a = [0 for i in range(n + 2)]
    a[0] = 1
    for i in range(1, n):
        a[i] = i + 1
    k-=1
  
    # calling unsort function
    unsort(0, n, a, k)
  
    for i in range(n):
        print(a[i] ," ",end="")
 
# Driver code
 
n = 10
k = 17
arrayWithKCalls(n, k)
 
# This code is contributed
# by Anant Agarwal.

// C# program to find an array that can
// be sorted with k merge sort calls.
using System;
 
class GFG {
     
    static void unsort(int l, int r,
                       int []a, int k)
    {
        if (k < 1 || l + 1 == r)
            return;
 
        // We make two recursive calls,
        // so reduce k by 2.
        k -= 2;
 
        int mid = (l + r) / 2;
        int temp = a[mid - 1];
        a[mid - 1] = a[mid];
        a[mid] = temp;
         
        unsort(l, mid, a, k);
        unsort(mid, r, a, k);
    }
 
    static void arrayWithKCalls(int n, int k)
    {
        if (k % 2 == 0)
        {
            Console.WriteLine("NO SOLUTION");
            return;
        }
 
        // Create an array with
        // values in [1, n]
        int []a = new int[n + 1];
        a[0] = 1;
         
        for (int i = 1; i < n; i++)
            a[i] = i + 1;
        k--;
 
        // calling unsort function
        unsort(0, n, a, k);
 
        for (int i = 0; i < n; ++i)
            Console.Write(a[i] + " ");
    }
     
    // Driver code
    public static void Main()
    {
         
        int n = 10, k = 17;
         
        arrayWithKCalls(n, k);
    }
}
 
// This code is contributed by vt_m.

<script>
 
// JavaScript program to find an array that can be
// sorted with k merge sort calls.
 
var k;
 
function unsort(l, r, a)
{
    if (k < 1 || l + 1 == r)
        return;
 
    // We make two recursive calls, so
    // reduce k by 2.
    k -= 2;
 
    var mid = parseInt((l + r) / 2);
    [a[mid - 1], a[mid]] = [a[mid], a[mid - 1]];
    unsort(l, mid, a);
    unsort(mid, r, a);
}
 
function arrayWithKCalls(n)
{
    if (k % 2 == 0) {
        document.write( " NO SOLUTION ");
        return;
    }
 
    // Create an array with values
    // in [1, n]
    var a = Array(n+1);
    a[0] = 1;
    for (var i = 1; i < n; i++)
        a[i] = i + 1;
    k--;
 
    // calling unsort function
    unsort(0, n, a);
 
    for (var i = 0; i < n; ++i)
        document.write( a[i] + ' ');
}
 
// Driver code
var n = 10
k = 17;
arrayWithKCalls(n);
 
</script>

3 1 4 6 2 8 5 9 7 10