Back
Featured image of post Shuffle

Shuffle

前言

排序问题实现过很多次了,但是如何保证随机的乱序呢?这就是洗牌问题了(Shuffle)

洗牌算法FisherYates原理

洗牌问题

Fisher-Yates shuffle算法

首先来看看Collection里面的方法

code:

    /**
     * Created by ymk on 2019/3/28.
     * 这个算法主要是用来实现洗牌算法的
     */
	public class FisherYates {

        public static void main(String[] args) {
            Integer[] raw = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
            List<Integer> pokers = Arrays.asList(raw);
            Joiner joiner= Joiner.on(",");
            System.out.println(joiner.join(pokers));
            Collections.shuffle(pokers);
            System.out.println(joiner.join(pokers));
        }
	}

输出:

    1,2,3,4,5,6,7,8,9,10,11,12,13
	5,9,1,12,7,8,2,10,11,6,3,4,13

源码实现

    public static void shuffle(List<?> list) {
        Random rnd = r;
        if (rnd == null)
            r = rnd = new Random(); // harmless race.
        shuffle(list, rnd);
    }

    private static Random r;

     @SuppressWarnings({"rawtypes", "unchecked"})
        public static void shuffle(List<?> list, Random rnd) {
            int size = list.size();
            if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
                for (int i=size; i>1; i--)
                    swap(list, i-1, rnd.nextInt(i));
            } else {
                Object arr[] = list.toArray();

                // Shuffle array
                for (int i=size; i>1; i--)
                    swap(arr, i-1, rnd.nextInt(i));

                // Dump array back into list
                // instead of using a raw type here, it's possible to capture
                // the wildcard but it will require a call to a supplementary
                // private method
                ListIterator it = list.listIterator();
                for (int i=0; i<arr.length; i++) {
                    it.next();
                    it.set(arr[i]);
                }
            }
        }

为什么优秀?

如果简单粗暴的随机抽取不够好呢?这就和昨天的钢条问题一样,在简单随机抽取的过程中就有可能出现重复的位置,就等于浪费了一次抽取。而使用了Fisher-Yates方法之所以优秀,就是在原理上保证了不会出现浪费次数,每一次抽卡的范围都在慢慢变小

自己实现

    package Shuffle;
	import com.google.common.base.Joiner;
	import java.util.*;

	/**
     * Created by ymk on 2019/3/28.
     * 这个算法主要是用来实现洗牌算法的
     */
	public class FisherYates {

        public static void byMyWayFisherYates(Integer[] raw) {
            Random rnd = new Random();
            //nextInt(n)生成的值范围是[0,n)的
            for (int i = raw.length; i>1; i--) {
                swap(raw,i-1,rnd.nextInt(i));
            }
        }


        public static void swap(Integer[] raw, int i, int j) {
            Integer temp = raw[i];
            raw[i] = raw[j];
            raw[j] = temp;
        }


        public static void main(String[] args) {
            Integer[] raw = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
            List<Integer> pokers = Arrays.asList(raw);
            Joiner joiner = Joiner.on(",");
            System.out.println(joiner.join(pokers));
            Collections.shuffle(pokers);
            System.out.println(joiner.join(pokers));

            Integer[] newRaw = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
            System.out.println(joiner.join(newRaw));
            byMyWayFisherYates(newRaw);
            System.out.println(joiner.join(newRaw));
        }
	}