Genere una permutación de los primeros N números naturales que tengan un recuento de diferencias adyacentes únicas igual a K | conjunto 2

Dados dos enteros positivos N y K , la tarea es construir una permutación de los primeros N números naturales tal que todas las posibles diferencias absolutas entre elementos adyacentes sean K .

Ejemplos:

Entrada: N = 3, K = 1
Salida: 1 2 3
Explicación: Considerando la permutación {1, 2, 3}, todas las posibles diferencias absolutas únicas de elementos adyacentes son {1}. Dado que la cuenta es 1(= K), imprima la secuencia {1, 2, 3} como la permutación resultante.

Entrada: N = 3, K = 2
Salida: 1 3 2

El enfoque ingenuo y el enfoque de dos puntos de este problema ya se discuten aquí . Este artículo analiza un enfoque diferente deque .

Enfoque: es fácil ver que se pueden generar respuestas para todos los valores de K entre [1, N-1] . Para cualquier K fuera de este rango, no existe respuesta. Para resolver el problema, mantenga una cola de dos extremos para todos los elementos actuales y un vector para almacenar la secuencia. Además, mantenga un valor booleano que le ayudará a determinar si aparece el elemento frontal o posterior. Iterar el elemento restante y si K es mayor que 1 , empujar el elemento de acuerdo con el valor booleano y disminuir K en 1 . Voltee el valor booleano para que todas las diferencias restantes tengan el valor 1. Siga los pasos a continuación para resolver el problema:

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

C++

// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the required array
void K_ValuesArray(int N, int K)
{
 
    // Check for base cases
    if (K < 1 || K >= N) {
        cout << -1;
        return;
    }
 
    // Maintain a deque to store the
    // elements from [1, N];
    deque<int> dq;
    for (int i = 2; i <= N; i++) {
        dq.push_back(i);
    }
 
    // Maintain a boolean value which will
    // tell from where to pop the element
    bool front = true;
 
    // Create a vector to store the answer
    vector<int> ans;
 
    // Push 1 in the answer initially
    ans.push_back(1);
 
    // Push the remaining elements
    if (K > 1) {
        front ^= 1;
        K--;
    }
 
    // Iterate over the range
    for (int i = 2; i <= N; i++) {
        if (front) {
            int val = dq.front();
            dq.pop_front();
 
            // Push this value in
            // the ans vector
            ans.push_back(val);
            if (K > 1) {
                K--;
 
                // Flip the boolean
                // value
                front ^= 1;
            }
        }
        else {
            int val = dq.back();
            dq.pop_back();
 
            // Push value in ans vector
            ans.push_back(val);
            if (K > 1) {
                K--;
 
                // Flip boolean value
                front ^= 1;
            }
        }
    }
 
    // Print Answer
    for (int i = 0; i < N; i++) {
        cout << ans[i] << " ";
    }
}
 
// Driver Code
int main()
{
    int N = 7, K = 1;
    K_ValuesArray(N, K);
 
    return 0;
}

Java

