Combinaciones donde cada elemento aparece dos veces y la distancia entre las apariencias es igual al valor

Dado un número positivo n, necesitamos encontrar todas las combinaciones de 2*n elementos tales que cada elemento del 1 al n aparezca exactamente dos veces y la distancia entre sus apariciones sea exactamente igual al valor del elemento. 

Ejemplos: 

Input :  n = 3
Output : 3 1 2 1 3 2
         2 3 1 2 1 3
All elements from 1 to 3 appear
twice and distance between two
appearances is equal to value
of the element.

Input :  n = 4
Output : 4 1 3 1 2 4 3 2
         2 3 4 2 1 3 1 4
 

Explicación
Podemos usar el retroceso para resolver este problema. La idea es buscar todas las combinaciones posibles para el primer elemento y explorar recursivamente el elemento restante para verificar si conducirán a la solución o no. Si la configuración actual no da como resultado una solución, damos marcha atrás. Tenga en cuenta que un elemento k se puede colocar en la posición i y (i+k+1) en la array de salida i >= 0 y (i+k+1) < 2*n. 

Tenga en cuenta que no es posible ninguna combinación de elementos para algún valor de n como 2, 5, 6, etc. 

C++

// C++ program to find all combinations where every
// element appears twice and distance between
// appearances is equal to the value
#include <bits/stdc++.h>
using namespace std;
 
// Find all combinations that satisfies given constraints
void allCombinationsRec(vector<int> &arr, int elem, int n)
{
    // if all elements are filled, print the solution
    if (elem > n)
    {
        for (int i : arr)
            cout << i << " ";
        cout << endl;
 
        return;
    }
 
    // try all possible combinations for element elem
    for (int i = 0; i < 2*n; i++)
    {
        // if position i and (i+elem+1) are not occupied
        // in the vector
        if (arr[i] == -1 && (i + elem + 1) < 2*n &&
                arr[i + elem + 1] == -1)
        {
            // place elem at position i and (i+elem+1)
            arr[i] = elem;
            arr[i + elem + 1] = elem;
 
            // recurse for next element
            allCombinationsRec(arr, elem + 1, n);
 
            // backtrack (remove elem from position i and (i+elem+1) )
            arr[i] = -1;
            arr[i + elem + 1] = -1;
        }
    }
}
 
void allCombinations(int n)
{
    // create a vector of double the size of given number with
    vector<int> arr(2*n, -1);
 
    // all its elements initialized by 1
    int elem = 1;
 
    // start from element 1
    allCombinationsRec(arr, elem, n);
}
 
// Driver code
int main()
{
    // given number
    int n = 3;
    allCombinations(n);
    return 0;
}

Java

// Java program to find all combinations where every
// element appears twice and distance between
// appearances is equal to the value
 
import java.util.Vector;
 
class Test
{
    // Find all combinations that satisfies given constraints
    static void allCombinationsRec(Vector<Integer> arr, int elem, int n)
    {
        // if all elements are filled, print the solution
        if (elem > n)
        {
            for (int i : arr)
                System.out.print(i + " ");
            System.out.println();
      
            return;
        }
      
        // try all possible combinations for element elem
        for (int i = 0; i < 2*n; i++)
        {
            // if position i and (i+elem+1) are not occupied
            // in the vector
            if (arr.get(i) == -1 && (i + elem + 1) < 2*n &&
                    arr.get(i + elem + 1) == -1)
            {
                // place elem at position i and (i+elem+1)
                arr.set(i, elem);
                arr.set(i + elem + 1, elem);
      
                // recurse for next element
                allCombinationsRec(arr, elem + 1, n);
      
                // backtrack (remove elem from position i and (i+elem+1) )
                arr.set(i, -1);
                arr.set(i + elem + 1, -1);
            }
        }
    }
      
    static void allCombinations(int n)
    {
         
        // create a vector of double the size of given number with
        Vector<Integer> arr = new Vector<>();
         
        for (int i = 0; i < 2*n; i++) {
            arr.add(-1);
        }
         
        // all its elements initialized by 1
        int elem = 1;
      
        // start from element 1
        allCombinationsRec(arr, elem, n);
    }
     
    // Driver method
    public static void main(String[] args)
    {
        // given number
        int n = 3;
        allCombinations(n);
    }
}

Python3

# Python3 program to find all combinations
# where every element appears twice and distance
# between appearances is equal to the value
 
