Объединение группировки в двудольные графы?

Question

Я пытаюсь найти хорошее (и быстрое) решение следующей проблемы:

У меня есть две модели, с которыми я работаю, назовем их игроками и командами. Игрок может быть в нескольких командах, а команда может иметь несколько игроков). Я работаю над созданием элемента пользовательского интерфейса в форме, которая позволяет пользователю выбирать несколько команд (флажки). Когда пользователь выбирает (или отменяет выбор) команды, я бы хотел отобразить команды, сгруппированные игроками.

Так для примера:

1. Если выбранные команды нет игроков, которые пересекаются, каждая команда будет иметь свой собственный раздел.

2. Если пользователь выбирает две команды и у них одни и те же игроки, будет один раздел, содержащий имена двух команд и всех игроков.

3. Если у TEAM_A есть игроки [1, 2, 4, 5] и TEAM_B, игроки [1, 3, 5, 6]. Там бы следующие разделы: SECTION_X = [TEAM_A, TEAM_B, 1, 5], SECTION_Y = [TEAM_A, 2, 3], Раздел _z = [TEAM_B, 3, 5]

Я надеюсь, что это ясно , По сути, я хочу найти команды, которые есть у всех игроков и группы. Я думал, может быть, есть способ сделать это, проводя двудольный граф? Не совсем точно, как бы и я мог бы переусердствовать. Я надеялся сделать это, создав некоторую структуру данных на сервере и используя ее на клиенте. Я хотел бы услышать ваши предложения, и я ценю любую помощь, которую вы можете дать!

Answer 1

Одним из решений является, чтобы каждый игрок обертка отслеживать выбранные команды, которые он находится на

class PlayerWrapper { 
    Player player; 
    TeamList teamList; 
} 

class TeamList { 
    private List<Team> teams; 
    int hashValue = // hash value derived from teams list 
    void add(Team team) { 
    teams.add(team); 
    hashValue = // update hash value 
    } 
} 

Затем сохранить хэш-таблицу игроков наборов, и хэш-таблица игроков оберток

HashTable<TeamList, Set<Player>> playerSets 
HashTable<Player, PlayerWrapper> playerWrappers 

Когда пользователь выбирает новую команду, итерацию через игроков команды и извлечение оберток игрока из playerWrappers. Для каждой обертки игрока извлеките Set<Player> от playerSets и удалите игрока из набора, затем добавьте новую команду в обертки TeamList, извлеките Set<Player> от playerSets и добавьте игрока в комплект.

void updatePlayer(Team team, Player player) { 
    PlayerWrapper wrapper = playerWrappers.get(player); 
    Set<Player> set = playerSets.get(wrapper.teamList); 
    set.remove(player); 
    wrapper.teamList.add(team); 
    set = playerSets.get(wrapper.teamList); 
    set.add(player); 
} 

Предполагая, что вы используете хэш-наборы для Set<Player> это должно в среднем требуют постоянного времени для обработки игрока Команды. Отмена выбора команды будет действовать одинаково, за исключением того, что вы удалите команду из wrapper.teamList вместо ее добавления, и у вас будет линейный поиск по времени через TeamList, чтобы найти и удалить команду. Использование List в TeamList предполагает, что пользовательский интерфейс предотвратит дублирование команд; будьте осторожны, используя вместо этого Set, потому что может быть труднее убедиться, что у двух оберток TeamLists будет одинаковый hashValue (т. е. вам может потребоваться предпринять шаги, чтобы гарантировать, что оба обертки TeamLists вернут свои команды в том же порядке - что-то вроде a java LinkedHashSet сделал бы трюк)