I am preparing a New Year's party with friends, we decided to play a secret Santa. But before the new year we are not meeting, so the draw is remote. I wanted to play around with the code, it came out like this:

Secret santa algorithm

The goal is to randomly scatter someone to whom a gift is presented, so that the situation that a person gives to himself does not come out)

Embarrassed by the presence of a crutch

if (j + 1 == guests.get(j))

What do you think can be improved? A concise, simple, not hanging on a large number of participants, performing its task algorithm is expected.

 import java.util.*; class Rextester { public static void main(String args[]) { int GUESTS_NUMBER = 10; List<Integer> 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)); } }

    2 answers 2

    Why not do it?

    1. Renumber the participants, let them be n .
    2. Generate collection { 1, 2, ..., n } and shuffle it ( Collections.shuffle )
    3. The participant in the first number in the received collection makes a gift to the second participant in the collection, the second to the third, the third to the fourth, ..., the last to the first.

    The algorithm simply generates a cycle of length n . Feature - several short cycles will never be generated, always only one long.

    • If you can clarify, and what is the disadvantage of the lack? - Kromster
    • @Kromster: Well, not all suitable permutations are generated, but only a part. - VladD
    • And what is "not all suitable permutations, but only a part"? - Kromster
    • @Kromster: Well, let's say we have 4 members. The algorithm will never say "let the first give to the second, second to the first, third to the fourth, and the fourth to the third." Because it always generates a long cycle. - VladD
    • 2
      @Kromster: I don't know. I honestly told Santa about the features of the solution, but it’s not for me to consider this feature a disadvantage or not. - VladD

    In your algorithm, you can make a check in the loop, if we give to ourselves, we change with the next one in the queue, if the last is with the first. Here is my option:

     public class Test { public static void main(String args[]) { int SANTA_NUMBERS = 10; List<Integer> santaList = new ArrayList<>(); for (int i = 0; i < SANTA_NUMBERS; ) { santaList.add(++i); } List<Integer> guests = new ArrayList<>(santaList); Collections.shuffle(guests); //в этом цикле проверяем for (int i = 0; i < santaList.size(); i++) { if (santaList.get(i) == guests.get(i)) { if (i + 1 < santaList.size()){ Integer receiver = guests.get(i + 1); guests.set(i + 1, guests.get(i)); guests.set(i , receiver); }else { Integer receiver = guests.get(1); guests.set(1, guests.get(i)); guests.set(i , receiver); } } } for (int j = 0; j < santaList.size(); j++) System.out.println(santaList.get(j) + " gives a gift to -> " + guests.get(j)); } }