Separating merged array of arithmetic and geometric series [closed]

Given an array of positive integers in increasing order. Separate them in two series, an arithmetic sequence and geometric sequence. The given array is such that a solution do exist.

The union of numbers of the two sequence must be the given array.
Both series can have common elements i.e. series need not to be disjoint.
The ratio of the geometric series can be fractional.

Example:

Given series : 2,4,6,8,10,12,25
AP: 2,4,6,8,10,12
GP: 4,10,25

I tried taking few examples but could not reach a general way. Even tried some graph implementation by introducing edges if they follow a particular sequence but could not reach solution.

You can do this in linear time.

First, notice that a geometric progression is just an arithmetic progression in the elementwise logarithm of the sequence. So we can think of having a sequence of pairs of numbers that we want to cover with a progression that is arithmetic in the first element and a progression that is arithmetic in the second element.

Two of the first three elements must lie in the same progression. Without loss of generality, I’ll assume it’s the arithmetic progression. You can find, in linear time, the longest arithmetic sequence with the right beginning and common difference that is a subsequence of your input. You do that and then you’re left with a bunch of uncovered elements; say their logarithms are g_1, g_2, …, g_k.

Find the “greatest common divisor” of g_2-g_1, …, g_k-g_1 — I want the biggest real number d such that g_2-g_1, g_3-g_1, …, g_k-g_1 can all be written as multiples of d.

Then, if there is a geometric progression covering g_1, …, g_k that is a subsequence of your input, there must be one with common ratio d. All you need to do is check that g_1, g_1 * exp(d), g_1 * exp(2d), …, g_k are all elements of your input, and you can do this in linear time.

So you do the above six times (twice — arithmetic and geometric — for each of the three possible choices of “first two”), and the above takes linear time.

Let’s assume a sequence must contain at least 2 numbers. Here is a more or less brute-force approach:

calculate the difference of each pair of numbers: this gives you a finite number of possible differences (lets call that number set D). One of that differences must be the constant difference of the AP
also, calculate the of ratio each pair of numbers: this gives you a finite number of possible ratios (lets call that number set R). One of that must be the constant ration of the GP
Choose each pair (d,r) out of D x R. Test if you can find an AP beeing a sub-sequence with constant diff d and and a GP sub-sequence with constant ratio r, so that the union of both sub-sequences form the original sequence.

For the last step, you have to consider that there may be more than one possible subsequence for a given d or r. However, you can do better than just generating all possible sub-sequences if you make use of that fact that at least one of the two sequences must contain the first of all numbers, and the second one must contain one of the numbers which is not contained within the other sub-sequence.

For instance, when using your example above, the set D will contain 2 (and some more numbers), and R will contain 2, 2.5, and some more numbers. Testing d=2, r=2, will lead to the AP 2,4,6,8,10,12, but the remaining number 25 is not part of a GP with at least two numbers and r=2 (neither 50 nor 12.5 is part of the given number set). However, when the next test is d=2, r=2.5, you will easily find the solution above.

You can try some method to find the longest arithmetic progression. Here is simple DP solution with quadratic complexity, and full pdf document contains clues to (theoretically) more effective method.

This method is applicable to geometric series to (checking A[i] + A[k] = 2*A[j] turns into A[i] * A[k] = A[j] * A[j] and so on..)

I would rather interpret your example as
AP: 2,4,6,8,10,12
GP: 25
as this is a valid interpretation as well and easier to find.

I’d first look at the first three integers. Let’s call them a, b and c.

If b – a = c – b, you can assume that this is the step width of your arithmetic series, and the geometric series has not started yet.
If b/a = c/b, you can assume that this is the ratio of the geometric series, and that the arithmetic series has not started yet.
Independently of whether or not either of the above conditions are met (thanks to
tmyklebu for pointing this out), you have several other valid hypotheses. You can assume that any two of the numbers form the beginning of one of the series, and the remaining element the beginning of the other series.

You could maintain a list of currently valid hypotheses as you proceed along the array. In the case of a hypothesis with only a single started sequence, you have to assume that the first number not belonging to that sequence is the beginning of the other sequence. If you have one sequence and the start of another sequence, you will likely encounter a number which is not part of the defined sequence. You can use that to define the remaining sequence.

You have to take some care. When you had a geometric series and find the second number not fitting that series, you know you have found two numbers belonging to the arithmetic series. But their difference might be a multiple of the step width. So you should iterate over all divisors of that difference, and check whether the intermediate values indicated by thas reduced step width are present in the geometric series. Only up to two elements of an arithmetic series can be part of a geometric series as well, so no need to check all divisors. It is enough to check for half and one-third of the width, and only if that number is an integer. A similar consideration has to be used to find the ratio of the geometric series, taking posisble duplicate elements into account. You have to check for the square root and cubic root of the fraction of the two defining numbers, and see whether these are rational as well and result in integers. Rounding might be an issue unless you have a data structure to represent rational numbers and do prime factor decomposition.

It might be that multiple step widths or ratios are consistent with the data so far. In that case, you should go with all of them, checking the remaining data to see whether they still hold. In the end, you either have a single valid hypothesis, or a set of hypotheses from which you can choose at will. If you want to, you could then check whether any of these series can be extended before the assumed first element, by reusing elements of the other series. This could be used to find 4 and 10 in the example of yours. But the answer should be valid even without this step.

Filed under: softwareengineering - @ 14:26

Thẻ: math, sequence

Thiết kế website giá rẻ

Danh mục

Separating merged array of arithmetic and geometric series [closed]