If a sequence is pure arithmetic (1,3,5,7,9...) or pure geometric (3,9,27,81...), its easy to detect.
How about a "mixed" arithmetic/geometric sequence ?
e.g. 2 3 5 6 7 9 10 14
it contain 3 arithmetic sequences (3 6 9), (3 5 7 9) and (2 6 10 14) in it.
e.g. 2 3 4 8 9 16 27 32 81
it contain 2 geometric sequences (2 4 8 16 32) and (3 9 27 81) in it.
e.g. 2 3 4 5 8 9 16 32
it contain 1 geometric sequence (2 4 8 16 32) and 2 arithmetic sequences (2 3 4 5) (3 5 7 9) in it.
(assume sequence should contain more than 2 elements)
Is there any algorithms can detect (analysis) the above mixed sequences and break down it ? i.e. detect and list out all sequences in it ? (Assume original sequence contain <= 20 integers)
Thanks.
Regards,
LAM Chi-fung
Code based on Abhinav Mathur's algorithm, may need more debugging, all result is -1 ;<
#include <Array.au3>
Func GetSequences(ByRef $arr)
Local $arithmetic_seq[1], $geometric_seq[1]
Local $n = UBound($arr)
For $i = 0 To $n - 3
For $j = $i + 1 To $n - 2
Local $arithmetic = $arr[$i] & "|" & $arr[$j]
Local $geometric = $arr[$i] & "|" & $arr[$j]
Local $d = $arr[$j] - $arr[$i]
Local $r = $arr[$j] / $arr[$i]
$ArithTmp=$arr[$j]
$GeoTmp=$arr[$j]
For $k = $j + 1 To $n - 1
If ($arr[$k] - $ArithTmp) = $d Then
$arithmetic &= "|" & $arr[$k]
$ArithTmp=$arr[$k]
EndIf
If $arr[$k] / $GeoTmp = $r Then
$geometric &= "|" & $arr[$k]
$GeoTmp=$arr[$k]
EndIf
Next
If StringReplace($arithmetic, "|", "") <> $arr[$i] & $arr[$j] And StringLen($arithmetic) > 2 Then
_ArrayAdd($arithmetic_seq, StringSplit($arithmetic, "|", 2))
EndIf
If StringReplace($geometric, "|", "") <> $arr[$i] & $arr[$j] And StringLen($geometric) > 2 Then
_ArrayAdd($geometric_seq, StringSplit($geometric, "|", 2))
EndIf
Next
Next
ConsoleWrite("Sequences for " & _ArrayToString($arr) & @CRLF)
ConsoleWrite("Arithmetic: " & @CRLF)
_ArrayDisplay($arithmetic_seq)
; Clear the arithmetic sequence for the next iteration
_ArrayDelete($arithmetic_seq, 1)
ConsoleWrite("Geometric: " & @CRLF)
_ArrayDisplay($geometric_seq)
; Clear the geometric sequence for the next iteration
_ArrayDelete($geometric_seq, 1)
EndFunc
Local $sequence1[9] = [2, 3, 5, 6, 7, 8, 9, 10, 14]
Local $sequence2[9] = [2, 3, 4, 8, 9, 16, 27, 32, 81]
Local $sequence3[9] = [2, 3, 4, 5, 7, 8, 9, 16, 32]
Local $sequences[3] = [$sequence1, $sequence2, $sequence3]
For $i = 0 To UBound($sequences) - 1
GetSequences($sequences[$i])
Next
Since the original sequence has N<=20, it's easier to just brute force it. You could use a simple algorithm for this:
l, n = your_input_list, number_of_elements
arithmetic_seq, geometric_seq = [], []
for i in [1, n]:
for j in [i+1, n]:
arithmetic, geometric = [l[i], l[j]], [l[i], l[j]]
d = l[j] - l[i]
r = l[j] / l[i]
while (arithmetic[-1] + d) in l:
arithmetic.append(arithmetic[-1] + d)
while (geometric[-1] * r) in l:
geometric.append(geometric[-1] * r)
if arithmetic.length > 2:
arithmetic_seq.append(arithmetic)
if geometric.length > 2:
geometric_seq.append(geometric)
There are definitely some corner cases that you'll need to iron out (left as an exercise for the reader), but this approach should work for you. The O(N^3) order should pass for small sequences. For larger sequences, you could look at memoization by traversing the sequence from right to left, but that's out of scope for this answer.
Here's a quick implementation in Python:
def get_sequences(l):
arithmetic_seq, geometric_seq = [], []
n = len(l)
for i in range(n):
for j in range(i+1, n):
arithmetic, geometric = [l[i], l[j]], [l[i], l[j]]
d = l[j] - l[i]
r = l[j] / l[i]
while (arithmetic[-1] + d) in l:
arithmetic.append(arithmetic[-1] + d)
while (geometric[-1] * r) in l:
geometric.append(int(geometric[-1] * r))
if len(arithmetic) > 2:
arithmetic_seq.append(arithmetic)
if len(geometric) > 2:
geometric_seq.append(geometric)
print("Sequences for ", l)
print("Arithmetic: ", arithmetic_seq)
print("Geometric: ", geometric_seq)
sequences = [[2, 3, 5, 6, 7, 9, 10, 14], [2, 3, 4, 8, 9, 16, 27, 32, 81], [2, 3, 4, 5, 8, 9, 16, 32]]
for seq in sequences:
get_sequences(seq)
This outputs:
Sequences for [2, 3, 5, 6, 7, 9, 10, 14]
Arithmetic: [[2, 6, 10, 14], [3, 5, 7, 9], [3, 6, 9], [5, 6, 7], [5, 7, 9], [6, 10, 14]]
Geometric: []
Sequences for [2, 3, 4, 8, 9, 16, 27, 32, 81]
Arithmetic: [[2, 3, 4], [2, 9, 16]]
Geometric: [[2, 4, 8, 16, 32], [2, 8, 32], [3, 9, 27, 81], [4, 8, 16, 32], [8, 16, 32], [9, 27, 81]]
Sequences for [2, 3, 4, 5, 8, 9, 16, 32]
Arithmetic: [[2, 3, 4, 5], [2, 5, 8], [2, 9, 16], [3, 4, 5]]
Geometric: [[2, 4, 8, 16, 32], [2, 8, 32], [4, 8, 16, 32], [8, 16, 32]]
So the algorithm is fairly correct. You need to debug your implementation, since I'm not sure about the language you've used for it.