雪球量化投资club

前天在网上看了雪球量化投资club的直播,听了四场交流演讲,对于量化投资的基本认识更加清晰了一些。下面挑一些个人理解的要点记录一下。

  1. 量化投资并不神秘,简单的指数基金定投其实也可以归到量化投资的范畴;
  2. 宽泛一点理解,凡是可以定量计算的,都可以用于量化投资,可以做所谓的动量投资(基本上就是自动化的追涨杀跌或者高抛低吸),也可以做基本面分析,所以量化投资不一定是高频交易,也可能时低频交易,一个量化策略可以吸收各种要素;
  3. 散户搞量化交易,相比机构能获得的资源比较有限,自然是有很多劣势,但是也有自己的优势,其中最大的一个优势就是资金量上基本上不会对价格造成冲击,所以交易成本很低。
  4. 量化是利用数据分析与程式化的交易(中低频交易不需要自动化程序)来反人性,用数据说话,而不要过于相信感觉或直觉;
  5. 量化交易要看全局看全时,总的目的是自己的投资组合赚钱,而不纠结于个别的品种,应当做较长时间的历史分析,而不能只看最近的效果;
  6. 量化交易一般需要建立模型,在历史数据上回测再调整,然而历史是螺旋发展的,回测可能会有过拟合的现象,也就是说,会出现一些特别的参数效果特别好,但是用来做策略未来不一定会好。我觉得最好还是要有对模型为什么效果会好的解释,并考察这种解释在未来是否会失效,比如最小市值策略,解释是A股特有的壳价值带来的,但如果新股发行持续改革,这个策略就会失效。
  7. 散户资金量小,可能无法建立足够的股票池构建组合,这时候可以考虑基金,类似华泰证券的券商基金交易费率极低,且没有最小消费的限制,非常适合量化交易。此外,如果场外购买基金,交易费率也是要仔细比较的。
  8. 学好Python,对量化交易好处多多。看来我去年开始用Python是个明智的决定。
  9. 在A股量化策略容易有效的原因是韭菜多,不过这种好日子估计最多5~10年,挣超额收益会越来越难。
  10. 演讲中提到的相关的资源:
    1. tushare:一个开源的金融数据库,可以用Python非常方便的使用;
    2. 优矿:一个量化策略平台,提供了丰富的API,支持Python语言。
    3. SSRN:获取免费的金融方面的英文论文。

比特币FAQ

这篇比特币FAQ试图以FAQ的形式对比特币做一个简单的介绍。主要参考了比特币白皮书和普林斯顿大学的教材《区块链:技术驱动金融》,当然不可避免的包含了很多个人理解,欢迎探讨。

1.什么是比特币?

比特币是一种数字货币,它不依赖于某一个中心机构发行,而是依赖于互联网,基于密码学与分布式计算理论发行,人人都可以参与,它的总量有限,你可以把它想象成数字世界的一种黄金。

2.比特币有什么用?

比特币是一种数字货币,因此理论上它可以做任何钱可以做的事情,目前来说它可以买到的最重要的东西是各国的货币,而在一些承认了比特币货币地位的国家,比如日本,比特币已经可以买机票之类的东西了。即使不把比特币当成货币,然而它依然可以以物换物,只要交易的参与者认同它的价值。

3.货币应当有国家信用背书,比特币没有,那么它的信用来自于哪里?

