How to find the number of times each number is either the greatest or smallest in each subsequence of a fixed size?
So, I need to find the product of all numbers in all the subsequences except for the smallest and largest number in each subsequence. I have observed that each number is repeated a fixed number of times in subsequences of a size k. I haven't derived the formula for it but have clearly observed it from different cases. If somehow, I could find the number of times each element is the smallest or largest in the subsequences, I could find the answer but am unable to proceed in this direction.
define 'all the subsequences'. is that every possible combination?
define number. Is this a double, int with an upper bound, random int, etc??
is this a vector of values, or something else?
define number. Is this a double, int with an upper bound, random int, etc??
is this a vector of values, or something else?
@jonnin I have INTEGER values with the maximum value being 10000 and total elements in the array can be at max 5000. As I said, I want SUBSEQUENCES of FIXED size.
So if I have array {2,3,5,4} and k = 3, then I will have subsequences- {2,3,5},{2,3,4},{2,5,4},{3,5,4} as they are the only possible subsequences of size(k=3) = 3....My ultimate goal is to find the product of all these numbers in all such subsequences EXCEPT for the smallest and the largest values in the subsequence...So,for example from the subsequence {2,3,5}, I will consider the value 3 since 2 and 5 will be eliminated being the smallest and largest value in this subsequence....So in all, we will have 3*3*4*4 = 144...
So if I have array {2,3,5,4} and k = 3, then I will have subsequences- {2,3,5},{2,3,4},{2,5,4},{3,5,4} as they are the only possible subsequences of size(k=3) = 3....My ultimate goal is to find the product of all these numbers in all such subsequences EXCEPT for the smallest and the largest values in the subsequence...So,for example from the subsequence {2,3,5}, I will consider the value 3 since 2 and 5 will be eliminated being the smallest and largest value in this subsequence....So in all, we will have 3*3*4*4 = 144...
Last edited on
the final product result will be a gigantic number... why would you ever want to multiply all these found numbers together?
If hypothetically your "array" (did you actually mean more like a set of unique, sorted ints?) was the max size of 5000 and looked like {1,1,1,1,1,1... 3, 999,999,999,999,999...}, then 3**4998 alone looks like it's 2385 digits long.
If hypothetically your "array" (did you actually mean more like a set of unique, sorted ints?) was the max size of 5000 and looked like {1,1,1,1,1,1... 3, 999,999,999,999,999...}, then 3**4998 alone looks like it's 2385 digits long.
Last edited on
My bad...I have to find the product%1000000007...I can use combinatorics to find the number of times each number will be included in the final result but this power will be too long and hence I cannot use it.
I agree with icy, but
INTEGER values with the maximum value being 10000
^^^
this tells me you can count the repeats with a bucket type approach.
eg if the number is 23,
bucket[23]++;
and bucket[23] tells you how many 23s you have.
an array of 10000 of ints is not a big deal. And that actually fits in shorts.
INTEGER values with the maximum value being 10000
^^^
this tells me you can count the repeats with a bucket type approach.
eg if the number is 23,
bucket[23]++;
and bucket[23] tells you how many 23s you have.
an array of 10000 of ints is not a big deal. And that actually fits in shorts.
Last edited on
Actually the number of times a number is repeated in a sequence is the problem...It will be too damn high when suppose you have 5000 elements and say you are at the middle element and are forming sub sequences of size 2...here, the number of times this number will be repeated would be very very large.
Last edited on
n total size
k subsequence size
number of combinations? n choose k
number of times a particular number is seen in all combinations? (n-1) choose (k-1)
So for the same simple example
[ [1,2,3], [1,2,4], [1,3,4], [2,3,4] ]
total combinations: 4 choose 3 --> 4 combinations in total.
"1" is seen: 3 choose 2 --> 3 times
"4" is also seen 3 times.
However you can't just product everything with power occurrences and divide by min/max to that power, because:
1**3 * 2**3 * 3**3 * 4**3 / 1**3 / 4**3 --> result is 216.
In the first subset, "3" is the maximum and should be discarded.
In the last subset, "2" is the minimum and should also be discarded.
So that's why the real answer is 36, or 6 times less.
Btw, the big prime thing can help you keep the running product low. As you calculate the product, you can take its modulus if it's greater than that prime.
Easier on scripting languages that automagically upscale to bigger ints; on C++ might just need to have everything as long.
k subsequence size
number of combinations? n choose k
number of times a particular number is seen in all combinations? (n-1) choose (k-1)
So for the same simple example
[ [1,2,3], [1,2,4], [1,3,4], [2,3,4] ]
total combinations: 4 choose 3 --> 4 combinations in total.
"1" is seen: 3 choose 2 --> 3 times
"4" is also seen 3 times.
However you can't just product everything with power occurrences and divide by min/max to that power, because:
1**3 * 2**3 * 3**3 * 4**3 / 1**3 / 4**3 --> result is 216.
In the first subset, "3" is the maximum and should be discarded.
In the last subset, "2" is the minimum and should also be discarded.
So that's why the real answer is 36, or 6 times less.
Btw, the big prime thing can help you keep the running product low. As you calculate the product, you can take its modulus if it's greater than that prime.
x = 1000000007 # Some loop that increases prod... prod = prod%x if prod>x |
Easier on scripting languages that automagically upscale to bigger ints; on C++ might just need to have everything as long.
oh, nevermind, lol, I can see how to fix my "however" caveat ;D
Find next_min, next_max, the next ones in line. We'll see these next_occurrences times, or (n choose k) - (n-1 choose k-1).
Edit: nevermind again; it's not so simple. Sometimes the next_min is not the min either (and same for next_max). In the case of an array [1,2,3,4,5] with k=3, one of the sets will be [3,4,5] and so the min is neither 1 nor 2. Similarly, there is also a set [1,2,3], where the max is neither 5 nor 4.
Needs more hardening, but the core goal seems correct -- to find a strategy without explicitly listing all the combinations
Find next_min, next_max, the next ones in line. We'll see these next_occurrences times, or (n choose k) - (n-1 choose k-1).
prod /= (next_min*next_occurrences) prod /= (next_max*next_occurrences) |
Edit: nevermind again; it's not so simple. Sometimes the next_min is not the min either (and same for next_max). In the case of an array [1,2,3,4,5] with k=3, one of the sets will be [3,4,5] and so the min is neither 1 nor 2. Similarly, there is also a set [1,2,3], where the max is neither 5 nor 4.
Needs more hardening, but the core goal seems correct -- to find a strategy without explicitly listing all the combinations
Last edited on
sort the array
the operation on the subsequence ignores its order, so you only care about the combination
say you are on position j, the element a_j will be the minimum of C(j-1, k-1) and the maximum of C(n-j, k-1) subsequences (the combinations that you may do with elements that are only to the left and to the right of j)
the operation on the subsequence ignores its order, so you only care about the combination
say you are on position j, the element a_j will be the minimum of C(j-1, k-1) and the maximum of C(n-j, k-1) subsequences (the combinations that you may do with elements that are only to the left and to the right of j)
What you guys are saying is correct but C(n,r) can be very large which cant be stored in a number
@ne555 You see suppose the number of elements are 5000....The 5000Cr will be a very very large number....5000! alone contain around 10^4 digits!
Topic archived. No new replies allowed.