Author |
Topic: Longest Arithmetic Progression (Read 8004 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Longest Arithmetic Progression
« on: Jul 9th, 2009, 10:56am » |
 Quote  Modify
|
Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 < i2 < ... < ik, such that
A[i1], A[i2], ..., A[ik] forms an arithmetic progression, and k is the largest possible.
The sequence S1, S2, ..., Sk is called an arithmetic progression if
Sj+1 - Sj is a constant.
Note: just two elements can be considered to form an arithmetic progression.
|
| « Last Edit: Jul 9th, 2009, 10:58am by Aryabhatta » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Longest Arithmetic Progression
« Reply #2 on: Jul 9th, 2009, 11:37am » |
Quote Modify
|
on Jul 9th, 2009, 11:05am, Aryabhatta wrote:| but I don't think anyone has come up with an O(n^2) solution, there. |
|
I think I might have. Although I never worked it out in an algorithm.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Longest Arithmetic Progression
« Reply #3 on: Jul 9th, 2009, 1:45pm » |
Quote Modify
|
on Jul 9th, 2009, 11:37am, towr wrote:
I think I might have. Although I never worked it out in an algorithm.
|
|
It seems like you reduced it to finding longest path in graphs. Is that accurate? Finding longest paths would be hard problem as we can solve Hamiltonian path with that...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Longest Arithmetic Progression
« Reply #4 on: Jul 9th, 2009, 2:21pm » |
Quote Modify
|
on Jul 9th, 2009, 1:45pm, Aryabhatta wrote:| It seems like you reduced it to finding longest path in graphs. Is that accurate? Finding longest paths would be hard problem as we can solve Hamiltonian path with that... |
|
But it's not a general graph. In fact, only nodes that are in arithmetic progression are even in the same connected component of the graph for a given distance.
You can take all pairs of numbers; sort them in different bins depending on the difference (using, for example, a hash_map to keep this O(n2) )
Then for each collection of pairs of nodes, build a "graph", which consists of disjointed linked lists.
Find the longest list.
And that's it.
You could do it in just one big graph of course, as long as distinct difference-edges have a different 'colour' or something.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Longest Arithmetic Progression
« Reply #5 on: Jul 9th, 2009, 3:48pm » |
Quote Modify
|
on Jul 9th, 2009, 2:21pm, towr wrote:
But it's not a general graph. In fact, only nodes that are in arithmetic progression are even in the same connected component of the graph for a given distance.
You can take all pairs of numbers; sort them in different bins depending on the difference (using, for example, a hash_map to keep this O(n2) )
Then for each collection of pairs of nodes, build a "graph", which consists of disjointed linked lists.
Find the longest list.
And that's it.
You could do it in just one big graph of course, as long as distinct difference-edges have a different 'colour' or something. |
|
Using hash is still potentially worse than O(n^2) in worst case.
There are algorithms which guarantee O(n^2) time.
Anyway, what you have is acceptable. Sorry I didn't think about what you wrote carefully enough.
|
|
IP Logged |
|
|
|
spsyam1729
Newbie
Posts: 1
|
|
Re: Longest Arithmetic Progression
« Reply #6 on: Jul 10th, 2009, 2:13am » |
Quote Modify
|
I guess we can do straight Dynamic Programming with O(N^2) space, keeping all the current lengths we can solve this in O(N^2) time
DP[i,j] will store length of AP from char 1 to i with j as the differential factor.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Longest Arithmetic Progression
« Reply #7 on: Jul 10th, 2009, 2:32am » |
Quote Modify
|
on Jul 9th, 2009, 3:48pm, Aryabhatta wrote:| Anyway, what you have is acceptable. Sorry I didn't think about what you wrote carefully enough. |
|
Oh, don't worry about it, I usually don't think too carefully about what I write either 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Longest Arithmetic Progression
« Reply #8 on: Jul 10th, 2009, 2:33am » |
Quote Modify
|
on Jul 10th, 2009, 2:13am, spsyam1729 wrote:| DP[i,j] will store length of AP from char 1 to i with j as the differential factor. |
|
What about AP's that don't start at 1?
Seems to me you need O(n2*d) where d is the maximum difference between two elements.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Longest Arithmetic Progression
« Reply #9 on: Jul 10th, 2009, 8:26am » |
Quote Modify
|
We can use the following property here :
If ..., a_{i+1}, a_i, ..., a_3, a_2, a_1, b, c_1, c_2, ..., c_i, c_{i+1}, ... is an A.P., then
a_i + c_i = 2b
Algo would be something like :
S = sort(A) .. where A is the given array
Consider each element in S as 'b' (as defined above) and move outward (on both sides) and keep finding all the A.P elements with b as center.
One should be able to create a list 3-tuples and their A.P constants. Then, simply grouping by A.P constants and chaining these 3-tuples in each group should give the chain as well as their lengths. Simply get the one with max length from then on.
It should be possible to do this in O(n^2), but I will try to check it properly later on.
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
miletus
Newbie
Posts: 4
|
|
Re: Longest Arithmetic Progression
« Reply #10 on: Jul 10th, 2009, 11:49am » |
Quote Modify
|
If we don't care about memory, we can use hash map + dp to achieve O(N^2)
something like this
Code:
const int N = 8;
int max_len = 1;
int a[N] = {3, 6, 7, 8, 11, 12, 14, 15};
// maps[i][diff] is the maximal length of the progression that
// ends at position i, with progression difference diff.
map<int, int> maps[N];
// Nested loop takes O(N^2)
for (int i = 1; i < N; i++) {
for (int j = 0; j < i; j++) {
// Using a real hash map implementaion will makes the following
// block O(1) while the STL map is implemented by RB-tree.
int diff = a[i] - a[j];
map<int, int>::const_iterator it = maps[j].find(diff);
// Simple DP updates
if (it == maps[j].end()) {
maps[i][diff] = 2;
} else {
int new_len = maps[j][diff] + 1;
maps[i][diff] = new_len;
max_len = new_len > max_len ? new_len : max_len;
}
}
}
|
|
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Longest Arithmetic Progression
« Reply #11 on: Jul 11th, 2009, 4:00am » |
Quote Modify
|
The following is a Java code of the algorithm that I talked about earlier.
Code:
import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public class LongestArithmeticProgression {
public static void main(String[] args) {
Map<Point, List<Integer>> apMap = new HashMap<Point, List<Integer>>();
int[] A = {31,1,100,13,125,6,32,12,254,365,112,67,33,34,35,43,57,28,19,36};
Arrays.sort(A);
int[] S = A;
for (int i = 0; i < S.length; i++) {
int j = i - 1;
int k = i + 1;
int b = S[i];
while (j >= 0 && k < S.length) {
int a_i = S[j];
int c_i = S[k];
if (a_i + c_i < 2*b) {
k++;
} else if (a_i + c_i > 2*b) {
j--;
} else {
j--;
k++;
Point ab = new Point(a_i, b);
List<Integer> abc = apMap.remove(ab);
if (abc == null) {
abc = new ArrayList<Integer>(S.length);
abc.add(a_i);
abc.add(b);
abc.add(c_i);
Point bc = new Point(b, c_i);
apMap.put(bc, abc);
} else {
abc.add(c_i);
int size = abc.size();
apMap.put(new Point(abc.get(size-2), c_i), abc);
}
}
}
}
int max = 0;
List<Integer> maxList = null;
for (Map.Entry<Point, List<Integer>> entry : apMap.entrySet()) {
List<Integer> entryList = entry.getValue();
if (entryList.size() >= max) {
max = entryList.size();
maxList = entryList;
}
}
System.out.println(maxList);
}
}
|
|
-- AI
P.S. -> I realize that I have done the tuple chaining slightly differently than what I had mentioned earlier. Here, I am chaining the tuples on the fly, whereas, earlier I mentioned about chaining the tuples after generating them. Both are valid as such.
|
| « Last Edit: Jul 11th, 2009, 4:15am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
mistaken_id
Junior Member
Posts: 132
|
|
Re: Longest Arithmetic Progression
« Reply #12 on: Jul 12th, 2009, 5:39pm » |
Quote Modify
|
@TenaliRaman or anyone:
If I give {3,4,5,2,1} as input to the algo what should the output be?
a) 3,4,5 or
b) 1,2,3,4,5
|
|
IP Logged |
|
|
|
mistaken_id
Junior Member
Posts: 132
|
|
Re: Longest Arithmetic Progression
« Reply #13 on: Jul 12th, 2009, 5:54pm » |
Quote Modify
|
on Jul 11th, 2009, 4:00am, TenaliRaman wrote:The following is a Java code of the algorithm that I talked about earlier.
Code:
import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public class LongestArithmeticProgression {
public static void main(String[] args) {
Map<Point, List<Integer>> apMap = new HashMap<Point, List<Integer>>();
int[] A = {31,1,100,13,125,6,32,12,254,365,112,67,33,34,35,43,57,28,19,36};
Arrays.sort(A);
int[] S = A;
for (int i = 0; i < S.length; i++) {
int j = i - 1;
int k = i + 1;
int b = S[i];
while (j >= 0 && k < S.length) {
int a_i = S[j];
int c_i = S[k];
if (a_i + c_i < 2*b) {
k++;
} else if (a_i + c_i > 2*b) {
j--;
} else {
j--;
k++;
Point ab = new Point(a_i, b);
List<Integer> abc = apMap.remove(ab);
if (abc == null) {
abc = new ArrayList<Integer>(S.length);
abc.add(a_i);
abc.add(b);
abc.add(c_i);
Point bc = new Point(b, c_i);
apMap.put(bc, abc);
} else {
abc.add(c_i);
int size = abc.size();
apMap.put(new Point(abc.get(size-2), c_i), abc);
}
}
}
}
int max = 0;
List<Integer> maxList = null;
for (Map.Entry<Point, List<Integer>> entry : apMap.entrySet()) {
List<Integer> entryList = entry.getValue();
if (entryList.size() >= max) {
max = entryList.size();
maxList = entryList;
}
}
System.out.println(maxList);
}
}
|
|
-- AI
P.S. -> I realize that I have done the tuple chaining slightly differently than what I had mentioned earlier. Here, I am chaining the tuples on the fly, whereas, earlier I mentioned about chaining the tuples after generating them. Both are valid as such. |
|
I think you need to remove duplicates for your algo to work correctly.
|
|
IP Logged |
|
|
|
mistaken_id
Junior Member
Posts: 132
|
|
Re: Longest Arithmetic Progression
« Reply #14 on: Jul 12th, 2009, 7:23pm » |
Quote Modify
|
Can we still find a O(n**2) when we want to find longest AP sequence in the original array but not in the sorted array.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Longest Arithmetic Progression
« Reply #15 on: Jul 13th, 2009, 4:47am » |
Quote Modify
|
I think miletus's solution doesn't require the array to be sorted. It should work fine.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Longest Arithmetic Progression
« Reply #17 on: Jul 14th, 2009, 1:14pm » |
Quote Modify
|
on Jul 12th, 2009, 5:39pm, mistaken_id wrote:@TenaliRaman or anyone:
If I give {3,4,5,2,1} as input to the algo what should the output be?
a) 3,4,5 or
b) 1,2,3,4,5 |
|
I innately assumed (b) as the answer, but if you remove the sorting step from my code, I believe it should give you (a) as well.
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print