# Find all combinations that
# satisfies given constraints
def allCombinationsRec(arr, elem, n):
 
    # if all elements are filled,
    # print the solution
    if (elem > n):
     
        for i in (arr):
            print(i, end = " ")
             
        print("")
        return
 
    # Try all possible combinations
    # for element elem
    for i in range(0, 2 * n):
     
        # if position i and (i+elem+1) are 
        # not occupied in the vector
        if (arr[i] == -1 and
           (i + elem + 1) < 2*n and
           arr[i + elem + 1] == -1):
         
            # place elem at position
            # i and (i+elem+1)
            arr[i] = elem
            arr[i + elem + 1] = elem
 
            # recurse for next element
            allCombinationsRec(arr, elem + 1, n)
 
            # backtrack (remove elem from
            # position i and (i+elem+1) )
            arr[i] = -1
            arr[i + elem + 1] = -1
         
def allCombinations(n):
 
    # create a vector of double
    # the size of given number with
    arr = [-1] * (2 * n)
 
    # all its elements initialized by 1
    elem = 1
 
    # start from element 1
    allCombinationsRec(arr, elem, n)
 
# Driver code
n = 3
allCombinations(n)
 
# This code is contributed by Smitha Dinesh Semwal.

C#

// C# program to find all combinations where every
// element appears twice and distance between
// appearances is equal to the value
using System;
using System.Collections.Generic;
 
class Test{
     
// Find all combinations that satisfies given
// constraints
static void allCombinationsRec(List<int> arr, int elem,
                               int n)
{
     
    // If all elements are filled, print the solution
    if (elem > n)
    {
        foreach(int i in arr)
            Console.Write(i + " ");
             
        Console.WriteLine();
 
        return;
    }
 
    // Try all possible combinations for element elem
    for(int i = 0; i < 2 * n; i++)
    {
         
        // If position i and (i+elem+1) are not
        // occupied in the vector
        if (arr[i] == -1 && (i + elem + 1) < 2 * n &&
                         arr[i + elem + 1] == -1)
        {
             
            // Place elem at position i and (i+elem+1)
            arr[i] = elem;
            arr[i + elem + 1] = elem;
 
            // Recurse for next element
            allCombinationsRec(arr, elem + 1, n);
 
            // Backtrack (remove elem from position i
            // and (i+elem+1) )
            arr[i] = -1;
            arr[i + elem + 1] = -1;
        }
    }
}
 
static void allCombinations(int n)
{
 
    // Create a vector of double the size of given
    // number with
    List<int> arr = new List<int>();
 
    for(int i = 0; i < 2 * n; i++)
    {
        arr.Add(-1);
    }
 
    // All its elements initialized by 1
    int elem = 1;
 
    // Start from element 1
    allCombinationsRec(arr, elem, n);
}
 
// Driver Code
public static void Main(string[] args)
{
     
    // Given number
    int n = 3;
     
    allCombinations(n);
}
}
 
// This code is contributed by ukasp

Javascript

<script>
 
// Javascript program to find all combinations where every
// element appears twice and distance between
// appearances is equal to the value
 
// Find all combinations that satisfies given constraints
function allCombinationsRec(arr, elem, n)
{
 
    // if all elements are filled, print the solution
    if (elem > n) {
        for (i of arr)
            document.write(i + " ");
        document.write("<br>");
 
        return;
    }
 
    // try all possible combinations for element elem
    for (let i = 0; i < 2 * n; i++)
    {
     
        // if position i and (i+elem+1) are not occupied
        // in the vector
        if (arr[i] == -1 && (i + elem + 1) < 2 * n &&
            arr[i + elem + 1] == -1)
            {
             
            // place elem at position i and (i+elem+1)
            arr[i] = elem;
            arr[i + elem + 1] = elem;
 
            // recurse for next element
            allCombinationsRec(arr, elem + 1, n);
 
            // backtrack (remove elem from position i and (i+elem+1) )
            arr[i] = -1;
            arr[i + elem + 1] = -1;
        }
    }
}
 
function allCombinations(n)
{
 
    // create a vector of double the size of given number with
    let arr = new Array(2 * n).fill(-1);
 
    // all its elements initialized by 1
    let elem = 1;
 
    // start from element 1
    allCombinationsRec(arr, elem, n);
}
 
// Driver code
// given number
let n = 3;
allCombinations(n);
 
// This code is contributed by gfgking.
</script>

Producción: 

 3 1 2 1 3 2 
 2 3 1 2 1 3 

Este artículo es una contribución de Rakesh Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuir@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *