I am doing the following programming exercise: Counting power sets. The statement is:
In this kata, you must create a function powers/Powers that takes an array, and returns the number of subsets possible to create from that list. In other words, counts the power sets.
For instance
powers([1,2,3]) => 8
...due to...
powers([1,2,3]) => [[], 1, [2], [3], [1,2], [2,3], [1,3], [1,2,3]]
Your function should be able to count sets up to the size of 500, so watch out; pretty big numbers occur there!
For comparison, my Haskell solution can compute the number of sets for an array of length 90 000 in less than a second, so be quick!
You should treat each array passed as a set of unique values for this kata.
Examples:
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
I have written the following answer:
import java.math.BigInteger;
import java.util.*;
public class Powers {
public static BigInteger powers/**/(int[] list) {
System.out.println("list: "+Arrays.toString(list));
System.out.println("list length: "+list.length);
double pow = Math.pow(2, list.length);
System.out.println("pow: "+pow);
return new BigInteger(String.valueOf((long)pow));
}
}
However for a 100 array it does not output the expected result. For example, for the following array:
list: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
list length: 100
It outputs:
9223372036854775807
Instead of:
1267650600228229401496703205376
I thought the difficulty was generated by rounnding the pow result from double to long, because of it outputs:
pow: 1.2676506002282294E30
Then I tried to use modPow to be able to get results with bigger numbers:
import java.math.*;
import java.util.*;
public class Powers {
public static BigInteger powers/**/(int[] list) {
System.out.println("list: "+Arrays.toString(list));
System.out.println("list length: "+list.length);
BigInteger pow = BigInteger.valueOf(2).modPow(BigInteger.valueOf(list.length), BigInteger.valueOf(Long.MAX_VALUE));
System.out.println("pow: "+pow);
return new BigInteger(String.valueOf(pow));
}
}
However when we test with the 100 length array, the output is:
137438953472
When it should be:
1267650600228229401496703205376
I think the challenge is due to Long.MAX_VALUE is equal than the highest value being calculated by modPow, because of it outputs:
pow: 137438953472
After that I tried to write a higher number for modulus inside modPow function and I wrote this:
import java.math.*;
import java.util.*;
public class Powers {
public static BigInteger powers/**/(int[] list) {
System.out.println("list: "+Arrays.toString(list));
System.out.println("list length: "+list.length);
BigInteger modulus = BigDecimal.valueOf(Double.POSITIVE_INFINITY).toBigInteger();
BigInteger pow = BigInteger.valueOf(2).modPow(BigInteger.valueOf(list.length), modulus);
System.out.println("pow: "+pow);
return new BigInteger(String.valueOf(pow));
}
}
However the following exception is being thrown:
java.lang.NumberFormatException: Character I is neither a decimal digit number, decimal point, nor "e" notation exponential mark.
at java.base/java.math.BigDecimal.<init>(BigDecimal.java:518)
at java.base/java.math.BigDecimal.<init>(BigDecimal.java:401)
at java.base/java.math.BigDecimal.<init>(BigDecimal.java:834)
at java.base/java.math.BigDecimal.valueOf(BigDecimal.java:1304)
at Powers.powers(Powers.java:7)
I think it is generated because of Double.POSITIVE_INFINITY gives us a bigger number than the highest being represented by BigInteger.
So as a result, the first two codes could pass the following tests:
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.fail;
import org.junit.Test;
import org.junit.Ignore;
import java.math.BigInteger;
public class PowersTest {
@Test
public void testPactical() {
assertEquals("An empty array should return 1!", Powers.powers(new int[]{}), BigInteger.valueOf(1));
assertEquals(Powers.powers(new int[]{1}), BigInteger.valueOf(2));
assertEquals(Powers.powers(new int[]{1,2,3,4,5}), BigInteger.valueOf(32));
}
}
However both codes, have difficulties to pass the 100 length array test.
In addition I have read:
- BigInteger.pow(BigInteger)?
- https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#modPow(java.math.BigInteger,%20java.math.BigInteger)
- https://www.tutorialspoint.com/java/math/biginteger_modpow.htm
- What does BigInteger having no limit mean?
- How to implement infinity in Java?
Could you help me to find out how to count power sets with very large arrays in Java?‽
EDIT:
It is solved by writting:
import java.math.*;
import java.util.*;
public class Powers {
public static BigInteger powers/**/(int[] list) {
return BigInteger.valueOf(2).pow(list.length);
}
}
