数组所有可能子集的乘积总和 [英] Sum of product of all possible subsets of array

问题描述

我写了一段代码来查找数组所有可能子集的乘积之和。我得到了预期的输出，但是我不能足够快地清除与时间相关的测试用例。

有人可以帮我优化我的代码以提高速度吗？

首次输入（testCases）是测试用例的数量。
根据测试用例的数量，我们将得到数组的大小（大小）和数组元素的大小（集合）。

例如，有效输入为：

  1 
 3 
 2 3 5 
  

其中：

1 是测试用例的数量。 3 是测试集的大小， 2 3 5 是输入集的元素。

预期输出为：

71

以上输出的计算结果为：

  {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 
  

---

 导入java.util.Scanner; 
 
公共类测试{
 static int printSubsets（int set []）{
 int n = set.length; 
 int b = 0; 
 
 for（int i = 0; i<（1< n）; i ++）{
 int a = 1; （int j = 0; j< n; j ++）{
 
 if（（i&（1<< j））> 0）{
 
a * = set [j]; 
}} 
 
 b + = a; 
} 
返回b； 
} 
 
 public static void main（String [] args）{
 
扫描仪扫描程序= 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（）; 
} 
} 
  

解决方案

您需要使用一点数学。假设您有3个值（例如您的示例），但是将它们称为 A ， B 和 C 。

要获得产品总和，您需要计算：

 结果3 = A + B + C + A * B + A * C + B * C + A * B * C 
 = A + B + A * B +（ 1 + A + B + A * B）* C 
  

现在，如果我们计算 A + B + A * B 首先，将其称为 Result2 ，然后您将得到：

  Result2 = A + B + A * B 
 Result3 = Result2 +（1 + Result2）* C 
  

我们重复一遍，所以

  Result2 = A + （1 + A）* B 
结果1 = A 
结果2 =结果1 +（1 +结果1）* B 
  

可以看到图案吗？让我们将其与4个值一起使用：

  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 
 =结果3 +（1 + Result3）* D 
  

摘要：

  Result1 = A 
 Result2 = Result1 +（1 + Result1）* B 
结果3 =结果2 +（1 +结果2）* C 
结果4 =结果3 +（1 +结果3）* D 
  

按照代码，这是：

  private static long sumProduct（int ... input）{ 
长结果= 0; 
代表（int值：输入）
结果+ =（结果+ 1）*值; 
的返回结果； 
} 
  

仅一次迭代，因此 O（n） 。

Test

 系统。 out.println（sumProduct（2，3））; 
 System.out.println（sumProduct（2，3，5））; 
 System.out.println（sumProduct（2，3，5，7））; 
  

输出

< pre class = lang-none prettyprint-override> 11
71
575


更新

也可以使用带有Lambda表达式的Java 8 Streams使用 IntStream.of（int ...） 或 Arrays.stream（int []） （它们相同）。 / p>

  //将IntStream与结果一起用作int 
私有静态int sumProduct（int ..输入）{
 return IntStream.of（input）.reduce（（a，b）-> a +（1 + a）* b）.getAsInt（）; 
} 
  

  //使用结果为long的数组
 private static long sumProduct（int ... input）{
 return Arrays.stream（input）
 .asLongStream（）
 .reduce（ （a，b）-> a +（1 + a）* b）
 .getAsLong（）; 
} 
  

I have written a code to find Sum of product of all possible subsets of array. I'm getting the expected output but I'm not able to make it fast enough to clear time related test cases.

Can anyone help me in optimizing my code for speed?

First input (testCases) is the number of testcases. Depending on number of testcase, we will have size of array (size) and array elements (set).

For example, a valid input would be:

1
3
2 3 5

where:

1 is the number of testcases. 3 is the size of the test set and 2 3 5 are the elements of the input set.

The expected output is:

71

The calculation for the above output is:

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

解决方案

You need to use a little math. Lets say you have 3 values, like your example, but lets call them A, B, and C.

To get sum of products, you need to calculate:

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

Now, if we calculate A + B + A*B first, calling it Result2, then you get:

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

And we repeat that, so

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

Can you see the pattern? Let's use that with 4 values:

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

Summary:

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

As code, this is:

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

Only one 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));

Output

11
71
575

UPDATE

Code can also be done using Java 8 Streams with a Lambda expression, using either IntStream.of(int...) or Arrays.stream(int[]) (they do the same).

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

这篇关于数组所有可能子集的乘积总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！