An overview,

Application scenario: Lottery

Drawing, can be manual drawing and timing drawing.

Raffles need to be as fair as possible.

The algorithm is divided into three parts:

  1. The Input and output

    Input parameters: list of participants and number of prizes

  2. The Process to deal with

    Select the winners

  3. The Output Output

    The winners


Second, the lottery algorithm

The algorithms that come to mind are:

  1. All the numberrandom
  2. Sampling algorithm
  3. shufflealgorithm
  4. Partitioning algorithm

(1) all numbersrandom

This is a violent method, which is also relatively easy to think of: a random selection of a number of people as winners.

But there is a conflict.

Simple steps are as follows:

  1. Load the participants in the activity into memory
  2. randomOne person is added to the winning list as the winnerresult
  3. If the winners repeat, continue to step 2

The code is as follows:

    /** * Get the list of winners **@paramNum Number of prizes *@paramParticipantIds *@returnList of winners */
    private List<String> getWinnerIds(final Integer num, final List<String> participantIds) {

        if (num >= participantIds.size()) {

            return participantIds;
        }

        Random random = new Random();
        
        Set<String> userIdSet = new HashSet<>(num);
        
        while (userIdSet.size() < num) {
            
            int index = random.nextInt(participantIds.size());
            
            String userId = participantIds.get(index);
            
            userIdSet.add(userId);
        }

        return participantIds.subList(0, num);
    }
Copy the code


(2) Sampling algorithm

When you think about the reservoir sampling algorithm you’ve learned before, the scene looks pretty much the same, picking a few from a batch of data.

However, sampling algorithm is mainly applied in big data scenarios, so it is just briefly mentioned here. If you are interested, please see the following link: https://crunch.apache.org/apidocs/0.15.0/org/apache/crunch/lib/Sample.html#weightedReservoirSample-org.apache.crunch.PC ollection-int-java.lang.Long-


(3)shufflealgorithm

It’s just random. I’m going to shuffle everything, and I’m going to pick the first few as the winners.

This method avoids conflicts.

As shown in figure:

Simple steps are as follows:

  1. Load the participants in the activity into memory
  2. I’m going to iterate, every timerandom, according to therandomThe numbers after that switch positions
  3. Take the first few people on the list as winners

The Shuffle can use java.util.collections directly from the JDK.

The code is as follows:

    /** * Get the list of winners **@paramNum Number of prizes *@paramParticipantIds *@returnList of winners */
    private List<String> getWinnerIds(final Integer num, final List<String> participantIds) {

        if (num >= participantIds.size()) {

            return participantIds;
        }

        Collections.shuffle(participantIds);

        return participantIds.subList(0, num);
    }
Copy the code


(4) Partitioning algorithm

Can it be any simpler without producing conflict?

Idea: Partition partition, each partition extracted one person

As shown in figure:

Simple steps are as follows:

  1. Load the participants in the activity into memory
  2. Count partitions (range), each partitionrandom, the subscript of the division winner =random + offsetOffset a
  3. According to the subscript to obtain the winning person

But a downside is that when num and the participants participantIds are not evenly divided, one of the regions causes an increase in winning.

The code is as follows:

    /** * Get the list of winners **@paramNum Number of prizes *@paramParticipantIds *@returnList of winners */
    private List<String> getWinnerIds(final Integer num, final List<String> participantIds) {

        if (num >= participantIds.size()) {

            return participantIds;
        }

        int offset = 0;

        int range = participantIds.size() / num;

        List<Integer> indexList = new ArrayList<>(num);

        Random rand = new Random();

        for (int i = 0; i < num; ++i) {

            int random = rand.nextInt(range);

            indexList.add(offset + random);

            offset += range;
        }

        return indexList.stream().map(participantIds::get).collect(Collectors.toList());
    }
Copy the code

PS: Compared with the other several, more like this, high operability and simple.