Genere una permutación de 1 a N tal que la diferencia absoluta de números consecutivos dé a K enteros distintos

Dados dos enteros N y K donde K < N , la tarea es generar una permutación de enteros de 1 a N tal que la diferencia absoluta de todos los enteros consecutivos dé exactamente K enteros distintos.

Ejemplos:  

Entrada: N = 3, K = 2 
Salida: 1 3 2 
|1 – 3| = 2 y |3 – 2| = 1 que da 2 enteros distintos (2 y 1)

Entrada: N = 5, K = 4 
Salida: 1 5 2 4 3 
|1 – 5| = 4, |5 – 2| = 3, |2 – 4| = 2 y |4 – 3| = 1 da 4 enteros distintos, es decir, 4, 3, 2 y 1 
 

Enfoque: El problema se puede resolver fácilmente mediante la simple observación. En los índices impares coloque la secuencia creciente 1, 2, 3,… y en los índices pares coloque la secuencia decreciente N, N-1, N-2,… y así sucesivamente.
Para N = 10 , una permutación con enteros distintos para diferencia absoluta consecutiva puede ser 1 10 2 9 3 8 4 7 5 6 . La diferencia absoluta consecutiva da los números enteros 9, 8, 7 y así sucesivamente . 
Entonces, primero imprima K enteros de tal secuencia y luego haga que el resto de las diferencias sean iguales a 1 . El código es bastante autoexplicativo.

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to generate a permutation of integers
// from 1 to N such that the absolute difference of
// all the two consecutive integers give K distinct integers
void printPermutation(int N, int K)
{
    // To store the permutation
    vector<int> res;
 
    int l = 1, r = N, flag = 0;
 
    for (int i = 0; i < K; i++) {
 
        if (!flag) {
 
            // For sequence 1 2 3...
            res.push_back(l);
            l++;
        }
        else {
 
            // For sequence N, N-1, N-2...
            res.push_back(r);
            r--;
        }
 
        // Flag is used to alternate between
        // the above if else statements
        flag ^= 1;
    }
 
    // Taking integers with difference 1
 
    // If last element added was r + 1
    if (!flag) {
        for (int i = r; i >= l; i--)
            res.push_back(i);
    }
 
    // If last element added was l - 1
    else {
        for (int i = l; i <= r; i++)
            res.push_back(i);
    }
 
    // Print the permutation
    for (auto i : res)
        cout << i << " ";
}
 
// Driver code
int main()
{
    int N = 10, K = 4;
 
    printPermutation(N, K);
 
    return 0;
}

// Java implementation of the above approach
import java.util.Vector;
 
class GFG
{
    // Function to generate a permutation
    // of integers from 1 to N such that the
    // absolute difference of all the two
    // consecutive integers give K distinct integers
    static void printPermutation(int N, int K)
    {
        // To store the permutation
        Vector<Integer> res = new Vector<>();
 
        int l = 1, r = N, flag = 0;
 
        for (int i = 0; i < K; i++)
        {
            if (flag == 0)
            {
                // For sequence 1 2 3...
                res.add(l);
                l++;
            }
            else
            {
                // For sequence N, N-1, N-2...
                res.add(r);
                r--;
            }
 
            // Flag is used to alternate between
            // the above if else statements
            flag ^= 1;
        }
 
        // Taking integers with difference 1
        // If last element added was r + 1
        if (flag != 1)
        {
            for (int i = r; i >= l; i--)
            {
                res.add(i);
            }
        }
        // If last element added was l - 1
        else
        {
            for (int i = l; i <= r; i++)
            {
                res.add(i);
            }
        }
 
        // Print the permutation
        for (Integer i : res)
        {
            System.out.print(i + " ");
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 10, K = 4;
        printPermutation(N, K);
         
    }
}
 
// This code is contributed by
// 29AjayKumar

# Python 3 implementation of the approach
 
# Function to generate a permutation
# of integers from 1 to N such that the
# absolute difference of all the two
# consecutive integers give K distinct
# integers
def printPermutation(N, K):
 
    # To store the permutation
    res = list();
 
    l, r, flag = 1, N, 0
 
    for i in range(K):
 
        if flag == False:
             
            # For sequence 1 2 3...
            res.append(l)
            l += 1
     
        else:
             
            # For sequence N, N-1, N-2...
            res.append(r);
            r -= 1;
 
    # Flag is used to alternate between
    # the above if else statements
        flag = flag ^ 1;
 
