1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

[java] algoritmo de combinaçoes

Discussão em 'Programação' iniciada por CyberOps, 3 de Dezembro de 2007. (Respostas: 12; Visualizações: 4908)

  1. CyberOps

    CyberOps I'm cool cuz I Fold

    Boas,

    indo directo ao assunto:

    tenho 2 hashtables

    Hashtable <String, ArrayList> disciplinasTurmasTPraticas = new Hashtable();
    Hashtable <String, ArrayList> disciplinasTurmasPraticas = new Hashtable();

    e esta é uma representacao +- de como os dados estao nas estruturas:

    disciplinasTurmasTPraticas:
    <cadeiraA, (turmatp1, turmatp2, turmatp3)>
    <cadeiraB, (turmatp1, turmatp2, turmatp3, turmatp4)>

    disciplinasTurmasPraticas:
    <cadeiraA, (turmap1, turmap2)>
    <cadeiraB, (turmap1, turmap2)>
    etc

    e basicamente o q preciso de fazer é as combinaçoes das varias turmas entre as varias cadeiras existentes nos arraylist's, tipo:

    cadeiraA - turmatp1
    cadeiraB - turmatp1
    cadeiraA - turmap1
    cadeiraB - turmap1

    cadeiraA - turmatp1
    cadeiraB - turmatp1
    cadeiraA - turmap1
    cadeiraB - turmap2
    .
    .
    cadeiraA - turmatp3
    cadeiraB - turmatp4
    cadeiraA - turmatp2
    cadeiraB - turmatp2

    ja ando de volta disto à umas horas e n consigo arranjar uma soluçao para isto, alguem tem alguma ideia de um algoritmo para o meu problema?

    obrigado desde já
     
  2. napalm

    napalm Power Member

    Vou deixar uma possível solução na minha opinião é bastante simples e que julgo não terás dificuldades em implementar em Java.
    No teu exemplo há 11 turmas divididas em 4 listas:
    Código:
    L - Lista
    S - Tamanho da Lista
    
    L1 = [1,2,3]; L2 = [1,2,3,4]; L3 = [1,2]; L4 = [1,2]
    S1 = 3; S2 = 4; S3 = 2; S4 = 2
    
    Se usarmos uma combinação ordeira em que a lista L4 é a primeira a variar, nota-se o seguinte padrão:
    L4 varia sempre, isto é de 1 em 1 iteração.
    L3 varia de 2 em 2 iterações (S4)
    L2 varia de 4 em 4 iterações (S4*S3)
    L1 varia de 16 em 16 iterações (S4*S3*S2)

    Assim ficamos com a seguinte informação extra:

    Código:
    V - Variação da Lista
    
    V1 = 16; V2 = 4; V3 = 2; V4 = 1
    
    Agora é uma questão de iterar S1*S2*S3*S4 vezes o que neste caso dá 48, começando no 0.

    Vamos fazer por exemplo a iteração 26:

    Código:
    L1: (26/V1)%S1 = 1; print L1[1] => 2
    L2: (26/V2)%S2 = 2; print L2[2] => 3
    L3: (26/V3)%S3 = 1; print L3[1] => 2
    L4: (26/V4)%S4 = 0; print L4[0] => 1
    
    Portanto 2 ciclos chegam para implementar esta solução. O exterior andará entre 0 e o produto do tamanho das listas (neste caso 48) e o interno percorrerá as listas, imprimindo os valores actuais de cada uma.
    Dada a tua organização de dados, sugiro-te que passes as tuas HashTables para Sets para ser mais simples iterar sobre todos de uma vez só. Algo do género:
    Código:
    Set turmas = disciplinasTurmasPraticas.entrySet().addAll(disciplinasTurmasTPraticas.entrySet());
    for(Map.Entry entry : turmas) {
      // nome da cadeira: entry.getKey()
      // lista de turmas : entry.getValue()
    }
    
    Espero que percebas a ideia :)
     
    Última edição: 3 de Dezembro de 2007
  3. CyberOps

    CyberOps I'm cool cuz I Fold

    antes de mais, fico muito grato pela tua ajuda.
    tenho mais uma duvida. seguindo o teu algoritmo, tou com alguma dificuldade em perceber como fazer a iteracao entre os diferentes arraylists, isto é, o numero de arraylists dentro das hashtables é irregular, logo a logica seria ter um ciclo for por cada arraylist, nao?
     
  4. napalm

    napalm Power Member

    Não. Se percebeste o que escrevi compreenderás que NUNCA vais precisar de iterar individualmente sobre cada ArrayList.
    O código em Java que pus no primeiro post junta as tuas HashTables num Set para simplificar iterares sobre todas as ArrayLists.
    Assim fica mais facil tirares os V de cada ArrayList para de seguida fazeres o algoritmo em si.
    De forma geral tem de ficar algo assim:

    Código:
    Set turmas = disciplinasTurmasPraticas.entrySet().addAll(disciplinasTurmasTPraticas.entrySet());
    int[] v = new int[turmas.size()];
    int combCount= 1;
    // calcular v e o número de combinações
    for(int i = turmas.size()-1; i >=0; i--) {
      v[i] = 1;
      combCount*= turmas.get(i).getValue().size();
      for(int j = turmas.size()-1; j > i; j++) {
        v[i] *= turmas.get(j).getValue().size();
      }
    }
    
    // output das combinações
    String course;
    ArrayList<String> classes;
    for(int i=0; i < combCount; i++) {
      for(int j = 0; j < turmas.size(); j++) {
        course = turmas.get(j).getKey();
        classes = turmas.get(j).getValue();
        System.out.println(course + " - " classes.get((i/v[j])%classes.size()));
      }
    }
    
    Não testei portanto é capaz de me ter escapado alguma coisa.
     
    Última edição: 3 de Dezembro de 2007
  5. napalm

    napalm Power Member

    Bom para fins de consulta deixo aqui um main funcional:

    Código:
    public static void main(String[] args) {
        Hashtable <String, ArrayList<String>> p,tp;
        p = new Hashtable<String, ArrayList<String>>();
        tp = new Hashtable<String, ArrayList<String>>();
        tp.put("cadeiraA", new ArrayList<String>(Arrays.asList("tpratica1","tpratica2","tpratica3")));
        tp.put("cadeiraB", new ArrayList<String>(Arrays.asList("tpratica1","tpratica2","tpratica3","tpratica4")));
        p.put("cadeiraA", new ArrayList<String>(Arrays.asList("pratica1","pratica2")));
        p.put("cadeiraB", new ArrayList<String>(Arrays.asList("pratica1","pratica2")));
        
        ArrayList<Map.Entry<String,ArrayList<String>>> turmas = new ArrayList<Map.Entry<String,ArrayList<String>>>(tp.entrySet());
        turmas.addAll(p.entrySet());
        
        int[] v = new int[turmas.size()];
        int combCount= 1;
        // calcular v e o número de combinações
        for(int i = turmas.size()-1; i >=0; i--) {
          v[i] = 1;
          combCount*= turmas.get(i).getValue().size();
          for(int j = turmas.size()-1; j > i; j--) {
            v[i] *= turmas.get(j).getValue().size();
          }
        }
    
        // output das combinações
        for(int i=0; i < combCount; i++) {
          for(int j = 0; j < turmas.size(); j++) {
            System.out.println(turmas.get(j).getKey() + " - " + turmas.get(j).getValue().get((i/v[j])%turmas.get(j).getValue().size()));
          }
          System.out.println("");
        }
    }
    
     
    Última edição: 3 de Dezembro de 2007
  6. CyberOps

    CyberOps I'm cool cuz I Fold

    epah, impecável. muito obrigado. se fores de coimbra terei todo o prazer em te pagar um copo.

    edit: ja agora, desconhecia essa cena dos sets. parece-me mto bom

    edit: ya, os v's das variaçoes, ja me tava a confundir. por acaso ta mto bem pensado ;)
     
    Última edição: 3 de Dezembro de 2007
  7. napalm

    napalm Power Member

    Lol obrigado mas sou de Lisboa :D Talvez um dia...

    O importante é que percebas o algoritmo, a implementação qualquer um a faz.
    O teu problema é um caso típico de quando se deve parar e voltar às bases, isto é, papel e lápis. A partir da altura em que comecei a ver alguns casos, notei logo o padrão das variações e a partir daí foram 5 mins até chegar à solução.

    Já agora, como nota extra, se reparares o turmas não é um Set mas sim uma ArrayList. A razão pq faço isto é que a interface Set não têm métodos de get(index).
     
  8. Viva,

    Java é algo recente para mim, por isso pedia-vos a V/ paciência.
    Pelo post, e tendo em conta que a questão vem de Coimbra, parece-me que o trabalho em mãos é o mesmo: - Um gerador de horários para alunos.

    Embora tenha percebido a explicação, não sei como adequar, não domino ainda estruturas de dados :( A minha abordagem na implementação foi ligeiramente diferente, recorrendo apenas a Hashtables. Neste momento estou perdido e pedia a V/ ajuda para retomar o "caminho".

    Tenho qq coisa do genero ...

    Hashtable <String, Disciplina> myDisciplinas; (em que a key é o nome da Disciplina)

    Na classe disciplina possuo mais 3 Hastables, uma para T, outra para TP e outra para P.

    Resumidamente eu preciso de gerar combinações das diversas disciplinas e respectivas turmas para poder gerar os horarios e guarda-las numa estrutura. Ou seja, ... D1T1, D1TP1, D1P1, D2T1, D2TP1, D2P1, ... Posteriormente a ideia seria passar essa estrutura com cada combinação encontrada, a um teste que validará a combinação de acordo com algumas condições.

    Imagino que seja uma solução idêntica, mas não sei como implementar apenas com hashtables.

    Obrigado pela ajuda
     
  9. CyberOps

    CyberOps I'm cool cuz I Fold

    eu ainda n sei mto bem o funcionamento das Maps, mas ja experimentaste fazer tipo:

    ArrayList<Map.Entry<String,<Map.Entry<String,ArrayList<String>>>>> turmas;
     
  10. napalm

    napalm Power Member

    Só um aviso rápido, se alguma vez chegarem a uma declaração desse género é o sinal óbvio que alguma abstracção é necessária ou a organização está pura e simplesmente mal feita e é ineficiente.

    buzina o algoritmo está todo aí. adapta as tuas estruturas ao mesmo ou vice-versa, mas mais do que isso não podes pedir.
    Já fui longe de mais com a minha ajuda ao CyberOps e não faço ideia se ele sequer percebeu a ideia e é capaz de a reproduzir sozinho.
     
  11. CyberOps

    CyberOps I'm cool cuz I Fold

    claro q percebi a ideia, pq alias se n perceber depois o professor quase de certeza q me lixa. é q ja tinha quase tudo implementado e so faltava mesmo o algoritmo, e graças a ti ja funca tudo, pq isto é bem mais do q gerar horarios. tb existe a parte de verificaçao de sobreposiçoes de aulas, calculo de restriçoes etc.

    agora relativamente ao buzina, quanto ao modo de como estas a implementar isso, de certeza q a ideia n é ter estruturas separadas pq ai la se vai o conceito de prog orientada a objectos, a n ser q n estejas a usar herança. se n tiveres de certeza q o prof n vai gostar.
     
  12. CrazyBomber

    CrazyBomber Power Member

    Não sei se podes fazer ou não, mas o que eu costumo fazer é ter estruturas diferentes para propósitos diferentes.
    Uma HashTable é óptima para ver se algo existe ou não. Mas é terrível para obter tudo o que lá está e organizar.
    Poderias usar outra estrutura, como uma Trie, por exemplo, para organizar isso. Se quiseres ainda melhor, fazes uma classe que engloba tudo isso, assim facilita imenso o trabaho.
    Se tiveres MESMO de fazer isso assim... então boa sorte :sad:
     
  13. Funciona!

    Caros,

    É só para agradecer e disponibilizar-me a pagar o almoço (o CyberOps paga a garrafa) ao Napalm assim que visites Coimbra. O problema colocado inicialmente, é ligeiramente mais complexo (percebi que sou colega de curso do CyberOps). Além de restrições que o problema inicial pedia, resolvi implementar algumas funcionalidades adicionais. Mas na prática o algoritmo acaba por ser o mesmo, basta contar as combinações, e adequar às estruturas. EXCELENTE DICA!

    Algo que acabo de perceber (chamem-me lammer ou newbie,...), é que o "segredo" da programação É realmente a representação do algortimo. Java é só um meio de implementar. ;)

    CrazyBomber, não percebi a dificuldade das Hashtable, estou a utilizar Hashtables e Vectores e "safei-me" na boa.

    Já agora fica a estatística:
    5 Disciplinas, 56 Turmas e 56 Turnos, 7620480 combinações, em 42 segundos num Macbook intel core 2 duo a 2,16G.

    +1 vez obrigado a todos.
    Buzi
     

Partilhar esta Página