Graphs: greater path

Since we can not mix numbers of different sizes, the first step is to separate the input into sets containing numbers of the same length: in case {31}, {154}, {3342, 1021, 2022, 2235, 4014 , 3501, 3502, 4332, 1554, 3001); the response must necessarily be equal to the response of some of these subsets; I'll use it to illustrate the algorithm, not its example, but the set {101, 322, 325, 342, 345, 422, 501, 502, 522} (in base 6, of course).

Ihavelistedthenumbersalreadyinascendingordertomakethefirstquestionquiteeasy:whatisthelargestsequencethataddressestheproblemconditionsstartingat522?Obviouslyitisthe{522}sequence,sincethestringrestrictionisincreasing,sowedonothaveanywheretogoafter522.

Mysecondquestion:whatisthebiggestsequencestartingin502?Obviouslytheansweris{502,522},since{502}canonlygoto{522}.Similarly,itiseasytoseethatthelargestsequencestartingat501is{501,502,522},etc.

Ifyouarelookingattheexamplenumbersindescendingorder,youdonothavetothinktoohard-youwillalwayshavezerooranalternative-untilyougetto322.

(The gray knots are we have already considered, the number in parentheses is the size of the largest path that starts at that node.) The red knot - 322 is the knot we are considering now. >

Now we have four possibilities to continue the sequence: {322, 522, ...}, {322, 422, ...}, {322, 342, ...} {322, 325, ...}. Which one is bigger? Now, we know that with the exception of the sequence that begins in 522 (which can only have one term), the other choices allow to continue for two more numbers. So the largest sequence starting at 322 has 1 + 2 = 3 terms.

After that, it's easy to see that the largest (and only) sequence starting at 101 has 4 terms, so it's the solution to the problem (since if you look at all nodes in the graph, some of them are 4).

In short, the idea of the algorithm is this:

para cada número n, em ordem decrescente:
    maior_sequência[n] := 1;  // sempre posso fazer a sequência unitária {n}
    para cada número “vizinho” v seguindo as regras do problema:
        // posso fazer a sequência {n, v, …}
        maior_sequência[n] := máximo(maior_sequência[n], 1 + maior_sequência[v]);        

retorne máximo(maior_sequência);

Does it make sense? This idea works because finding the largest sequence that starts in a given number depends only on the number: it does not matter how I got in n so far; the path to n never affects the path I can follow after n . This is only possible because the graph is acyclic - I can never go back due to the restriction of the numbers being increasing.

If I did not have this restriction, a valid response to this example would be eg {101, 501, 502, 522, 422, 322, 342, 345, 325}, which passes through all numbers, but this problem is much more difficult, since then I would have to somehow save the numbers I have already visited. In this example, if I did not do this, I could have the infinite sequence, 342, 342, 345, 325, 322 , 342, 345, 325, 322 , ...}.

This idea is an example of a much more general idea called dynamic programming ; the Wikipedia link seems to confuse more than clarifies, but I did not find much material in Portuguese. The Programming Marathon wiki at UFMG has more problems and some references in English if you want to study ideas.

    

