Recuento de subconjuntos que no contienen elementos adyacentes

Dada una array arr[] de N enteros, la tarea es encontrar el recuento de todos los subconjuntos que no contienen elementos adyacentes de la array dada.

Ejemplos:  

Entrada: arr[] = {2, 7} 
Salida: 3 
Todos los subconjuntos posibles son {}, {2} y {7}.

Entrada: arr[] = {3, 5, 7} 
Salida: 5  

Método 1: la idea es usar un patrón de máscara de bits para generar todas las combinaciones como se explica en este artículo. Al considerar un subconjunto, debemos verificar si contiene elementos adyacentes o no. Un subconjunto contendrá elementos adyacentes si se establecen dos o más bits consecutivos en su máscara de bits. Para verificar si la máscara de bits tiene configurados bits consecutivos o no, podemos desplazar la máscara un bit a la derecha y tomarla como AND con la máscara. Si el resultado de la operación AND es 0, entonces la máscara no tiene conjuntos consecutivos y, por lo tanto, el subconjunto correspondiente no tendrá elementos adyacentes de la array.
A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <iostream>
#include <math.h>
using namespace std;
 
// Function to return the count
// of possible subsets
int cntSubsets(int* arr, int n)
{
 
    // Total possible subsets of n
    // sized array is (2^n - 1)
    unsigned int max = pow(2, n);
 
    // To store the required
    // count of subsets
    int result = 0;
 
    // Run from i 000..0 to 111..1
    for (int i = 0; i < max; i++) {
        int counter = i;
 
        // If current subset has consecutive
        // elements from the array
        if (counter & (counter >> 1))
            continue;
        result++;
    }
    return result;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 5, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << cntSubsets(arr, n);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
     
class GFG
{
 
// Function to return the count
// of possible subsets
static int cntSubsets(int[] arr, int n)
{
 
    // Total possible subsets of n
    // sized array is (2^n - 1)
    int max = (int) Math.pow(2, n);
 
    // To store the required
    // count of subsets
    int result = 0;
 
    // Run from i 000..0 to 111..1
    for (int i = 0; i < max; i++)
    {
        int counter = i;
 
        // If current subset has consecutive
        if ((counter & (counter >> 1)) > 0)
            continue;
        result++;
    }
    return result;
}
 
// Driver code
static public void main (String []arg)
{
    int arr[] = { 3, 5, 7 };
    int n = arr.length;
 
    System.out.println(cntSubsets(arr, n));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 implementation of the approach
 
# Function to return the count
# of possible subsets
def cntSubsets(arr, n):
 
    # Total possible subsets of n
    # sized array is (2^n - 1)
    max = pow(2, n)
 
    # To store the required
    # count of subsets
    result = 0
 
    # Run from i 000..0 to 111..1
    for i in range(max):
        counter = i
 
        # If current subset has consecutive
        # elements from the array
        if (counter & (counter >> 1)):
            continue
        result += 1
 
    return result
 
# Driver code
arr = [3, 5, 7]
n = len(arr)
 
print(cntSubsets(arr, n))
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to return the count
// of possible subsets
static int cntSubsets(int[] arr, int n)
{
 
    // Total possible subsets of n
    // sized array is (2^n - 1)
    int max = (int) Math.Pow(2, n);
 
    // To store the required
    // count of subsets
    int result = 0;
 
    // Run from i 000..0 to 111..1
    for (int i = 0; i < max; i++)
    {
        int counter = i;
 
        // If current subset has consecutive
        if ((counter & (counter >> 1)) > 0)
            continue;
        result++;
    }
    return result;
}
 
// Driver code
static public void Main (String []arg)
{
    int []arr = { 3, 5, 7 };
    int n = arr.Length;
 
    Console.WriteLine(cntSubsets(arr, n));
}
}
     
// This code is contributed by Rajput-Ji

<script>
 
// Javascript implementation of the approach
 
// Function to return the count
// of possible subsets
function cntSubsets(arr, n)
{
 
    // Total possible subsets of n
    // sized array is (2^n - 1)
    var max = Math.pow(2, n);
 
    // To store the required
    // count of subsets
    var result = 0;
 
    // Run from i 000..0 to 111..1
    for (var i = 0; i < max; i++) {
        var counter = i;
 
        // If current subset has consecutive
        // elements from the array
        if (counter & (counter >> 1))
            continue;
        result++;
    }
    return result;
}
 
// Driver code
var arr = [3, 5, 7];
var n = arr.length;
document.write( cntSubsets(arr, n));
 
 
</script>

5

Método 2: El enfoque anterior requiere un tiempo exponencial. En el código anterior, se requería el número de máscaras de bits sin 1 consecutivos. Este conteo se puede obtener en tiempo lineal usando programación dinámica como se explica en este artículo.
A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <iostream>
using namespace std;
 
// Function to return the count
// of possible subsets
int cntSubsets(int* arr, int n)
{
    int a[n], b[n];
 
    a[0] = b[0] = 1;
 
    for (int i = 1; i < n; i++) {
 
        // If previous element was 0 then 0
        // as well as 1 can be appended
        a[i] = a[i - 1] + b[i - 1];
 
        // If previous element was 1 then
        // only 0 can be appended
        b[i] = a[i - 1];
    }
 
    // Store the count of all possible subsets
    int result = a[n - 1] + b[n - 1];
 
    return result;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 5, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << cntSubsets(arr, n);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to return the count
// of possible subsets
static int cntSubsets(int []arr, int n)
{
    int []a = new int[n];
    int []b = new int[n];
 
    a[0] = b[0] = 1;
 
    for (int i = 1; i < n; i++)
    {
 
        // If previous element was 0 then 0
        // as well as 1 can be appended
        a[i] = a[i - 1] + b[i - 1];
 
        // If previous element was 1 then
        // only 0 can be appended
        b[i] = a[i - 1];
    }
 
    // Store the count of all possible subsets
    int result = a[n - 1] + b[n - 1];
 
    return result;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 3, 5, 7 };
    int n = arr.length;
 
    System.out.println(cntSubsets(arr, n));
}
}
 
// This code is contributed by Princi Singh

# Python3 implementation of the approach
 
# Function to return the count
# of possible subsets
def cntSubsets(arr, n) :
 
    a = [0] * n
    b = [0] * n;
 
    a[0] = b[0] = 1;
 
    for i in range(1, n) :
         
        # If previous element was 0 then 0
        # as well as 1 can be appended
        a[i] = a[i - 1] + b[i - 1];
 
        # If previous element was 1 then
        # only 0 can be appended
        b[i] = a[i - 1];
 
    # Store the count of all possible subsets
    result = a[n - 1] + b[n - 1];
 
    return result;
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 3, 5, 7 ];
    n = len(arr);
 
    print(cntSubsets(arr, n));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
     
