Versão atual:

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.

Versões(3):

Ver a versão formatada

Organizar uma lista de permutas entre caracteres

Comentário

new question