Just to update and help someone who by chance wants the code resolved.

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class DirectedGraphList
{
private class Vertice
{
    private String item;
    private boolean Visitado;
    int maiorSequencia;
    Vertice proximo;
    private ArrayList<Vertice> lst = new ArrayList<Vertice>();

    public Vertice(String item) {
        this.item = item;
        Visitado=false;
        maiorSequencia=0;
        lst=new ArrayList<Vertice>();
        proximo=null;
    }
    public String getItem() {
        return this.item;
    }
    public void setItem(String item) {
        this.item = item;
    }
    public void addAdjacent(Vertice v) {
        if (!lst.contains(v))
            lst.add(v);
    }
    public ArrayList<Vertice> getAdjacents() {
        return lst;
    }
    public Vertice getAdjacent(int i) {
        Vertice res = null;
        if ((i >= 0) && (i < lst.size()))
            res = lst.get(i);
        return res;
    }
    public int getDegree(){
        return lst.size(); 
    }
}

private ArrayList<Vertice> vert;

public DirectedGraphList() {
    vert = new ArrayList<Vertice>();
}

private Vertice searchVerticeRef(String item)
{
    Vertice res = null;
    int i;

    for (i = 0; ((i < vert.size()) && !vert.get(i).getItem().equals(item)); i++);

    if (i < vert.size())
        res = vert.get(i);

    return res;
}

public void addVertice(String item)
{
    if (searchVerticeRef(item) == null) 
    {
        Vertice novo = new Vertice(item);
        vert.add(novo);
    }
}

public void addEdge(String strOrig, String strDest)
{
    Vertice vAux1 = searchVerticeRef(strOrig);
    Vertice vAux2 = searchVerticeRef(strDest);

    if (vAux1 == null)
        throw new IllegalArgumentException("Aresta origem invalida: " + strOrig);
    else if (vAux2 == null)
        throw new IllegalArgumentException("Aresta destino invalida: " + strDest);
    else
    {
        vAux1.addAdjacent(vAux2);
    }
}

public int getNumVertices() {
    return vert.size();
}

public int getDegree(String vertice)
{
    int i, j, c = 0;
    Vertice v = searchVerticeRef(vertice);
    if (v != null)
    {
        // grau de saida
        c += v.getDegree();

        // grau de entrada
        for (i = 0; i < vert.size(); i++)
        {
            if (!vert.get(i).getItem().equals(vertice))
            {
                for (j = 0; j < vert.get(i).getDegree(); j++)
                {
                    if (vert.get(i).getAdjacent(j).getItem().equals(vertice))
                        c++;
                }                   
            }
        }
    }
    return c;
}

public ArrayList<String> getAllAdjacents(String vertice)
{
    ArrayList<String> res = null;
    Vertice v = searchVerticeRef(vertice);
    if (v != null)
    {
        res = new ArrayList<String>();
        for (int j = 0; j < v.getDegree(); j++)
            res.add(v.getAdjacent(j).getItem());
    }
    return res;
}

public ArrayList<String> getSources()
{
    ArrayList<String> res = new ArrayList<String>();
    boolean checked;
    String vertice;

    for (int k=0; k<vert.size(); k++)
    {
        vertice = vert.get(k).getItem();

        checked = false;
        for (int i=0; i<vert.size(); i++)
        {
            for (int j=0; j<vert.get(i).getDegree(); j++)
            {
                if (vert.get(i).getAdjacent(j).getItem().equals(vertice))
                {
                    checked = true;
                    break;
                }
            }
        }

        if (!checked)
            res.add(vertice);
    }
    return res;
}

public ArrayList<String> getSinks()
{
    ArrayList<String> res = new ArrayList<String>();

    for (int i=0; i<vert.size(); i++)
    {
        if (vert.get(i).getAdjacents().isEmpty())
            res.add(vert.get(i).getItem());
    }
    return res;
}

public void showInfo()
{
    System.out.print("V = { ");
    for (int i = 0; i < vert.size()-1; i++)
        System.out.printf("%s, ", vert.get(i).getItem());
    System.out.printf("%s }\n", vert.get(vert.size()-1).getItem());

    ArrayList<String> arestas = new ArrayList<String>();
    for (int i = 0; i < vert.size(); i++)
        for (int j = 0; j < vert.get(i).lst.size(); j++)
            arestas.add(String.format("(%s, %s)", vert.get(i).getItem(), vert.get(i).getAdjacent(j).getItem()));

    System.out.print("E = {\n");
    if (!arestas.isEmpty()) {
        System.out.printf("      %s", arestas.get(0));

        for (int i = 1; i < arestas.size(); i++)
            System.out.printf(",\n      %s", arestas.get(i));
    }
    System.out.println("\n    }");
}
public static void criaArray(ArrayList<Integer> a,String nome) throws FileNotFoundException{
    try{
        FileReader ler= new FileReader(nome);
        BufferedReader arq=new BufferedReader(ler);
        int parsedStr;
        String str=arq.readLine();
        while(str!=null){
            parsedStr=Integer.parseInt(str);
            a.add(parsedStr);
            str=arq.readLine();
        }
    }
    catch(IOException e){
        System.out.println("Erro na abertura do arquivo: "+
                e.getMessage());
    }
}
public static int diferente(String a,String b){
    int diferentes=0;
    if(a.length()==b.length()){
        for(int i=0;i<a.length();i++){
            if(a.charAt(i)!=b.charAt(i))
                diferentes++;
        }
    }
    else 
        diferentes=2;
    return diferentes;
}
public static boolean maior(String str1,String str2){
    int aux=Integer.parseInt(str1, 6);
    int aux1=Integer.parseInt(str2, 6);
    if(aux>aux1)
        return true;
    else return false;
}

public static boolean possibilidades(DirectedGraphList graph,String a,ArrayList<Integer> array){
    int diferentes=0;
    for(int i=0;i<array.size();i++){
        String numero=Integer.toString(array.get(i),6);
        diferentes=diferente(numero,a);
        if(diferentes==1 && maior(numero,a)){
            graph.addEdge(a,numero);
        }   
    }
    return true;
}

public void printaSequencia(Vertice a){
    System.out.println(a.item);
    Vertice atual=a;
    while(atual.proximo!=null){
        atual=atual.proximo;
        System.out.println(atual.item);
    }
}

public void atribuiTamanhoSequencia(){
    for(int i=vert.size()-1;i>=0;i--){
        vert.get(i).maiorSequencia=1;
        for(int k=vert.get(i).lst.size()-1;k>=0;k--){
            if (vert.get(i).lst.get(k).maiorSequencia+1 > vert.get(i).maiorSequencia){
                vert.get(i).maiorSequencia=vert.get(i).lst.get(k).maiorSequencia+1;
                vert.get(i).proximo=vert.get(i).lst.get(k);
            }
        }
    }

}
public Vertice getVerticeInicial(){
    Vertice aux=null;
    int tamanho=0;
    for(int i=0;i<vert.size();i++){
        if(vert.get(i).maiorSequencia>tamanho){
            aux=vert.get(i);
            tamanho=vert.get(i).maiorSequencia;
        }
    }
    return aux;
}


public static void main(String[] args) throws FileNotFoundException
{
    ArrayList<Integer> numeros=new ArrayList<Integer>();
    criaArray(numeros,"/home/geovane/Documentos/CC/ALPROII/test100000a");
    DirectedGraphList g = new DirectedGraphList();
    HeapSort.heapsort(numeros);
    for(int j=0;j<numeros.size();j++){
    g.addVertice(Integer.toString(numeros.get(j),6));
    }
    for(int i=0;i<numeros.size();i++){
        String numer=Integer.toString(numeros.get(i), 6);
        possibilidades(g,numer,numeros);
    }
    g.atribuiTamanhoSequencia();
    Vertice inicial=g.getVerticeInicial();
    g.printaSequencia(inicial);
}
}

Problem solved !! Thanks @ctgPi