Suma del promedio de todos los subconjuntos

Dada una array arr de N elementos enteros, la tarea es encontrar la suma del promedio de todos los subconjuntos de esta array.

Ejemplo:  

Input  : arr[] = [2, 3, 5]
Output : 23.33 
Explanation : Subsets with their average are, 
[2]        average = 2/1 = 2
[3]        average = 3/1 = 3
[5]        average = 5/1 = 5
[2, 3]        average = (2+3)/2 = 2.5
[2, 5]        average = (2+5)/2 = 3.5
[3, 5]        average = (3+5)/2 = 4
[2, 3, 5]    average = (2+3+5)/3 = 3.33

Sum of average of all subset is, 
2 + 3 + 5 + 2.5 + 3.5 + 4 + 3.33 = 23.33 

Una solución ingenua es iterar a través de todos los subconjuntos posibles, obtener un promedio de todos ellos y luego agregarlos uno por uno, pero esto llevará un tiempo exponencial y será inviable para arreglos más grandes. 
Podemos obtener un patrón tomando un ejemplo,  

arr = [a0, a1, a2, a3]
sum of average = 
a0/1 + a1/1 + a2/2 + a3/1 +
(a0+a1)/2 + (a0+a2)/2 + (a0+a3)/2 + (a1+a2)/2 +
 (a1+a3)/2 + (a2+a3)/2 + 
(a0+a1+a2)/3 + (a0+a2+a3)/3 + (a0+a1+a3)/3 + 
 (a1+a2+a3)/3 +
(a0+a1+a2+a3)/4

If S = (a0+a1+a2+a3), then above expression 
can be rearranged as below,
sum of average = (S)/1 + (3*S)/2 + (3*S)/3 + (S)/4

El coeficiente con numeradores se puede explicar de la siguiente manera, supongamos que estamos iterando sobre subconjuntos con K elementos, entonces el denominador será K y el numerador será r*S, donde ‘r’ denota la cantidad de veces que se agregará un elemento de array en particular mientras iterando sobre subconjuntos del mismo tamaño. Por inspección, podemos ver que r será nCr(N – 1, n – 1) porque después de colocar un elemento en la suma, necesitamos elegir (n – 1) elementos de (N – 1) elementos, por lo que cada elemento será tienen una frecuencia de nCr(N – 1, n – 1) considerando subconjuntos del mismo tamaño, ya que todos los elementos participan en la suma el mismo número de veces, esta será la frecuencia de S también y será el numerador en el final expresión. 
En el siguiente código, nCr se implementa utilizando el método de programación dinámica, Puedes leer mas al respecto aquí, 
 

// C++ program to get sum of average of all subsets
#include <bits/stdc++.h>
using namespace std;
 
// Returns value of Binomial Coefficient C(n, k)
int nCr(int n, int k)
{
    int C[n + 1][k + 1];
    int i, j;
 
    // Calculate value of Binomial Coefficient in bottom
    // up manner
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= min(i, k); j++) {
            // Base Cases
            if (j == 0 || j == i)
                C[i][j] = 1;
 
            // Calculate value using previously stored
            // values
            else
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
    return C[n][k];
}
 
// method returns sum of average of all subsets
double resultOfAllSubsets(int arr[], int N)
{
    double result = 0.0; // Initialize result
 
    // Find sum of elements
    int sum = 0;
    for (int i = 0; i < N; i++)
        sum += arr[i];
 
    // looping once for all subset of same size
    for (int n = 1; n <= N; n++)
 
        /* each element occurs nCr(N-1, n-1) times while
           considering subset of size n  */
        result += (double)(sum * (nCr(N - 1, n - 1))) / n;
 
    return result;
}
 
// Driver code to test above methods
int main()
{
    int arr[] = { 2, 3, 5, 7 };
    int N = sizeof(arr) / sizeof(int);
    cout << resultOfAllSubsets(arr, N) << endl;
    return 0;
}

// java program to get sum of
// average of all subsets
import java.io.*;
 
class GFG {
 
    // Returns value of Binomial
    // Coefficient C(n, k)
    static int nCr(int n, int k)
    {
        int C[][] = new int[n + 1][k + 1];
        int i, j;
 
        // Calculate value of Binomial
        // Coefficient in bottom up manner
        for (i = 0; i <= n; i++) {
            for (j = 0; j <= Math.min(i, k); j++) {
                // Base Cases
                if (j == 0 || j == i)
                    C[i][j] = 1;
 
                // Calculate value using
                // previously stored values
                else
                    C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
            }
        }
        return C[n][k];
    }
 
    // method returns sum of average of all subsets
    static double resultOfAllSubsets(int arr[], int N)
    {
        // Initialize result
        double result = 0.0;
 
        // Find sum of elements
        int sum = 0;
        for (int i = 0; i < N; i++)
            sum += arr[i];
 
        // looping once for all subset of same size
        for (int n = 1; n <= N; n++)
 
            /* each element occurs nCr(N-1, n-1) times while
            considering subset of size n */
            result += (double)(sum * (nCr(N - 1, n - 1))) / n;
 
        return result;
    }
 
    // Driver code to test above methods
    public static void main(String[] args)
    {
        int arr[] = { 2, 3, 5, 7 };
        int N = arr.length;
        System.out.println(resultOfAllSubsets(arr, N));
    }
}
 
// This code is contributed by vt_m

# Python3 program to get sum
# of average of all subsets
 
