[java] algoritmo de combinaçoes

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á
 
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:
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?
 
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:
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:
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:
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).
 
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
 
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;
 
CyberOps disse:
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;
Clicar para expandir...
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.
 
napalm disse:
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.
Clicar para expandir...

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.
 
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:
 
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
 
Inicie sessão ou registe-se para poder participar.
Back
Topo