投资中的傲慢与偏见

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

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

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

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

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

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

战狼2

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

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

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

朝闻道家庭基金条款

1. 基金介绍

  1. 朝闻道家庭基金(以下简称本基金)是基金管理人(也就是本人,以下简称管理人)个人投资时,为了方便计算实际收益率而成立的,如果亲戚朋友认同本人投资理念,有意参与成为投资人也欢迎;
  2. “朝闻道”取自论语“朝闻道,夕死可矣”,因为管理人认为,正确的理念是投资赚钱最重要的因素;
  3. 本基金投资的品种包括但不限于股票、基金、网贷、数字货币等;
  4. 本基金属于进取型投资风格,因此基金净值可能会有较大波动(预期30%),预期年化收益为20%。
  5. 本基金于2017年初成立,投资活动与净值计算从2016年开始,基金的过往情况请参考这里

2.投资人须知

  1. 对管理人有深入的了解,相信管理人的人品与知识水平;
  2. 所投入的资金最好是3~5年内确定不需要动用的,如果短期投资建议投资类似余额宝的货币基金;
  3. 本基金不保底,高收益的投资还保底的都是骗子,投资人应能够承受本金的损失,管理人会力求避免本金的损失,但是这种风险是不可能消除的;
  4. 不要因为短期的净值波动而质疑管理人,管理人可以向投资人介绍投资的品种,解释投资决策的理由,但是没有做这些事情的义务;
  5. 投资人赎回份额时,请至少提前3个交易日预约,管理人需要时间卖出资产获取现金。
  6. 为减轻工作量,管理人只在每月月底公布净值,此外,会在投资人投入、提现资金的当日计算净值。
  7. 起投金额1万元。

3. 收费标准

只有收费,管理人才有更大的动力来取得收益,投资人才能正视投资的风险。目前私募基金的收费标准一般是每年管理费2%,并计提超额收益的20%。本基金将以大大低于私募的标准收费。

  1. 管理费:三年之内资金退出时,无论是赚钱还是亏损,一次性收取本金1%的管理费,三年以上资金退出时,免收管理费,以上是为了鼓励长期投资至少三年;
  2. 收益分成基准:以央行三年期定期存款利率为标准,低于标准不分成;
  3. 收益分成方法:
    1. 高于收益分成基准的收益在资金退出时管理人一次性分成20%;
    2. 基金分红时管理人分成20%。
  4. 收益计算方法:按投资人投入时的基金净值计算基金份额,提现时再按基金份额与提现时的净值计算收益。
  5. 关于分红:本基金三年内没有任何分红的计划,所有投资活动获得的红利等现金收入,都将再次投入进行投资。投资人如果想获得现金,只能赎回基金份额。

下面举一个例子,投资人投入15000元,此时净值为1.5,份额10000份,三年后全部提现,此时净值2.5,价值25000,实际收益10000元,收益率为(2.5-1.5)/1.5=66.67%,免收管理费,按照央行三年期定期存款利率3.25%计算,基准收益率为9.75%,故超出部分收益为56.92%,管理人分成超出收益的20%,即(56.92%*0.2=)11.38%,合(15000*11.38%= )1707元,投资人实际收益为(9.75%+56.92%*0.8=) 55.29%,合(15000*55.29%=)8293元,本息合计23293元。

看不懂计算过程的,请参考第2条第1款。

有趣的位操作

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

朝闻道家庭基金201707月报

本月所持股票基本在横盘调整,贵州茅台再次接近历史新高,银行股经历了一次上涨。清空试验仓位瑞贝卡,因为看到一篇瑞贝卡的专题报道,说它的高管工资特别特别低,我觉得这是很不正常的,还是不碰为妙,搞笑的是卖了就大跌了。减仓万科,前期越跌越买的资金可以减少一些了。中青旅换成了中国国旅,主要是考虑到中国国旅较高的股息率以及免税店的火爆生意。建仓永辉超市,看好超市的消费升级。

比特币本月月底的变化值得一提,比特币的扩容问题一直是妨碍比特币成长的争议焦点,比特币核心开发组早前几个月就有人因为理念不一致愤怒的离开。目前的核心开发组希望增加一种称为闪电网络的特性,以侧链的方式来解决,而以部分矿工为代表的人,则希望简单的提升区块的大小。我在研究过两种方案后,个人倾向于矿工的解决方案,所谓的闪电网络提高了结算机构的地位,而提升区块大小则简单直接,至于提升区块大小被诟病的占磁盘空间大导致全节点会变少的问题,我觉得随着硬盘空间的变大并不是严重的问题,而且中本聪很早就给出了缩减容量的技术方案。因为本月底是算力对升级方案进行投票的重要节点,有消息称比特币将要分裂,因此币价遭到打压,我觉得分裂的风险很小,因此也小小玩了一把高抛低吸。目前币价又回归到了分裂消息之前的价格,如果这几个月平稳过渡,解决了容量问题,相信币价还有一波大的增长。此外,投入了部分比特币购买算力,参与挖矿活动。

拍拍贷完成了银行存管接入。将拍拍贷所有投资都变成了散标投资。拍拍贷散标累计年化收益率15.78%。

本月股票市值降低,比特币市值升高,总的来说净值和上月相比基本持平。

时间 净值 沪深300(比率)
20160101 1.0000 3470.41 (1.0000)
20161231 1.2526 3297.76 (0.9503)
20170126 1.2566 3387.96 (0.9762)
20170226 1.3245 3473.85 (1.0010)
20170331 1.3604 3456.05 (0.9959)
20170430 1.4060 3439.75 (0.9912)
20170531 1.5623 3492.88 (1.0065)
20170630 1.7505 3666.80 (1.0566)
20170731 1.7594 3737.87 (1.0771)

期末持仓品种:

  1. A股:贵州茅台、双汇发展、伊利股份、恒瑞医药、格力电器、美的集团、老板电器、苏泊尔、中国国旅、宇通客车、福耀玻璃、万科A、雅戈尔、平安银行、兴业银行、涪陵榨菜、中国建筑、海康威视、永辉超市、中国巨石。
  2. 基金:广发中证养老产业指数A、富国中证红利指数增强。
  3. 其他:拍拍贷散标、比特币。

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

最近几天在一些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;
            }
        }
    }

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

后记

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

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

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