Summe des Produkts aller möglichen Teilmengen von Array

Question

Ich habe einen Code geschrieben, um Summe des Produkts aller möglichen Teilmengen von Array zu finden. Ich bekomme die erwartete Ausgabe, aber ich kann es nicht schnell genug machen, um zeitbezogene Testfälle zu löschen.

Kann mir jemand bei der Optimierung meines Codes für Geschwindigkeit helfen?

Die erste Eingabe (testCases) ist die Anzahl der Testfälle. Abhängig von der Anzahl der Testfälle haben wir die Größe der Array- (Größe) und Array-Elemente (Set).

Zum Beispiel eine gültige Eingabe wäre:

1 
3 
2 3 5 

wo:

1 die Anzahl der Testfälle ist. 3 ist die Größe des Testsets und 2 3 5 sind die Elemente des Eingabesets.

die erwartete Ausgabe ist:

71

Die Berechnung für die oben genannte Ausgabe ist:

{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

Sie müssen ein wenig Mathematik verwenden. Nehmen wir an, Sie haben 3 Werte, wie Ihr Beispiel, aber rufen Sie sie A, B und C.

Summe von Produkten zu erhalten, müssen Sie berechnen:

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

Wenn wir nun A + B + A*B zuerst berechnen, es Result2 Aufruf, dann erhalten Sie:

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

Und wir wiederholen, dass, also

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

Können Sie das Muster sehen? Lassen Sie uns das nutzen mit 4 Werte:

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 

Zusammenfassung:

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

Als Code, das ist:

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

nur eine Iteration, so O (n).

-Test

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

Ausgabe

11 
71 
575 

UPDATE

-Code auch mit einem Lambda-Ausdruck Java 8 Streams verwendet getan werden kann, entweder IntStream.of(int...) oder Arrays.stream(int[]) (sie machen das gleiche).

// 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(); 
}