Counting n powersets given a list

Question

I am writing a function that determines the number 'n' power sets of a list. After processing the problem and working through it I found the relationship between the length of the set and the number of powersets.

2^i

where i is the length of the list.

This formula holds true for:

Powers.powers(new int[]{});        // 1
Powers.powers(new int[]{1});       // 2
Powers.powers(new int[]{1,2});     // 4
Powers.powers(new int[]{1,2,3,4}); // 16

Using this information I wrote out the following code:

if(list.length == 1) return BigInteger.valueOf(2);
if(list.length == 0) return BigInteger.valueOf(1);
return BigInteger.valueOf((long)Math.pow(2, list.length));

This works fine for the first few tests, until it hiccups at array length 100. Fortunately it does calculate the correct value that being 1.2676506e+30, but the expected number of powersets of Arraysize 100 is: 9223372036854775807.

Edit: Adjusted the formula to 2^i, and to clarify I understand how the calculation works, I just don't understand how or why the test case expects 9223372036854775807. It passes an array of length 100 with all values being 0 except for value of index 99 being 100.

you mean `|P(S)| = 2^n` (same as `4 ^ (n/2)`, but cleaner). Thats `1 << n` in `BigInt`. — Pierre D, Dec 12 '20 at 14:50
Since all the other results are even numbers, why would you expect the result for 100 to be the odd number Long.MAX_VALUE, i.e. 9223372036854775807? — Andreas, Dec 12 '20 at 14:50
expected:<9223372036854775807> but was:<1267650600228229401496703205376> my test case is expecting this. I did not write the test case. — Rawley Fowler, Dec 12 '20 at 14:52
The code you showed does return 9223372036854775807, because `double` value 1.2676506e+30 becomes `Long.MAX_VALUE` when cast to a `long`, because of the numeric overflow that would otherwise occur. --- You said it actually returned 1267650600228229401496703205376, but I cannot reproduce that result, given the shown code. — Andreas, Dec 12 '20 at 14:55
BTW, if you ever need to do it using first principles (e.g. in a language that doesn't have the luxury of arbitrary precision arithmetic), see https://stackoverflow.com/a/55405842/758174. — Pierre D, Dec 12 '20 at 14:56
Without an explanation of why you expect that odd-numbered result, this question is unanswerable. — kaya3, Dec 12 '20 at 14:58

Andreas · Accepted Answer · 2020-12-12T15:30:54.350

You mean 2 ^ n, not 4 ^ (n/2). Well, it's actually the same thing.

And it is very easily calculated with BigInteger, without risk of overflow:

static BigInteger powerSets(int n) {
    return BigInteger.ONE.shiftLeft(n);
}

Test

System.out.println(powerSets(0));
System.out.println(powerSets(1));
System.out.println(powerSets(2));
System.out.println(powerSets(4));
System.out.println(powerSets(100));
System.out.println(powerSets(1000));

Output

1
2
4
16
1267650600228229401496703205376
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

UPDATE: If there can be duplicate values, it becomes slightly more complex:

static BigInteger powers(int... values) {
    return Arrays.stream(values).boxed()
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
            .values().stream()
            .map(freq -> BigInteger.valueOf(freq + 1))
            .reduce(BigInteger.ONE, BigInteger::multiply);
}

Test

System.out.println(powers());
System.out.println(powers(1));
System.out.println(powers(1,2));
System.out.println(powers(1,2,3,4));
System.out.println(powers(0,1,2,3,4,5,6,7,8,9,
                          10,11,12,13,14,15,16,17,18,19,
                          20,21,22,23,24,25,26,27,28,29,
                          30,31,32,33,34,35,36,37,38,39,
                          40,41,42,43,44,45,46,47,48,49,
                          50,51,52,53,54,55,56,57,58,59,
                          60,61,62,63,64,65,66,67,68,69,
                          70,71,72,73,74,75,76,77,78,79,
                          80,81,82,83,84,85,86,87,88,89,
                          90,91,92,93,94,95,96,97,98,99));
System.out.println(powers(1,3,3,3,3,7));

Output

1
2
4
16
1267650600228229401496703205376
20

Counting n powersets given a list

1 Answers1