算法练习(41): 随机背包(1.3.34)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 随机背包
• Fisher–Yates洗牌算法

题目

1.3.34 随机背包。随机背包能够存储一组元素并支持下表中的 API：

API for a generic random bag
编写一个 RandomBag 类来实现这份 API。请注意，除了形容词随机之外，这份 API 和 Bag 的 API 是相同的，这意味着迭代应该随机访问背包中的所有元素(对于每次迭代，所有的 N! 种排列出现的可能性均相同)。

---

1.3.34 Random bag. A random bag stores a collection of items and supports the fol- lowing API:Write a class RandomBag that implements this API. Note that this API is the same as for Bag, except for the adjective random, which indicates that the iteration should provide the items in random order (all N ! permutations equally likely, for each iterator). Hint : Put the items in an array and randomize their order in the iterator’s constructor.

分析

这道题的难点在于“随机”二字，“随机访问背包中的所有元素”。这类就用到了一个经典的算法：Fisher–Yates洗牌算法（中文读作：费雪耶兹）

Fisher–Yates随机置乱算法也被称做高纳德置乱算法，通俗说就是生成一个有限集合的随机排列。Fisher-Yates随机置乱算法是无偏的，所以每个排列都是等可能的，当前使用的Fisher-Yates随机置乱算法是相当有效的，需要的时间正比于要随机置乱的数，不需要额为的存储空间开销。Fisher–Yates算法详解
高纳德是美国计算机科学家唐纳德·克努斯(Donald Knuth)的中文名。这位“现代计算机科学的鼻祖”是计算机界的传奇人物。他在 年仅36岁时就获得了图灵奖，成为该奖历史上最年轻的获奖者。他的获奖作品《计算机程序设计艺术》原计划出七卷，至今才出到第四卷。尽管如此，它依然与爱 因斯坦的《相对论》、狄拉克的《量子力学》、费曼的《量子电动力学》等并列，被《科学美国人》杂志评选为20世纪最重要的12本物理学著作之一。

答案

public class RandomBag<Item> implements Iterable<Item> {

    private Item[] a = (Item[]) new Object[1];
    private int N = 0;

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    public void add(Item x) {
        if (N == a.length)
            resize(2 * a.length);
        a[N++] = x;
    }

    private void resize(int max) {
        Item[] temp = (Item[]) new Object[max];
        for (int i = 0; i < N; i++) {
            temp[i] = a[i];
        }
        a = temp;
    }

    public Iterator<Item> iterator() {
        // TODO Auto-generated method stub
        return new RandomBagIterator();
    }

    private class RandomBagIterator implements Iterator<Item> {
        private int[] seq = new int[N];
        private int index = 0;

        public RandomBagIterator() {
            for (int i = 0; i < seq.length; i++)
                seq[i] = i;
            StdRandom.shuffle(seq);
        }

        public boolean hasNext() {
            // TODO Auto-generated method stub
            return index < N;
        }

        public Item next() {
            // TODO Auto-generated method stub
            return a[seq[index++]];
        }

        public void remove() {
            // TODO Auto-generated method stub

        }
    }

    public static void main(String[] args) {
        RandomBag<String> randomBag = new RandomBag<String>();
        randomBag.add("我");
        randomBag.add("的");
        randomBag.add("名字");
        randomBag.add("叫");
        randomBag.add("顶级程序员不穿女装");
        randomBag.add("微博:https://m.weibo.cn/p/1005056186766482");

        for (String string : randomBag) {
            System.out.println(string);
        }
    }
}

代码索引

RandomBag.java

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。