0 Replies - 1225 Views - Last Post: 05 October 2012 - 10:43 AM Rate Topic: -----

#1 butterfly13  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 05-October 12

problem finding the longest increasing sequence in 2-D array

Posted 05 October 2012 - 10:43 AM

In this program the purpose is to find the longest increasing subsequence in a two-dimensional array using recursion, and. The input file is being read and the input is being placed in a ArrayList<String>.

I'm having problems checking the boundaries across the Map, since I have to check the top, bottom , left, right, and the top-left, top-right, bottom-left, bottom-right.

For my private getLongestSequence the idea is to

// Private recursive routine
ArrayList getLongestSequence( Position startingSquare )
{
ArrayList result = new ArrayList( );

for each Position p that is adjacent to startingSquare AND has a large value )
{
recursively compute the longest sequence starting at p
and if this sequence is longer than the one in result,
update result
}


add startingSquare to result
return result;
}




import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;

public class Main 
{
    private static ArrayList<String> list = new ArrayList();
    private static Map<Location, ArrayList<Location>> m = new HashMap();
    private static int column, rows;

    public static void main(String[] args) throws FileNotFoundException
    {
        File f = new File("numbers1.txt");
        Scanner scanner = new Scanner(f);  //reads the file
        
        while(scanner.hasNextLine())    //while the file has next line, add the string to the list
        {
            list.add(scanner.nextLine());
        }
        column = (new StringTokenizer(list.get(0))).countTokens(); //count the columns
        rows = list.size();  //count the rows
        ArrayList <Location> newList = makeArray(list); //create an arrayList
                                                         //with the Location of each token
     //   ArrayList<Location> test = getLongestSequence2(newList.get(22));
    }
    public ArrayList getLongestSequence(ArrayList<Location> l)
    {   
        for (Location loc: l)
            m.put(loc,getLongestSequence2(loc));
        
        Map.Entry<Location, ArrayList<Location>> maxEntry = null;

        for(Map.Entry<Location, ArrayList<Location>> entry : m.entrySet())
        {
        if (maxEntry == null || entry.getValue().size() > maxEntry.getValue().size())
            maxEntry = entry;
        }
        return maxEntry.getValue();
    }
    

// I have trouble checking for the boundaries to implement the recursion, 

    private static ArrayList<Location> getLongestSequence2(Location startL)
    {
        ArrayList<Location> result = new ArrayList();

        m.get(new Location (startL.getRow()-1,startL.getCol()-1,startL.getValue()));
        System.out.println("RRRRRRR " + startL);


        return result;    
    }



    private boolean boundaries(int row, int col)
    { 
        if((row>=0 && row< rows)&& (col>=0 && col<column))
           return true;
        return false;
    }
    private static ArrayList<Location> makeArray(ArrayList<String> l)
    {
        ArrayList<Location> arr =new ArrayList();
        StringTokenizer string ;
        Location loc;
        int c;
        for(int i=0; i<l.size(); i++)
        { 
            string = new  StringTokenizer(l.get(i));
            c = 0;
            while(string.hasMoreTokens())
        {
            loc = new Location(i,c,Integer.parseInt(string.nextToken()));
            arr.add(loc);
            c++;
           
        } 
        }
        
        return arr;
    }
    public Location checkBoundaries(Location square, int direction)
    {
        switch(direction)
        {
            case 0: return square.
        }
        return null;
    }
}



This is the Location Class

public class Location
{
    private int row, col, values;
    public Location(int r, int c,int v )
    {
        row = r;
        col = c;
        values = v;
    }
    public int getValue()
    {
        return values;
    }
    public int getRow()
    {
        return row;
    }
    public int getCol()
    {
        return col;
    }

    public String toString()
    {
        return row+"," + col;
    }
}





Is This A Good Question/Topic? 0
  • +

Page 1 of 1