Has anyone considered this problem ? For arbitrary input set with length of n ( i.e. n squares), what is the upperbound for the number of different results ?
Hi,We haven't set any upper bound on the number of different results to report. So, please report all possible.
Thank you ... but this is not what I mean.I just want to know the upperbound theoretically. If the input consists of n integers, is there any upperbound of the number of results theoretically and how to construct an input to reach the upperbound.
I found john_e_lilley shared an input files in other thread http://software.intel.com/en-us/forums/showpost.php?p=150354 which shows an input with 1024 integers may has 11 different results. So the upperbound is at least 1 + log2(n) for input with n integers. However, I do not know if it is the exact upperbound.
I think that's not correct.The worst possible combination is one of the form:2*3*5*7*11*13*17*19**...For example for :
But the number of possible solutions is 2^8=256 for that example.
Do you mean the area equals 9699690 ? Of course the number of possible solution is no more than 2^n, but I do not think there is really an input set has 2^n solutions in our problem. In fact, there are at most n solutions for input set with n integers.Could you please give us an input file (n ordered integers) next time ? Then I can check the number of results by my solver. I believe the test cases are best for demonstration.
Let me clarify.If the area = 9699690 (with a large number of tiles, not necesarily 1x1), and you try to determine the possible rectangle shapes for a tiling test, you'll see that there are 256 possible rectangles (2^number_of_factors for this case, not a generic formula).Let's expand all factors in a smaller case:Test case with 210 ones: 1 1 1 1 ... 1 0The total area is 210. If we decompose the area in prime numbers we get: 210=2*3*5*7 (I expect 2^4 possible rectangles):1 x 2102 x 1053 x 706 x 355 x 4210 x 2115 x 1430 x 77 x 3014 x 1521 x 1042 x 535 x 670 x 3105 x 2210 x 1For each new factor, the number of tiling tests get doubled.
Wow, I got it. This test case is very interesting.It still shows for a very large input, the number of solutions will not too large respect to the input.Anyway, I believe you have given a very special case to demostrate the quickly increasing of the number of solutions.
Its possible that the problem with the largest number of solutions relative to its input size are problems whose total area is the multiple of sequential primes starting at 2. Given N primes, the possibe number of soutions is 2^(N+1) because you also have to account for the 1x and x1 cases (some of which may be excluded by the actual rectangle sizes, of course). So if the problem consists of N! 1's in a row, there will be 2^(N+1) solutions. Since 2^N grows more slowly than N! the output size is less then N*log(N) for the N! 1's case, but I don't know by how much (my math ability ends here :-). I'm not sure what the upper bound of the output-vs-input size is for the general case.