Страницы

Поиск по вопросам

понедельник, 15 октября 2018 г.

алгоритм Тайного Санты (SSA - Secret Santa Algorithm)

Готовлю новогоднюю вечеринку с друзьями, решили сыграть в тайного санту. Но до нового года не встречаемся, поэтому жеребьевка удаленно. Захотелось поиграться с кодом, вышел вот такой:
Secret Santa Algorithm
Цель - рандомно раскидать кто кому дарит подарок, так, чтобы не вышло ситуации, что человек дарит самому себе)
Смущает наличие костыля
if (j + 1 == guests.get(j))
Как думаете, что можно улучшить? Ожидается лаконичный, простой, не зависающий на большом количестве участников, выполняющий свою задачу алгоритм.
import java.util.*;
class Rextester {
public static void main(String args[]) { int GUESTS_NUMBER = 10; List guests = new ArrayList<>(); for (int i = 0; i < GUESTS_NUMBER;) { guests.add(++i); } boolean shuffled = false; outer: while (!shuffled) { Collections.shuffle(guests); shuffled = true; for (int j = 0; j < guests.size(); j++) { if (j + 1 == guests.get(j)) { shuffled = false; continue outer; } } } for (int j = 0; j < guests.size(); j++) System.out.println(j + 1 + " gives a gift to -> " + guests.get(j)); } }


Ответ

А почему бы не сделать так?
Перенумеровать участников, пусть их n Сгенерировать коллекцию { 1, 2, ..., n } и перетасовать её (Collections.shuffle) Участник в первым номером в полученной коллекции делает подарок второму участнику в коллекции, второй — третьему, третий — четвёртому, ..., последний — первому.
Алгоритм генерирует просто цикл длины n. Особенность — никогда не будут сгенерированы несколько коротких циклов, всегда только один длинный.

Комментариев нет:

Отправить комментарий