货币不一定要有国家信用背书,比如目前黄金还是可以用作国际通行的货币,货币的信用来自于有多少人相信它是货币,基于国家发行的纸币讲的是一个故事,基于密码学共识发行的比特币讲的是另一个故事,人类正是因为有了相信故事的能力,才能组织起更大规模的合作。(推荐阅读《人类简史》

比特币的信用来源确实不好理解,它通过一种分布式的方式,对谁有多少钱这个问题达成了共识,只要参与这个系统的人都不可否认。你仍然需要理解的是,任何现代货币都是一个故事,货币的特点就是承认它有货币价值的人越多,它就越有货币价值,所以不可否认这里面有信仰成分。

4.这么说比特币就是一种传销或者说庞氏骗局嘛?

比特币和传销或庞氏骗局有一点相同,就是都需要一点点信仰。但是区别主要在于,对比特币的信仰会使得这种货币真正具有价值,它的价值就是作为一种货币存在,而不是其他的。而传销或者庞氏骗局带来的是更多的上当受骗的人。另外还有一点不那么重要的区别在于,比特币社区聚集的是一帮极客,他们希望的是建立一种新的货币体系,出发点绝不是骗钱。

5.比特币究竟是怎么发行的?

比特币需要定期对所有未确认的交易进行确认记账,而获得这个记账权的人将获得一定的比特币奖励,这些奖励是比特币原始的来源。每完成一批交易的记账,会打包成一个所谓的区块,每个区块都有一个指针指向前一个区块,因此被称为区块链。

6.谁有多少比特币是怎么记录的,有一个类似银行的账户么?

并没有类似银行账户的概念,比特币区块链只是记录了比特币的产生,以及它产生后所有的转账记录,当转账到某个地址而暂时没有转出时,则这个地址对这个比特币有所有权。

7.地址是什么?

地址可以理解为一种身份的证明,它是公开的,就像人人都能看见你家大门上的门牌号码一样。但是只有你自己有一把钥匙可以打开这扇门,这里用到了密码学中的签名算法,总的来说,你可以通过私钥来证明这个地址(公钥)归你管理。

8.比特币真的有一个一个的币吗?

上面我们说了,比特币区块链就是一个大帐本,所以并没有像人民币那样一个一个的币存在,而只是人人都能看到某个地址上有多少数量的比特币还没有花掉,而这个地址上的比特币只有持有私钥的人才能签名确认后花掉。因此,比特币实际上就是私钥,因为知道了私钥的人就能花掉比特币。

9.怎么保存比特币?

首先,如前所述,保存比特币首要的就是要保存私钥,这是所谓比特币钱包的主要功能,私钥泄露,则比特币丢失。此外,某个地址上有多少币是由公共的区块链来确定的,人人都可以连上比特币网络验证。

10.那么究竟谁来记账呢?我为什么要信任这个记账的人?

这是比特币的最精妙的设计。谁来记账是一个不确定的事情,每个节点都要去花很长的时间的计算(这需要消耗电力)来竞争这个记账的权力,获得记账权力后,如果随便乱记,那么会得不到其他节点的承认,这个生成的区块也将作废,虽然它也指向前一个区块形成了区块链,但是其他的人可以创建一个得到更多人承认的区块,产生一条更长的区块链,使得你这条短的区块链作废,浪费了电力而得不到打包的比特币奖励。这种精妙的设计通过人性是逐利的来达到了可信。

##11.每个区块都会产生比特币,那么比特币会不会越来越多?

不会,每个区块的奖励每隔一段时间会减半,因此这是一个比例为1/2的等比数列,其总量为2100万个。因此比特币是设计为通缩的。

12.通缩的货币会越来越能换到更多的商品,那么理论上人人都会囤积比特币而不会花费比特币,那么它还有货币价值吗?

这确实是个好问题,我的理解是到一定的时候(比特币获得了它应有的地位,价格趋于稳定),比特币的拥有者自然会花比特币,就像现在拥有黄金的人一样。而且比特币可以和其他支持通胀的货币一起构成货币体系,就如同现在的黄金和法币一样。

13.我听说比特币是匿名的,所以都被用来买毒品?

比特币是一个公开的大帐本,但是它的地址是一串字符串,确实不能直接和人联系起来,因此有一定的匿名性。但是同时,它的账本是公开的,历史是不可更改可以随时查看的,从这个角度来说,它的匿名性还不如现金,只要把比特币地址和人取得了联系,就会追溯到所有的历史。实际上,用比特币贩毒的丝绸之路就被FBI抓了,所以比特币只是一种工具,并不天然的利于犯罪。

14.我听说比特币被用来洗钱?

就像上一问一样,我不认为比特币天然的利于洗钱,像中国政府已经开始监管交易所里用比特币进行洗钱的风险了,我觉得比特币还是应当更多的用于合规合法的应用。

15.要怎么获得比特币呢?

目前来说,通过竞争记账权,也就是俗称的挖矿,来获得比特币已经很专业很困难了,最简单的办法还是找持有比特币的人用人民币来买,而买卖的方式,最简单的是通过场外交易平台,如LocalBitcoins。参见如何获得比特币?

16.既然比特币只是一种技术,而不由任何组织发行,那么岂不是随随便便都会产生类似的各种数字货币?那么比特币还有什么特别的价值吗?

确实是可以产生任意多种类似的数字货币,甚至它们的技术可以更优秀,但是有两点需要注意,比特币有先发优势,数字货币的价值需要越多参与者越好,在比特币已经占领高地的情况下其他数字货币很难从头开始取得优势地位,其次比特币自身也是可以进行技术革新而进化的。

17.我听说最近比特币分裂了,这是怎么回事?

比特币的相关规则和软件都是开源的,因此当有人不认同现有理念的时候,可以从某个区块开始,按照一个新的规则来打包交易(挖矿),而不接受原来的规则挖出来的区块,反之原来的规则也不再兼容这个新规则挖出来的区块,因此从这个区块开始,有两条区块链各自为政。在这个分类区块之前的未使用的比特币,可以同时转账到两个区块链分支,因此先当于1个原来的比特币变成了新的两个区块链上的各1个比特币。

18.这种分裂不是相当于比特币翻倍了么?

不完全是这样,分裂后的比特币由于参与者用脚投票,会出现价值上的差异,从既定事实的角度来说,只有价值高的那种才算是正宗的比特币。目前比特币的转账手续费较高,如何解决这个问题,产生了两个方案,一个是对区块的大小进行扩容,支持这个观点的人分叉出了被称为BCH的数字货币,而另外更复杂的协议仍暂时保留了BTC的称号。

19.比特币和区块链的关系?

区块链技术产生于比特币的研发,目前衍生出更多的技术,但是区块链技术的应用场景还需要进一步着实,目前的热潮泡沫很大,个人认为以比特币为代表的数字货币才是区块链真正落实了的应用场景。很多应用场景根本没必要使用区块链技术,但是数字货币却很可能是很有必要的,这一点在此不能详述,可以参见哈耶克的《货币的非国家化》。

20.如何投资比特币?

对大部分人来说,投资比特币唯一可行的方式就是用少量的完全不影响生活的钱购买比特币,长期持有5~10年。由于比特币价格仍在剧烈波动中,任何试图追涨杀跌的行为都将陷入赌徒的境地。

投资中的傲慢与偏见

雪球网是我去年以来上得最多的网站之一,在我尝试投资的路上,起到了很大的作用,即使到现在,我的选股也还有很大抄作业的意味,看看雪球上的大V们感兴趣的股票,再加上一些自己的分析判断,大概是我目前的水平状态。

雪球上当然也有韭菜和小白,有一些感觉水平比我还低的人,但是大部分情况下我觉得讨论质量还是比较高的。不过最让我觉得讨论水平低下的是对比特币的讨论,无论是大V,还是小白,大部分人的看法都是“传销”,“庞氏骗局”,“没有国家背书的货币毫无意义”,“本世纪最大骗局”之类的。说实话,我也看不清比特币的未来,可能还要至少翻一百倍,也可能一文不值,只能当作一个时代的纪念。但是我能够清楚明白的是,这是一个有着深厚数学基础和经济学基础的伟大发明,而绝不是什么传销和旁氏骗局能解释的。比特币作为一种金融工具,但是由于它的数学基础与程序运行的特点,吸引的早期用户大多是程序员,很多传统的投资界人士可能并没有用心去了解过,或者实际上看也没看懂。

我一直觉得投资中的两大心理障碍是贪婪与恐惧,但是现在发现傲慢与偏见也是,比如很多人都倾向于投资计算机、互联网这些高大上的新兴行业,而对白酒、水电之类的没有太多技术含量的股票不屑一顾。我觉得如果抛开道德因素看的化,任何钱都是平等的,卖白酒的也是挣钱,卖软件的也是挣钱,没有高低之分,对投资人而言,更是应该哪里挣钱哪里去。

其实我看到雪球上的投资人对于比特币的无知言论是觉得很高兴的,因为这说明还有很多人没有发现数字货币和区块链的价值,比特币其实还是再比较小的圈子的一个玩具,对它的推广固然任重道远,但也蕴含了无穷的潜力。这也启示我,对于自己不懂不了解的东西千万不要妄下结论,否则失去了真理也失去了真金。

(写此文时,比特币价格突破3000美金。)

《战狼2》:战狼2的成功启示

战狼2

战狼2票房已经突破20亿,豆瓣评分也高达7.5分(好于79%的动作片),我觉得算是叫好又叫座了。我也凑热闹去看了,电影本身我觉得人们已经讨论得够多,我没什么要补充的,总的来说,达到了好莱坞大片的水准,要是把主角换成美国人,解放军换成美军,照样是一部好的爆米花电影。

我想说说它的成功。人们调侃说,估计现在找吴京投资《战狼3》的投资人都把钱堆到他家门口了,毫无疑问,《战狼2》获得了极大的商业成功,电影背后的故事也被逐渐挖了出来。看完这些故事,再联系电影本身的品质,我想有几点值得思考:

  1. 成功需要各种因素,《战狼2》赶上了这个月没有外国大片,主要对手《建军大业》太过于作业化,夹带的爱国主义情怀赶上了中国民族主义的上升期,当然最主要的还是电影的品质过硬;
  2. 吴京我最早知道他是电视剧《太极宗师》,算是男一号,但是后来一直坎坷,在香港电影里面演反角,比如《杀破狼》,动作很凌厉,但毕竟是反派,还只是大反派的小打手,台词都没几句。《战狼2》片头鸣谢了刘伟强和陈木胜,可以想象,吴京在这些动作片导演下没有白呆,从一个动作片演员到大片导演,虽然我不是行内人,也可以想象有多少东西需要学习;
  3. 吴京的老婆谢楠挑人的眼光真不错,所以才有抵押房产投资电影的故事,我老婆说,仔细看看,吴京也还蛮帅的,认真的男人最帅吧。

有趣的位操作

位操作总给人一种直接安排计算机0/1的感觉,这里搜集整理一些有趣的题目。

在线编程(刷题)的低级错误

最近几天在一些OJ网站上刷了不少算法题,都是直接在网页上写代码,脑中调试,然后提交,发现提交通不过大概有以下几种情况:

  1. 算法设计出现根本性错误,一般是对题意有误解,或重要的分支情况未考虑到;
  2. 算法设计基本正确,但是有一些边界情况未考虑到;
  3. 时间复杂度太高;
  4. 低级错误。

以上的1、2、3属于算法的基本功,无论你是在线刷题,还是用IDE刷题,都避免不了,但是对于低级错误,IDE的编辑器静态分析就能发现一批,编译时又能发现一批,似乎也不是什么问题。

问题在于,技能的反面就是解决问题,解决一些低级错误是会浪费时间的,而且,有一些低级错误会躲过编译器,造成更大的危害,因此很有必要尽量减少这些低级错误。在线刷题时,我自己常见的低级错误(主要是java语言的):

  1. 没有写分号,或者写了中文分号;
  2. 括号未匹配;
  3. 未记住一些API的名称,比如HashMap中的containsKey而不是contains;
  4. 拼写错误,导致API调用错误,甚至标识符前后不一致;
  5. 更改了某个标识符,但是没有更改完全;
  6. 忘记写返回语句,或者某些支路忘记写返回语句,甚至返回了错误的变量或变量类型;
  7. 重复声明变量,比如循环内外各申明一次;
  8. 想要在循环外使用循环变量,但没有在外面声明;

暂时这些,以后不断补充。

如何改善?我发现我这么多年来都犯了一个错误,因为自己粗心,又觉得不可能不犯错误,就放弃了改善的机会,有些放任自流,从认识上就需要提高。以下是一些观点和方法,希望慢慢能标本兼治:

  1. 人都会犯错误,甚至犯低级错误,即所谓的粗心,粗心不能根除,但是可以改善;
  2. 意识到自己的低级错误并改善,而不要视而不见,放任自流;
  3. 适当放慢速度,萝卜快了不洗泥;
  4. 第一遍写的时候随时自我复查,要习惯脑子里有一个角色在复查,争取一次写对;
  5. 写完复查一遍。
  6. 及时总结自己犯了哪些低级错误。

这里谈的都是低级错误,还每涉及到如果提高程序的正确性,这一点以后再总结。

逆序对计数问题

有一组数,对于其中任意两个数组,若前面一个大于后面一个数字,则这两个数字组成一个逆序对。计算给定数组中的逆序对个数。

《建军大业》:创业的细节

建军大业

跑到电影院去看这部一般来说应该免费接受教育的电影,一是满足某人的恶趣味去数星星,二是自己也对一切创业史感兴趣。主旋律的题材,香港导演,一堆小鲜肉演员,作为电影来说还是及格的,只是这个故事我们已经看过无数遍了。反倒是一些细节我比较感兴趣,而还有一些细节却在电影中看不出来,看来真感兴趣还是得去读史料。

  1. 电影中有一段南昌起义后征用南昌银行中金条的小场景,甚至还有拿枪顶着人头同时又打欠条的镜头,一般历史的角度都是从政治军事来看的,但是我对经济的角度却最感兴趣,想知道民国时期,军阀割据时,各家是如何解决军饷问题的。
  2. 南昌起义基本失败后,朱德手下只剩下八百人,但是到了井冈山会师时,又拉出了几万人的队伍,包括打散了的叶挺、贺龙等等,后来都扩充了军队,我其实对这些人在阶段性失败后如何东山再起比较感兴趣,一般的文艺作品貌似着墨不多,可能一般对毛泽东的路线斗争与邓小平的几起几落写得多一些。
  3. 这次电影的战斗效果很爆表,我都很怀疑真正的历史火力有没有那么猛。然后,电影中还有毛泽东买军火的片段,我对当年的军火的来源与流动也很感兴趣。电影中还提到了汉阳兵工厂,它的百年历史,拍成电影或电视剧应该也很有意思。

硬币组合问题

假设我们有面值为1,2,5,10,25的硬币,那么组成面值共有多少种可能的情况?这是美分的情况。

一般的假设我们有面值为的硬币,其中,那么组成面值共有多少种可能的情况?

按照一般找钱的顺序,我们从大钱开始考虑,这样剩下的面值才能比较迅速的减小。

1.递推式1

考虑美分的情况,假设我们要组成面值101,记组合数为f(101),如果使用了一个25分的,那么剩下的情况数应该是f(76),但是注意,这个f(76)已经不能使用25分的硬币了,简单起见,我们把硬币种类编号引入组合数,当可以用编号1~k时,组合数记为f(m,k),所以上面的分析可以记为组合数f(101,5),使用了一个25分时,剩下的情况数为f(76, 4),针对25美分的使用,可以得到下表

25分个数 剩余
0 f(101, 4)
1 f(76, 4)
2 f(51, 4)
3 f(26, 4)
4 f(1, 4)

将第二列的数字相加,就得到了结果。现在要求的问题简化了,只需要考虑面值为1,2,5,10的情况,同样的以f(76, 4)为例,可以化简为f(76,3),f(66,3)…f(6,3),这样递归迭代下去,我们最终要解决的子问题是f(m,1),用一种面值来组成m,显然,只需要面值m能被整除即可,由此结束了递归迭代。

按照这种思路,直接写成Java代码如下:

    public int countCoins(int n, int[] coins) {
        if(n < 0) return 0;
        return countCoins(n, coins.length - 1, coins);
    }

    public int countCoins(int n, int level, int[] coins) {
        if(level == 0) {
            return n % coins[0] == 0 ? 1 : 0;
        }
        int ways = 0;
        for(int i = 0; i*coins[level] <= n; i++) {
            ways += countCoins(n-i*coins[level], level-1, coins);
        }
        return ways;
    }

2. 递推式1的动态规划

在1中,我们通过不断的减去大的硬币面值,求解各个子问题,得到最终的结果,不难发现,这些子问题存在很多重复,比如考虑如下的计算路径:f(101, 5)->f(76, 4)->f(16,3)…和f(101, 5)->f(26, 4)->f(16,3)…后面的计算时完全重合的,因此,如果把这些计算结果缓存起来,可以大大提高计算的速度,这就是动态规划的思想。我们需要建立如下的一张表,以下考虑计算f(6,5)

  0 1 2 3 4 5 6
1 1 1 1 1 1 1 1
2 1 1 2 2 3 3 4
5 1 1 2 2 3 4 5
10 1 1 2 2 3 4 5
25 1 1 2 2 3 4 5

注意到我们的递推式,每次分解出很多项,那么在动态规划填表时,也就需要很多项目相加才行。动态规划时,先填满第一行,再根据递推式计算第二行,直到计算最后一行。

由此得到Java代码如下:

    public int countCoins(int n, int[] coins) {
        if(n < 0) return 0;
        int[][] ways = new int[coins.length][n + 1];
        for(int j = 0; j <= n; j++) {
            ways[0][j] = j % coins[0] == 0 ? 1 : 0;
        }
        for(int i = 1; i < coins.length; i++) {
            for(int j = 0; j <= n; j++) {
                if(j < coins[i]) {
                    ways[i][j] = ways[i-1][j];
                }
                else {
                    for(int k = 0; k*coins[i] <= j; k++) {
                        ways[i][j] +=  ways[i-1][j-k*coins[i]];
                    }
                }
            }
        }
        return ways[coins.length - 1][n];
    }

注意到最后一行其实只需要计算最后一个元素。(因为它只跟前一行相关),所以上述代码还可以修改节约时间,不过代码会变得不太美观,这里就不写了。

3 递推式2及其动态规划

我们发现,递推式1中,一项被分解成多项,导致计算过程中做了相当多的加法,能不能简化一下呢?

还是考虑f(101,5),我们可以这样考虑,首先不使用25美分,情况数为f(101,4),其次是使用25美分的情况,那么至少要使用一个25美分,如果去掉这个25美分,则相当于剩下的76美分,既可以使用25美分,也可以不用,实际上就是f(76,5),由此得到递推关系,这样在动态规划填表时,每次取上一行的数与本行之前相距的数相加。注意当

由此得到动态规划的代码如下:

    public int countCoins(int n, int[] coins) {
        if(n < 0) return 0;
        int[][] ways = new int[coins.length][n + 1];
        for(int j = 0; j <= n; j++) {
            ways[0][j] = j % coins[0] == 0 ? 1 : 0;
        }
        for(int i = 1; i < coins.length; i++) {
            for(int j = 0; j <= n; j++) {
                if(j < coins[i]) {
                    ways[i][j] = ways[i-1][j];
                }
                else {
                    ways[i][j] = ways[i-1][j] + ways[i][j-coins[i]];
                }
            }
        }
        return ways[coins.length - 1][n];
    }

4 递推式2的简化

仔细考察我们填表的过程,填第二行时,左边的较小元素和第一行一样,右边较大的元素在第一行的基础上加上本行较小的一个元素,所以其实只需要存储一行元素就行了,计算 时, 在左边已经计算出来了,而直接使用自身存储便可。由此得到更加简化的动态规划代码:

    public int countCoins(int n, int[] coins) {
        if(n < 0) return 0;
        int[] ways = new int[n + 1];
        for(int j = 0; j <= n; j++) {
            ways[j] = j % coins[0] == 0 ? 1 : 0;
        }
        for(int i = 1; i < coins.length; i++) {
            for(int j = coins[i]; j <= n; j++) {
                ways[j] += ways[j-coins[i]];
            }
        }
        return ways[n];
    }

考虑第一行,如果设置ways[0] = 1,j<coins[0]时,ways[j] = 0,那么第一行同样可以用递推式ways[j] += ways[j-coins[i]]得到。代码可进一步简化如下:

    public int countCoins(int n, int[] coins) {
        if(n < 0) return 0;
        int[] ways = new int[n+1];
        ways[0] = 1;
        for(int i = 0; i < coins.length; i++) {
            for(int j = coins[i]; j <= n; j++) {
                ways[j] = ways[j] + ways[j-coins[i]];
            }
        }
        return ways[n];
    }

全排列生成算法实现

我们知道n个相异元素的全排列种数为n!,那么由程序如何生成n个相异元素的排列呢,对此问题的研究很多,本文首先用Java实现了《算法设计与分析基础》一书中4.3节的三个算法。

1 插入法

这种算法最直观,基于排列的递推定义。符合所谓减治法的思想,或者说是数学归纳法的思想,如果n-1个元素已经排好,我们只需要把第n个元素插入这些排列中所有可能的位置即可,每个元素有n个位置可以插入,刚好是(n-1)!*n=n!种情况。如果插入的时候,方向先从右到左,再从左到右循环,那么每两个相邻的排列将只有最小的差异,即只有某两个相邻元素相异。比如已经有12,21则12从右到左插入3,21从左到右插入3,最终得到123,123,312,321,231,213。具体的Java代码如下,这是一个递归算法。

public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if(n <= 0) return permutations;
        if(n == 1) {
            permutations.add( new int[]{1});
            return permutations;
        }
        ArrayList<int[]> remainders = getPermutations(n-1);
        for(int i = 0; i < remainders.size(); i++) {
            int[] remainder = remainders.get(i);
            for(int j = 0; j < n; j++) {
                int[] permutation = new int[n];
                if(i % 2 ==0) {//insert from right to left
                    System.arraycopy(remainder, 0, permutation, 0, n - 1- j);
                    permutation[n - 1 - j] = n;
                    System.arraycopy(remainder, n - 1 - j, permutation, n - j, j);
                }
                else {//inset from left to right
                    System.arraycopy(remainder, 0, permutation, 0, j);
                    permutation[j] = n;
                    System.arraycopy(remainder, j, permutation, j + 1, n - 1- j);
                }
                permutations.add(permutation);
            }
        }
        return permutations;
	}

