Suma iloczynu wszystkich możliwych podzbiorów macierzy

Question

Napisałem kod, aby znaleźć Suma iloczynu wszystkich możliwych podzbiorów macierzy. Otrzymuję oczekiwany wynik, ale nie jestem w stanie zrobić tego wystarczająco szybko, aby usunąć przypadki testowe związane z czasem.

Czy ktoś może mi pomóc w optymalizacji mojego kodu na szybkość?

Pierwsze wejście (testCases) to liczba testcases. W zależności od liczby wersji testowej, będziemy mieć rozmiar tablicy (rozmiar) i elementy tablicy (zestaw).

Na przykład, ważne wejściowy będzie:

1 
3 
2 3 5 

gdzie:

1 oznacza liczbę testami. 3 to rozmiar zestawu testowego i 2 3 5 są elementami zestawu wejściowego.

oczekiwany wynik wynosi:

71

Obliczenia dla powyższego wyjścia:

{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

Musisz użyć trochę matematyki. Powiedzmy, że masz 3 wartości, jak na przykład, ale możesz je nazwać A, B i C.

Aby uzyskać sumę produktów, trzeba obliczyć:

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

Teraz, jeśli obliczymy A + B + A*B pierwszy, nazywając go Result2, a następnie pojawi się:

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

I powtarzamy, że więc

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

Czy widzisz wzór? Użyjmy że z 4 wartości:

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 

Podsumowanie:

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

jako kod, to jest:

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

Tylko jedna iteracja, więc O (n).

test

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

Wyjście

11 
71 
575 

UPDATE

Kod może być również wykonane przy użyciu Java 8 strumieni wyrażenia lambda, stosując albo IntStream.of(int...) lub Arrays.stream(int[]) (robią to samo).

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