class GFG
{
 
// Function to return the count
// of possible subsets
static int cntSubsets(int []arr, int n)
{
    int []a = new int[n];
    int []b = new int[n];
 
    a[0] = b[0] = 1;
 
    for (int i = 1; i < n; i++)
    {
 
        // If previous element was 0 then 0
        // as well as 1 can be appended
        a[i] = a[i - 1] + b[i - 1];
 
        // If previous element was 1 then
        // only 0 can be appended
        b[i] = a[i - 1];
    }
 
    // Store the count of all possible subsets
    int result = a[n - 1] + b[n - 1];
 
    return result;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 3, 5, 7 };
    int n = arr.Length;
 
    Console.WriteLine(cntSubsets(arr, n));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of the approach
 
// Function to return the count
// of possible subsets
function cntSubsets(arr, n)
{
    var a = Array(n);
    var b = Array(n);
 
    a[0] = b[0] = 1;
 
    for (var i = 1; i < n; i++) {
 
        // If previous element was 0 then 0
        // as well as 1 can be appended
        a[i] = a[i - 1] + b[i - 1];
 
        // If previous element was 1 then
        // only 0 can be appended
        b[i] = a[i - 1];
    }
 
    // Store the count of all possible subsets
    var result = a[n - 1] + b[n - 1];
 
    return result;
}
 
// Driver code
var arr = [3, 5, 7 ];
var n = arr.length;
document.write( cntSubsets(arr, n));
 
</script>

5

método 3; Si observamos más de cerca el patrón, podemos observar que la cuenta es en realidad (N + 2) el ^número de Fibonacci para N ≥ 1 .  

n = 1, conteo = 2 = fib(3) 
n = 2, conteo = 3 = fib(4) 
n = 3, conteo = 5 = fib(5) 
n = 4, conteo = 8 = fib(6) 
n = 5, cuenta = 13 = fib(7) 
……………. 

Por lo tanto, los subconjuntos se pueden contar en tiempo O (log n) usando el método 5 de este artículo.