Somme du produit de tous les sous-ensembles possibles du tableau

Question

J'ai écrit un code pour trouver la somme du produit de tous les sous-ensembles possibles du tableau. J'obtiens la sortie attendue mais je ne suis pas capable de la faire assez rapidement pour effacer les cas de test liés au temps.

Quelqu'un peut-il m'aider à optimiser mon code pour la vitesse?

La première entrée (testCases) est le nombre de cas de test. Selon le nombre de cas de test, nous aurons la taille de tableau (taille) et les éléments de tableau (ensemble).

Par exemple, une entrée valide serait:

1 
3 
2 3 5 

où:

1 est le nombre de cas de test. 3 est la taille de l'ensemble de test et 2 3 5 sont les éléments de l'ensemble d'entrée.

Le résultat attendu est la suivante:

71

Le calcul de la sortie ci-dessus est la suivante:

{2}, {3}, {5}, {2, 3}, {3, 5}, {2, 5}, {2, 3, 5} 

=> 2 3 5  6  15  10  30 

=> 2 + 3 + 5 + 6 + 15 + 10 + 30 

=> 71 

---

import java.util.Scanner; 

public class Test { 
    static int printSubsets(int set[]) { 
     int n = set.length; 
     int b = 0; 

     for (int i = 0; i < (1 << n); i++) { 
      int a = 1; 
      for (int j = 0; j < n; j++){ 

       if ((i & (1 << j)) > 0) { 

        a *= set[j]; 
       }} 

      b += a; 
     } 
     return b; 
    } 

    public static void main(String[] args) { 

     Scanner scanner = new Scanner(System.in); 
     int testCases = scanner.nextInt(); 

     for (int i = 0; i < testCases; i++) { 
      int size = scanner.nextInt(); 
      int set[] = new int[size]; 
      for (int j = 0; j < set.length; j++) { 
       set[j] = scanner.nextInt(); 
      } 

      int c = printSubsets(set); 
      System.out.println((c - 1)); 

     } 
     scanner.close(); 
    } 
} 

Answer 1

Vous devez utiliser un peu de maths. Disons que vous avez 3 valeurs, comme votre exemple, mais appelons les A, B, et C.

Pour obtenir la somme des produits, vous devez calculer:

Result3 = A + B + C + A*B + A*C + B*C + A*B*C 
     = A + B + A*B + (1 + A + B + A*B) * C 

Maintenant, si l'on calcule A + B + A*B d'abord, l'appelant Result2, vous obtenez:

Result2 = A + B + A*B 
Result3 = Result2 + (1 + Result2) * C 

Et nous répétons que, donc

Result2 = A + (1 + A) * B 
Result1 = A 
Result2 = Result1 + (1 + Result1) * B 

Pouvez-vous voir le motif? Utilisons que, avec 4 valeurs:

Result4 = A + B + C + D + A*B + A*C + A*D + B*C + B*D + C*D 
     + A*B*C + A*B*D + A*C*D + B*C*D + A*B*C*D 
     =  A + B + C + A*B + A*C + B*C + A*B*C 
     + (1 + A + B + C + A*B + A*C + B*C + A*B*C) * D 
     = Result3 + (1 + Result3) * D 

Résumé:

Result1 = A 
Result2 = Result1 + (1 + Result1) * B 
Result3 = Result2 + (1 + Result2) * C 
Result4 = Result3 + (1 + Result3) * D 

code, c'est:

private static long sumProduct(int... input) { 
    long result = 0; 
    for (int value : input) 
     result += (result + 1) * value; 
    return result; 
} 

Une seule itération, donc O (n).

test

System.out.println(sumProduct(2, 3)); 
System.out.println(sumProduct(2, 3, 5)); 
System.out.println(sumProduct(2, 3, 5, 7)); 

Sortie

11 
71 
575 

MISE À JOUR

code

peut également être fait en utilisant Java 8 Streams avec une expression Lambda, en utilisant IntStream.of(int...) ou Arrays.stream(int[]) (ils font la même chose).

// Using IntStream with result as int 
private static int sumProduct(int... input) { 
    return IntStream.of(input).reduce((a, b) -> a + (1 + a) * b).getAsInt(); 
} 

// Using Arrays with result as long 
private static long sumProduct(int... input) { 
    return Arrays.stream(input) 
       .asLongStream() 
       .reduce((a, b) -> a + (1 + a) * b) 
       .getAsLong(); 
}