Bom, como trabalho da faculdade, tenho que criar um algoritmo que, dado certo arquivo com x números, seja capaz de verificar qual a maior sequência de números que, em base 6, respeitem as as seguintes regras:
- A sequência deve ser crescente
- De um número para outro da sequência, somente um dígito pode mudar
- Todos os números da sequência tem que ter o mesmo número de digitos (15-->10015 não é válido)
Um exemplo seria:
O arquivo contém os números 782, 229, 446, 527, 874, 19, 829, 70, 830, 992, 430 e 649.
Ou seja, em base 6: 3342, 1021, 2022, 2235, 4014, 31, 3501, 154, 3502, 4332, 1554 e 3001.
Portanto, a maior sequência respeitando essas regras seria: 649, 829 e 830, que corresponde a 3001, 3501 e 3502 em base 6.
Certo, os arquivos não são assim tão simples, há arquivos que chegam a ter até 100.000 números, portanto, criei um grafo. Eu tentei tanto com matriz como com lista de adjacências. Adicionar os vértices e as arestas (ou seja, quais são os números que respeitam as regras para um número x) não foi um problema, meu problema é caminhar no grafo, pois pesquisando na internet só achei caminhamento mínimo, mas o que eu preciso é: achar o maior caminho.
Tentei com DFS mas o resultado não é o que eu quero.
Meu código é o seguinte:
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;
private ArrayList<Vertice> lst = new ArrayList<Vertice>();
public Vertice(String item) {
this.item = item;
}
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 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){
graph.addEdge(a,numero);
}
}
return true;
}
public void DFS(Vertice a){
a.Visitado=true;
for(int i=0;i<a.lst.size();i++){
Vertice b=a.lst.get(i);
if(!b.Visitado){
DFS(b);
}
}
}
public static void main(String[] args) throws FileNotFoundException
{
ArrayList<Integer> numeros=new ArrayList<Integer>();
criaArray(numeros,"/home/geovane/Documentos/CC/ALPROII/teste5000b");
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);
}
}
}