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