2 JohnsonTrott算法

在Johnson-Trotter算法中,每次循环都进行一次满足条件的相邻元素的交换,直到不存在满足条件的可交换的元素,此时说明所有排列的情况均已输出,算法结束。

具体过程如下:

  1. 初始化所有元素的移动方向为左,输出序列本身
  2. 移动最大的可移动的元素(当元素移动方向上的元素比自己小时,才能移动)
  3. 反转所有比移动元素大的所有元素的移动方向
  4. 重复2~3步,直到不能移动为止

具体例子

上面的算法流程有些抽象,现在举个例子来加深理解。假设现在要计算所有排列。首先是将所有元素的移动方向为标记为向左,我们可以表示成这样,然后根据算法流程中的步骤2,移动最大的可移动元素。这里的可移动元素是指在其移动方向上的相邻元素比自己小时,例如都是可移动元素,因为在他们的移动方向上(左移)的相邻元素:1,2分别比2,3小,而每次都只移动这些可移动元素中最大的那个项。接着,在每次交换完成之后,寻找所有比当前交换元素大的元素,将他们的移动方向反转一下。

下面列出在计算过程中所有的情况

Java代码如下:

public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if (n <= 0) return permutations;
        int[] first = new int[n];
        boolean[] mobile = new boolean[n];
        for(int i = 0; i < n; i++) {
            first[i] = i + 1;
            mobile[i] = true;//true:left; false:right;
        }
        permutations.add(first);

        while(true) {
            int[] last = permutations.get(permutations.size()-1).clone();
            int k = findLargestMobile(last, mobile);
            if(k == -1) break;
            int max = last[k];
            int neighbor = mobile[k] ? k - 1 : k + 1;
            swap(last, k, neighbor);
            swap(mobile, k, neighbor);
            reverseLarger(last, mobile, max);
            permutations.add(last);
        }
        return permutations;
    }

    private static int findLargestMobile(int[] array, boolean[] mobile) {
        int k = -1;// -1 means can't find mobile element
        int max = -1;
        for(int i = 0; i < array.length; i++) {
            int j = mobile[i] ? i - 1: i + 1;
            if(j < 0 || j >= array.length) continue;
            if(array[i] > array[j] && array[i] > max) {
                max = array[i];
                k = i;
            }
        }
        return k;
    }

    private static void reverseLarger(int[] array, boolean[] mobile, int max) {
        for(int i = 0; i < array.length; i++) {
            if(array[i] > max) mobile[i] = !mobile[i];
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    private static void swap(boolean[] array, int i, int j) {
        boolean temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

3 字典序生成法

字典序生成法在当前已经生成的排列上寻找下一个字典序的排列:

  1. 找到最长的递减序列后缀,记这个序列的前一个元素为i,如果找不到i,则证明已经生成了最后一个完全倒序的排列,生成完毕。
  2. 在前述后缀中,找到比元素i大的最小元素j,并交换i和j;
  3. 将后缀逆序排列。
  4. 重复1到3。

比如排列123654,首先找到后缀654,在找到中间最小大于3的4,交换得到124653,然后将后缀逆序得到124356,又如排列123645,找到后缀5,交换得到123654,后缀只有一个,逆序后不变仍未123654。

具体的Java代码如下:

public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if(n <= 0) return permutations;
        int[] first = new int[n];
        for(int i = 0; i < n; i++) first[i] = i + 1;
        permutations.add(first);

        while(true) {
            int[] last = permutations.get(permutations.size()-1).clone();
            int i = n - 1;
            while(i > 0) {
                if(last[i] > last[i-1]) {
                    break;
                }
                i--;
            }
            if(i==0) break;

            int j = n - 1;
            while(j >= i) {
                if(last[j]>last[i-1]) {
                    break;
                }
                j--;
            }
            swap(last, i-1, j);

            int k = n - 1;
            while(i < k) {
                swap(last, i, k);
                i++;
                k--;
            }
            permutations.add(last);
        }
        return permutations;
    }

4 序数法

这个方法把n!个排列与0~n!-1之间的数一一对应起来,这样,我们就可以按照0~n!-1的次序,逐一生成相关的排列。这个对应的关键在于0~n!-1之间的数m,可以用如下的方式表示: ,其中

故m对应序列,现在再把这个序列和排列一一对应起来,n-1位的序列对应n位的排列。

表示排列p中的数i+1所在位置的右边比它小的数的个数。比如对于排列p=4213,4,3,2的逆序数分别为3,0,1,由此对应为,反过来呢,如果知道了逆序数,也可以一一恢复出排列来。比4小的有3个,4只能放最左边,比3小的为0个,3只能放最右边,比2小的一个,2放第二个位置,剩下的放1,故为4213。

0 000 1234 12 200 1423
1 001 2134 13 201 2413
2 010 1324 14 210 1432
3 011 2314 15 211 2431
4 020 3124 16 220 3412
5 021 3214 17 221 3421
6 100 1243 18 300 4123
7 101 2143 19 301 4213
8 110 1342 20 310 4132
9 111 2341 21 311 4231
10 120 3142 22 320 4312
11 121 3241 23 321 4321

Java代码如下:

    public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if (n <= 0) return permutations;
        int[] factorials = new int[n+1];
        factorials[0] = 1;
        for(int i = 1; i <=n; i++) {
            factorials[i] = i * factorials[i - 1];
        }// init factorial array
        for(int m = 0; m < factorials[n]; m++) {
            int remainder = m;
            int[] permutation = new int[n];
            for(int i = n-1; i >=0; i--) {
                int count = remainder / factorials[i];
                remainder = remainder % factorials[i];
                setPosition(permutation, count, i + 1);
            }
            permutations.add(permutation);
        }
        return permutations;
    }

    private static void setPosition(int[] permutation, int count, int num) {
        int zeros = 0;
        for(int i = permutation.length - 1; i >=0; i--) {
            if(permutation[i] == 0) zeros++;
            if(zeros == count + 1) {
                permutation[i] = num;
                break;
            }
        }
    }

5 轮转法

基准序列,先逐步生成以开头的所有排列:

  1. 先生成以开头的所有排列
  2. 再生成以打头的排列,除了前述2个排列外,再将其后三位从左至右轮转2次,得到4个新排列,一共6个排列;
  3. 再生成以打头的排列,除了前述6个排列外,再将其后四位从左至右轮转3次,得到18个新排列,一共24个排列;
  4. 依次类推,一直到生成以开头的所有排列为止。

然后将基准序列从左到右轮转一次,生成以开头的所有排列,依次类推,直到生成以开头的所有排列。

java代码如下:

    public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if (n <= 0) return permutations;
        int[] first = new int[n];
        for(int i = 0; i < n; i++) {
            first[i] = i + 1;
        }
        for (int i = 0; i < n; i++) {
            if(i > 0) {
                rotateLeft(first, 0, n);
            }
            int[] base = first.clone();
            permutations.addAll(rotateBase(base));
        }
        return permutations;
    }

    private static ArrayList<int[]> rotateBase(int[] base) {
        ArrayList<int[]> permutations = new ArrayList<int[]>();
        permutations.add(base);
        for(int prefixSize = base.length - 2; prefixSize >= 1; prefixSize--) {
            int currentSize = permutations.size();
            for(int i = 0; i < currentSize; i++) {
                int[] last = permutations.get(i);
                for(int j = 0; j < base.length - prefixSize - 1; j++) {
                    int[] rotated = last.clone();
                    rotateLeft(rotated, prefixSize, base.length);
                    permutations.add(rotated);
                    last = rotated;
                }
            }
        }
        return permutations;
    }

    private static void rotateLeft(int[] permutation, int start, int end) { 
      // rotate from left to right
        int temp = permutation[start];
        for(int i = start; i < end - 1; i++) {
            permutation[i] = permutation[i + 1];
        }
        permutation[end-1] = temp;
    }