# Returns value of Binomial
# Coefficient C(n, k)
def nCr(n, k):
 
    C = [[0 for i in range(k + 1)]
            for j in range(n + 1)]
 
    # Calculate value of Binomial
    # Coefficient in bottom up manner
    for i in range(n + 1):
     
        for j in range(min(i, k) + 1):
         
            # Base Cases
            if (j == 0 or j == i):
                C[i][j] = 1
 
            # Calculate value using
            # previously stored values
            else:
                C[i][j] = C[i-1][j-1] + C[i-1][j]
     
    return C[n][k]
 
# Method returns sum of
# average of all subsets
def resultOfAllSubsets(arr, N):
 
    result = 0.0 # Initialize result
 
    # Find sum of elements
    sum = 0
    for i in range(N):
        sum += arr[i]
 
    # looping once for all subset of same size
    for n in range(1, N + 1):
 
        # each element occurs nCr(N-1, n-1) times while
        # considering subset of size n */
        result += (sum * (nCr(N - 1, n - 1))) / n
 
    return result
 
# Driver code
arr = [2, 3, 5, 7]
N = len(arr)
print(resultOfAllSubsets(arr, N))
 
 
# This code is contributed by Anant Agarwal.

// C# program to get sum of
// average of all subsets
using System;
 
class GFG {
     
    // Returns value of Binomial
    // Coefficient C(n, k)
    static int nCr(int n, int k)
    {
        int[, ] C = new int[n + 1, k + 1];
        int i, j;
 
        // Calculate value of Binomial
        // Coefficient in bottom up manner
        for (i = 0; i <= n; i++) {
            for (j = 0; j <= Math.Min(i, k); j++)
            {
                // Base Cases
                if (j == 0 || j == i)
                    C[i, j] = 1;
 
                // Calculate value using
                // previously stored values
                else
                    C[i, j] = C[i - 1, j - 1] + C[i - 1, j];
            }
        }
        return C[n, k];
    }
 
    // method returns sum of average
    // of all subsets
    static double resultOfAllSubsets(int[] arr, int N)
    {
        // Initialize result
        double result = 0.0;
 
        // Find sum of elements
        int sum = 0;
        for (int i = 0; i < N; i++)
            sum += arr[i];
 
        // looping once for all subset
        // of same size
        for (int n = 1; n <= N; n++)
 
            /* each element occurs nCr(N-1, n-1) times while
               considering subset of size n */
            result += (double)(sum * (nCr(N - 1, n - 1))) / n;
 
        return result;
    }
 
    // Driver code to test above methods
    public static void Main()
    {
        int[] arr = { 2, 3, 5, 7 };
        int N = arr.Length;
        Console.WriteLine(resultOfAllSubsets(arr, N));
    }
}
 
// This code is contributed by Sam007

<?php
// PHP program to get sum
// of average of all subsets
 
// Returns value of Binomial
// Coefficient C(n, k)
function nCr($n, $k)
{
    $C[$n + 1][$k + 1] = 0;
    $i; $j;
 
    // Calculate value of Binomial
    // Coefficient in bottom up manner
    for ($i = 0; $i <= $n; $i++)
    {
        for ($j = 0; $j <= min($i, $k); $j++)
        {
            // Base Cases
            if ($j == 0 || $j == $i)
                $C[$i][$j] = 1;
 
            // Calculate value using
            // previously stored values
            else
                $C[$i][$j] = $C[$i - 1][$j - 1] +
                             $C[$i - 1][$j];
        }
    }
    return $C[$n][$k];
}
 
// method returns sum of
// average of all subsets
function resultOfAllSubsets($arr, $N)
{
    // Initialize result
    $result = 0.0;
 
    // Find sum of elements
    $sum = 0;
    for ($i = 0; $i < $N; $i++)
        $sum += $arr[$i];
 
    // looping once for all
    // subset of same size
    for ($n = 1; $n <= $N; $n++)
 
        /* each element occurs nCr(N-1,
        n-1) times while considering
        subset of size n */
        $result += (($sum * (nCr($N - 1,
                                 $n - 1))) / $n);
 
    return $result;
}
 
// Driver Code
$arr = array( 2, 3, 5, 7 );
$N = sizeof($arr) / sizeof($arr[0]);
echo resultOfAllSubsets($arr, $N) ;
 
// This code is contributed by nitin mittal.
?>

<script>
    // javascript program to get sum of
    // average of all subsets
     
    // Returns value of Binomial
    // Coefficient C(n, k)
    function nCr(n, k)
    {
        let C = new Array(n + 1);
        for (let i = 0; i <= n; i++)
        {
            C[i] = new Array(k + 1);
            for (let j = 0; j <= k; j++)
            {
                C[i][j] = 0;
            }
        }
        let i, j;
   
        // Calculate value of Binomial
        // Coefficient in bottom up manner
        for (i = 0; i <= n; i++) {
            for (j = 0; j <= Math.min(i, k); j++) {
                // Base Cases
                if (j == 0 || j == i)
                    C[i][j] = 1;
   
                // Calculate value using
                // previously stored values
                else
                    C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
            }
        }
        return C[n][k];
    }
   
    // method returns sum of average of all subsets
    function resultOfAllSubsets(arr, N)
    {
        // Initialize result
        let result = 0.0;
   
        // Find sum of elements
        let sum = 0;
        for (let i = 0; i < N; i++)
            sum += arr[i];
   
        // looping once for all subset of same size
        for (let n = 1; n <= N; n++)
   
            /* each element occurs nCr(N-1, n-1) times while
            considering subset of size n */
            result += (sum * (nCr(N - 1, n - 1))) / n;
   
        return result;
    }
     
    let arr = [ 2, 3, 5, 7 ];
    let N = arr.length;
    document.write(resultOfAllSubsets(arr, N));
     
</script>

Producción :  

63.75

Este artículo es una contribución de Utkarsh Trivedi . 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 review-team@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.