1. java
  2. android
  3. c#
  4. .net
  5. javascript
  6. php
  7. jquery
  8. html
  9. sql

Organizar uma lista de permutas entre caracteres

Tenho uma lista contendo vários objetos da classe Caractere, onde cada caractere pode escolher de um até três destinos possíveis, a troca pode ocorrer caso tenha alguém que deseja o local atual do mesmo ou que através de outra permuta uma vaga seja liberada, sendo que é seguido a ordem da lista por prioridade.

  1. "A", ["B", "Y", "Z"];
    1. "B", ["C", "X"];
    2. "C", ["A"];
    3. "T", ["B"];
    4. "H", ["B", "K", "Z"];
    5. "K", ["H", "A"];
    6. "M", ["U", "F"];
    7. "O", ["G"];
    8. "E", ["V", "C"];
    9. "Z", ["A"].

O resultado esperado para os itens da lista:

  1. A conseguiu para B.
    1. B conseguiu para C.
    2. C conseguiu para A.
    3. T não conseguiu ir pra nenhum lugar.
    4. H conseguiu para K.
    5. K conseguiu para H.
    6. M não conseguiu ir pra nenhum lugar.
    7. O não conseguiu ir pra nenhum lugar.
    8. E não conseguiu ir pra nenhum lugar.
    9. Z não conseguiu ir pra nenhum lugar.

Leitura inicial: "A" procura por outros Caracteres que possuem locais atuais que sejam "B", "Y" ou "Z", o segundo item possui o local atual "B", porém ele não deseja ir para "A", e sim para "C" ou "X", verifico então "B", a primeira opção é "C", o terceiro item possui o local atual "C" e deseja ir para "A", ou seja, pode haver uma troca de locais entre os três. ...

A lista segue a ordem de prioridade e não por eficiência, o que ocorrer primeiro "ganha".

public class Caractere {
   private String localAtual;
   private String[] destinos;

   ...
}

A lista é extensa e consegui diminuí-la removendo os Caracteres que não tinham locais atuais e destinos possíveis.

Porém estou com dificuldades para rastrear as combinações, pois como no exemplo que citei:

caso uma permuta não ocorra as outras não serão possíveis.

Existe alguma fórmula matemática pra resolver esse problema ou como poderia fazer essa checagem?

Obs: Não é nenhum trabalho/tarefa de faculdade/curso, não quero um código e sim uma ideia de como implementar um algoritmo.

  1. Você vai ver essas setas em qualquer página de pergunta. Com elas, você pode dizer se uma pergunta ou uma resposta foram relevantes ou não.
  2. Edite sua pergunta ou resposta caso queira alterar ou adicionar detalhes.
  3. Caso haja alguma dúvida sobre a pergunta, adicione um comentário. O espaço de respostas deve ser utilizado apenas para responder a pergunta.
  4. Se o autor da pergunta marcar uma resposta como solucionada, esta marca aparecerá.
  5. Clique aqui para mais detalhes sobre o funcionamento do GUJ!

0 resposta

Não é a resposta que estava procurando? Procure outras perguntas com as tags java ou faça a sua própria pergunta.