6 回溯法

我们将问题形象化,假如你手里有编号为1、2、3的3张扑克牌和编号为1、2、3的三个盒子。现在需要将这3张扑克牌分别放入3个盒子里,并且每个盒子有且只有一张扑克牌。总共有几种放法呢?

首先你来到了1号盒子面前,你现在手里有3张扑克牌,先放哪一张好呢?很显然三者都要尝试,那就姑且约定一个顺序:每次到一个盒子面前,都先放1号,再放2号,最后放3号。于是你在一号盒子里放入了编号为1的扑克牌。来到2号盒子面前,由于之前的1号扑克牌已经不在手中,按照之前约定的顺序,你将2号牌放到了2号盒子里。3号也是同样。你又往后走当你来到第4个盒子面前,诶,没有第四个盒子,其实我们不需要第4个盒子,因为手中的扑克牌已经放完了。

你发现了吗?当你走到第四个盒子前的时候,已经完成了一种排列,即“1 2 3”。然而并没有到此结束,产生了一种排列之后,你需要立即返回。现在你已经退到了3号盒子面前,你需要取回之前放在3号盒子中的扑克牌,再去尝试看看还能否放别的扑克牌,从而产生一个新的排列。于是你取回了3号牌,但由于你手中只有3号牌,你只能再次退回到2号盒子面前。