// Java Program for the above approach
import java.util.*;
class GFG{
 
// Function to calculate the required array
static void K_ValuesArray(int N, int K)
{
 
    // Check for base cases
    if (K < 1 || K >= N) {
        System.out.print(-1);
        return;
    }
 
    // Maintain a deque to store the
    // elements from [1, N];
    Deque<Integer> dq = new LinkedList<Integer>();
    for (int i = 2; i <= N; i++) {
        dq.add(i);
    }
 
    // Maintain a boolean value which will
    // tell from where to pop the element
    boolean front = true;
 
    // Create a vector to store the answer
    Vector<Integer> ans = new Vector<Integer>();
 
    // Push 1 in the answer initially
    ans.add(1);
 
    // Push the remaining elements
    if (K > 1) {
        front ^=true;
        K--;
    }
 
    // Iterate over the range
    for (int i = 2; i <= N; i++) {
        if (front) {
            int val = dq.peek();
            dq.removeFirst();
 
            // Push this value in
            // the ans vector
            ans.add(val);
            if (K > 1) {
                K--;
 
                // Flip the boolean
                // value
                front ^=true;
            }
        }
        else {
            int val = dq.getLast();
            dq.removeLast();
 
            // Push value in ans vector
            ans.add(val);
            if (K > 1) {
                K--;
 
                // Flip boolean value
                front ^=true;
            }
        }
    }
 
    // Print Answer
    for (int i = 0; i < N; i++) {
        System.out.print(ans.get(i)+ " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 7, K = 1;
    K_ValuesArray(N, K);
 
}
}
 
// This code is contributed by 29AjayKumar

Python3

# python Program for the above approach
from collections import deque
 
# Function to calculate the required array
def K_ValuesArray(N, K):
 
    # Check for base cases
    if (K < 1 or K >= N):
        print("-1")
        return
 
    # Maintain a deque to store the
    # elements from [1, N];
    dq = deque()
    for i in range(2, N + 1):
        dq.append(i)
 
    # Maintain a boolean value which will
    # tell from where to pop the element
    front = True
 
    # Create a vector to store the answer
    ans = []
 
    # Push 1 in the answer initially
    ans.append(1)
 
    # Push the remaining elements
    if (K > 1):
        front ^= 1
        K -= 1
 
    # Iterate over the range
    for i in range(2, N+1):
        if (front):
            val = dq.popleft()
 
            # Push this value in
            # the ans vector
            ans.append(val)
            if (K > 1):
                K -= 1
 
                # Flip the boolean
                # value
                front ^= 1
 
        else:
            val = dq.pop()
 
            # Push value in ans vector
            ans.append(val)
            if (K > 1):
                K -= 1
 
                # Flip boolean value
                front ^= 1
 
    # Print Answer
    for i in range(0, N):
        print(ans[i], end=" ")
 
# Driver Code
if __name__ == "__main__":
 
    N = 7
    K = 1
    K_ValuesArray(N, K)
 
    # This code is contributed by rakeshsahni

C#

// C# Program for the above approach
 
using System;
using System.Collections.Generic;
class GFG
{
 
    // Function to calculate the required array
    static void K_ValuesArray(int N, int K)
    {
 
        // Check for base cases
        if (K < 1 || K >= N)
        {
            Console.Write(-1);
            return;
        }
 
        // Maintain a deque to store the
        // elements from [1, N];
        LinkedList<int> dq = new LinkedList<int>();
        for (int i = 2; i <= N; i++)
        {
            dq.AddLast(i);
        }
 
        // Maintain a boolean value which will
        // tell from where to pop the element
        bool front = true;
 
        // Create a vector to store the answer
        List<int> ans = new List<int>();
 
        // Push 1 in the answer initially
        ans.Add(1);
 
        // Push the remaining elements
        if (K > 1)
        {
            front ^= true;
            K--;
        }
 
        // Iterate over the range
        for (int i = 2; i <= N; i++)
        {
            if (front)
            {
                int val = dq.First.Value;
                dq.RemoveFirst();
 
                // Push this value in
                // the ans vector
                ans.Add(val);
                if (K > 1)
                {
                    K--;
 
                    // Flip the boolean
                    // value
                    front ^= true;
                }
            }
            else
            {
                int val = dq.Last.Value;
                dq.RemoveLast();
 
                // Push value in ans vector
                ans.Add(val);
                if (K > 1)
                {
                    K--;
 
                    // Flip boolean value
                    front ^= true;
                }
            }
        }
 
        // Print Answer
        for (int i = 0; i < N; i++)
        {
            Console.Write(ans[i] + " ");
        }
    }
 
    // Driver Code
    public static void Main()
    {
        int N = 7, K = 1;
        K_ValuesArray(N, K);
 
    }
}
 
// This code is contributed by Saurabh Jaiswal

Javascript

<script>
// Javascript Program for the above approach
 
// Function to calculate the required array
function K_ValuesArray(N, K) {
 
    // Check for base cases
    if (K < 1 || K >= N) {
        document.write(-1);
        return;
    }
 
    // Maintain a deque to store the
    // elements from [1, N];
    let dq = new Array();
    for (let i = 2; i <= N; i++) {
        dq.push(i);
    }
 
    // Maintain a boolean value which will
    // tell from where to pop the element
    let front = true;
 
    // Create a vector to store the answer
    let ans = new Array();
 
    // Push 1 in the answer initially
    ans.push(1);
 
    // Push the remaining elements
    if (K > 1) {
        front ^= true;
        K--;
    }
 
    // Iterate over the range
    for (let i = 2; i <= N; i++) {
        if (front) {
            let val = dq[0];
            dq.shift();
 
            // Push this value in
            // the ans vector
            ans.push(val);
            if (K > 1) {
                K--;
 
                // Flip the boolean
                // value
                front ^= true;
            }
        }
        else {
            let val = dq.Last.Value;
            dq.pop();
 
            // Push value in ans vector
            ans.push(val);
            if (K > 1) {
                K--;
 
                // Flip boolean value
                front ^= true;
            }
        }
    }
 
    // Print Answer
    for (let i = 0; i < N; i++) {
        document.write(ans[i] + " ");
    }
}
 
// Driver Code
let N = 7, K = 1;
K_ValuesArray(N, K);
 
// This code is contributed by Saurabh Jaiswal
</script>
Producción

1 2 3 4 5 6 7 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *