wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Longest Arithmetic Progression
        
(Message started by: Aryabhatta on Jul 9^th, 2009, 10:56am)

Title: Longest Arithmetic Progression
Post by Aryabhatta on Jul 9^th, 2009, 10:56am

Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i₁ < i₂ < ... < i_k, such that

A[i₁], A[i₂], ..., A[i_k] forms an arithmetic progression, and k is the largest possible.

The sequence S₁, S₂, ..., S_k is called an arithmetic progression if

S_j+1 - S_j is a constant.

Note: just two elements can be considered to form an arithmetic progression.

Title: Re: Longest Arithmetic Progression
Post by Aryabhatta on Jul 9^th, 2009, 11:05am

Apparently this has appeared before: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1214319368

but I don't think anyone has come up with an O(n^2) solution, there.

Title: Re: Longest Arithmetic Progression
Post by towr on Jul 9^th, 2009, 11:37am

on 07/09/09 at 11:05:54, 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.

Title: Re: Longest Arithmetic Progression
Post by Aryabhatta on Jul 9^th, 2009, 1:45pm

on 07/09/09 at 11:37:52, 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...

Title: Re: Longest Arithmetic Progression
Post by towr on Jul 9^th, 2009, 2:21pm

on 07/09/09 at 13:45:58, 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(n²) )
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.

Title: Re: Longest Arithmetic Progression
Post by Aryabhatta on Jul 9^th, 2009, 3:48pm

on 07/09/09 at 14:21:40, towr wrote:

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.

Title: Re: Longest Arithmetic Progression
Post by spsyam1729 on Jul 10^th, 2009, 2:13am

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.

Title: Re: Longest Arithmetic Progression
Post by towr on Jul 10^th, 2009, 2:32am

on 07/09/09 at 15:48:34, 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 ;)

Title: Re: Longest Arithmetic Progression
Post by towr on Jul 10^th, 2009, 2:33am

on 07/10/09 at 02:13:35, 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(n²*d) where d is the maximum difference between two elements.

Title: Re: Longest Arithmetic Progression
Post by TenaliRaman on Jul 10^th, 2009, 8:26am

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

Title: Re: Longest Arithmetic Progression
Post by miletus on Jul 10^th, 2009, 11:49am

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;
}
}
}

Title: Re: Longest Arithmetic Progression
Post by TenaliRaman on Jul 11^th, 2009, 4:00am

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.

Title: Re: Longest Arithmetic Progression
Post by mistaken_id on Jul 12^th, 2009, 5:39pm

@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

Title: Re: Longest Arithmetic Progression
Post by mistaken_id on Jul 12^th, 2009, 5:54pm

on 07/11/09 at 04:00:32, TenaliRaman wrote:

The following is a Java code of the algorithm that I talked about earlier.

Code:

I think you need to remove duplicates for your algo to work correctly.

Title: Re: Longest Arithmetic Progression
Post by mistaken_id on Jul 12^th, 2009, 7:23pm

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.

Title: Re: Longest Arithmetic Progression
Post by Grimbal on Jul 13^th, 2009, 4:47am

I think miletus's solution doesn't require the array to be sorted. It should work fine.

Title: Re: Longest Arithmetic Progression
Post by Aryabhatta on Jul 13^th, 2009, 12:48pm

It is possible to do this without hashing/sorting.

Here is an algorithm: http://compgeom.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf

Title: Re: Longest Arithmetic Progression
Post by TenaliRaman on Jul 14^th, 2009, 1:14pm

on 07/12/09 at 17:39:05, 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