    # Taking integers with difference 1
 
    # If last element added was r + 1
    if flag == False:
        for i in range(r, 2, -1):
            res.append(i)
 
    # If last element added was l - 1
    else:
        for i in range(l, r):
            res.append(i)
 
    # Print the permutation
    for i in res:
        print(i, end = " ")
 
# Driver code
N, K = 10, 4
printPermutation(N, K)
 
# This code is contributed by
# Mohit Kumar 29

// C# implementation of the above approach
using System;
using System.Collections;
 
class GFG
{
    // Function to generate a permutation
    // of integers from 1 to N such that the
    // absolute difference of all the two
    // consecutive integers give K distinct integers
    static void printPermutation(int N, int K)
    {
         
        // To store the permutation
        ArrayList res = new ArrayList();
 
        int l = 1, r = N, flag = 0;
        for (int i = 0; i < K; i++)
        {
            if (flag == 0)
            {
                // For sequence 1 2 3...
                res.Add(l);
                l++;
            }
            else
            {
                // For sequence N, N-1, N-2...
                res.Add(r);
                r--;
            }
 
            // Flag is used to alternate between
            // the above if else statements
            flag ^= 1;
        }
 
        // Taking integers with difference 1
        // If last element added was r + 1
        if (flag != 1)
        {
            for (int i = r; i >= l; i--)
            {
                res.Add(i);
            }
        }
         
        // If last element added was l - 1
        else
        {
            for (int i = l; i <= r; i++)
            {
                res.Add(i);
            }
        }
 
        // Print the permutation
        foreach (int i in res)
        {
            Console.Write(i + " ");
        }
    }
 
    // Driver code
    public static void Main()
    {
        int N = 10, K = 4;
        printPermutation(N, K);       
    }
}
 
// This code is contributed by PrinciRaj1992

<?php
// PHP implementation of the approach
 
// Function to generate a permutation
// of integers from 1 to N such that the
// absolute difference of all the two
// consecutive integers give K distinct
// integers
function printPermutation($N, $K)
{
     
    // To store the permutation
    $res = array();
 
    $l = 1;
    $r = $N;
    $flag = 0;
 
    for ($i = 0; $i < $K; $i++)
    {
        if (!$flag)
        {
 
            // For sequence 1 2 3...
            array_push($res, $l);
            $l++;
        }
        else
        {
 
            // For sequence N, N-1, N-2...
            array_push($res, $r);
            $r--;
        }
 
        // Flag is used to alternate between
        // the above if else statements
        $flag ^= 1;
    }
 
    // Taking integers with difference 1
 
    // If last element added was r + 1
    if (!$flag)
    {
        for ($i = $r; $i >= $l; $i--)
            array_push($res, $i);
    }
 
    // If last element added was l - 1
    else
    {
        for ($i = l; $i <= $r; $i++)
            array_push($res, $i);
    }
 
    // Print the permutation
    for($i = 0; $i < sizeof($res); $i++)
        echo $res[$i], " ";
}
 
// Driver code
$N = 10;
$K = 4;
 
printPermutation($N, $K);
 
// This code is contributed by Ryuga
?>

<script>
 
// Javascript implementation of the approach
 
// Function to generate a permutation of
// integers from 1 to N such that the
// absolute difference of all the two
// consecutive integers give K distinct integers
function printPermutation(N, K)
{
     
    // To store the permutation
    var res = [];
    var l = 1, r = N, flag = 0;
 
    for(var i = 0; i < K; i++)
    {
        if (!flag)
        {
             
            // For sequence 1 2 3...
            res.push(l);
            l++;
        }
        else
        {
             
            // For sequence N, N-1, N-2...
            res.push(r);
            r--;
        }
 
        // Flag is used to alternate between
        // the above if else statements
        flag ^= 1;
    }
 
    // Taking integers with difference 1
 
    // If last element added was r + 1
    if (!flag)
    {
        for(var i = r; i >= l; i--)
            res.push(i);
    }
 
    // If last element added was l - 1
    else
    {
        for(var i = l; i <= r; i++)
            res.push(i);
    }
 
    // Print the permutation
    for(var i = 0; i< res.length; i++)
    {
        document.write(res[i] + " ");
    }
}
 
// Driver code
var N = 10, K = 4;
 
printPermutation(N, K);
 
// This code is contributed by noob2000
 
</script>

1 10 2 9 8 7 6 5 4 3

Complejidad de tiempo : O(K+N)

Complejidad espacial : O(N)