你回到2号盒子后,收回了2号牌。现在你的手中有2张牌了,分别是2号和3号牌。按照之前的约定,现在需要往2号盒子中放3号扑克牌(上次放的是2号牌)。放好后,你来到3号盒子面前,将手中仅剩的2号牌放入了3号盒子。又来到了4号盒子面前,当然没有4号盒子。此时又产生了一个新的排列“1 3 2”。

接下来按照刚才的步骤去模拟,便会依次生成所有排列:“2 1 3”、“2 3 1”、“3 1 2”和“3 2 1”。

Java代码实现如下:

    public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if (n <= 0) return permutations;
        boolean[] visited = new boolean[n];
        int[] current = new int[n];
        dfs(permutations, current, visited, 0);
        return permutations;
    }

    private static void dfs(ArrayList<int[]> permutations, int[] current, boolean[] visited, int step) {
        int n = current.length;
        if(step == n) {
            permutations.add(current.clone());
            return;
        }
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                current[step] = i + 1;
                visited[i] = true;
                dfs(permutations, current, visited, step + 1);
                visited[i] = false;
            }
        }
    }

当然,如果改用栈,也可以变成非递归的版本。

后记

对一个问题用不同的算法解决,可以综合复习各种算法思路。

另外重要的一点就是,如果看过一个算法没有写代码实现过,很可能会有一些没有真正理解的细节存在。

如果以后再发现好的算法,还会再补充。