青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 18,  comments - 104,  trackbacks - 0

了解C++的童鞋都知道algorithm里面有個next_permutation可以求下一個排列數,通過《STL 源碼剖析》(或者自己讀代碼)可以知道其實現,比如:

abcd  next_permutation ->  abdc

那么,為什么abcd的下一個是abdc而不是acbd呢?

說簡單一點,用 1,2,3,4 代替 a,b,c,d,可以得到:

原排列                  中間轉換                值
1,2,3,4        3,2,1            ((3 * (3) + 2) * (2) + 1) * (1) = 23
1,2,4,3        3,2,0            ((3 * (3) + 2) * (2) + 0) * (1) = 22
1,3,2,4        3,1,1            ((3 * (3) + 1) * (2) + 1) * (1) = 21
1,3,4,2        3,1,0            ((3 * (3) + 1) * (2) + 0) * (1) = 20
1,4,3,2        3,0,1            ((3 * (3) + 0) * (2) + 1) * (1) = 19
.                  .                     .
.                  .                     .
.                  .                     .
4,3,2,1        0,0,0            ((0 * (3) + 0) * (2) + 0) * (1) = 0
                               |      |      |                       |                    |                   |
                               |      |                              |                    |
                               |                                     |


 上面的中間轉換指的是:每一個數字后面比當前位數字大的數字的個數。比如:

1,3,4,2  中,1 后面有(3, 4, 2) 他們都大于1,所以第一位是 3
                              3 后面有(4, 2), 但只有4大于3,所以第二位是 1
                              4 后面有(2), 沒有比4 大的,所以第三位是 0
                              最后一位后面肯定沒有更大的,所以省略了一個0。

經過這種轉換以后,就得到了一種表示方式(中間轉換),這種表達方式和原排列一一對應,可以相互轉化。

仔細觀察這種中間表達方式,發現它的第一位只能是(0,1,2,3),第二位只能是(0,1,2),第三位只能是(0,1)。通常,數字是用十進制表示的,計算機中用二進制,但是現在,我用一種特殊的進制來表示數:

第一位用1進制,第二位用2進制。。。

于是就得到了這種中間表示方式的十進制值。如:

                                                              階                  
                                            |                  |                    |
1,1,0    ---->   ((1 * (3) + 1) * (2) + 0) * (1) = 8

3,1,0    ---->   ((3 * (3) + 1) * (2) + 0) * (1) = 20

這樣,就可以得到一個十進制數和一個排列之間的一一對應的關系。
現在排列數和有序的十進制數有了一一對應的關系(通過改變對應關系,可以使十進制數升序)。

到這里已經可以很容易的得到任意一個排列了,但是還沒有完,這種不定進制還有其他用處:

在寫程序的時候,很容易遇到一種情況就是:有好幾種類別的狀態需要存儲,但是對象的數量過大,需要對這種狀態表示方式進行壓縮。比如:

enum A{
A_1,
A_2,
A_3,
};

enum B{
B_1,
B_2,
B_3,
B_4,
B_5,
};

struct State{
A a : 2;
B b : 3;
};

其實 a 可以表示4個狀態,b可以表示8個狀態,因為State總共有3×5=15,也就是說4位就足夠了,這里多用了1位(當然有人可能會說,現在內存這么大,誰在乎1bit呀,告訴你,我在乎!),不考慮對齊。

下面用上面介紹的方法來壓縮:
A 有3種狀態,B有5種狀態,那么如果把A放在高位,那么對于一個狀態(注意enum從0開始):
(A_3,B_3),就是2×5+3=13
(A_2,B_5),就是1×5+4=9

(A_1,B_1),就是0×5+0=0
(A_3,B_5),就是2×5+4=14

這樣就可以節省1bit啦。如果這個State有1M個,那就可以節省1M內存如果有1G呢,就省1G啦,有些時候,這種表示狀態的小對象,充斥在程序的各個角落。

從數字到狀態也很容易,就像進制轉換一樣先除,再模,就OK了。

總結下:

    先說了next_permutation的問題,引出排列的另一種表達方式,然后引入了一種不定進制的表示將其轉化為十進制數字,從而使的排列數和有序的十進制數一一對應起來。
    從這種不定進制的表示方式,描述一種壓縮狀態的方法。
posted on 2010-02-24 00:11 尹東斐 閱讀(3440) 評論(7)  編輯 收藏 引用

FeedBack:
# re: next_permutation, next, next, next...
2010-02-24 05:23 | 孟布
很好。。。  回復  更多評論
  
# re: next_permutation, next, next, next...
2010-02-24 09:53 | 凡客50元優惠卷
好  回復  更多評論
  
# re: next_permutation, next, next, next...
2010-02-24 18:56 | jimmy
那個括號里面的話很拽誒~~ 哈哈哈~~~  回復  更多評論
  
# re: next_permutation, next, next, next...
2010-02-25 10:05 | 凡客誠品
很好123456  回復  更多評論
  
# re: next_permutation, next, next, next...
2011-08-14 08:58 | leaf
(A_3,B_3),就是2×5+2=12
這里應該是這樣  回復  更多評論
  
# re: next_permutation, next, next, next...
2013-11-22 20:51 | 一夢
很好,很強大!  回復  更多評論
  
# re: next_permutation, next, next, next...
2013-11-22 20:55 | 一夢
恩是的 呵呵@leaf
  回復  更多評論
  
<2013年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用鏈接

留言簿(4)

隨筆檔案

文章分類

文章檔案

相冊

好友博客

搜索

  •  

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            国产综合色一区二区三区| 久久免费国产| 国产精品国产三级国产专区53| 亚洲精品一区二区三区在线观看 | 狠狠色噜噜狠狠狠狠色吗综合| 久久精品视频在线播放| 久久欧美中文字幕| 亚洲欧洲日产国产网站| 99精品视频网| 国模私拍视频一区| 91久久久久久久久| 欧美三级小说| 久久人人看视频| 欧美国产先锋| 亚洲欧美成人一区二区三区| 久久国产视频网站| aa成人免费视频| 欧美伊人久久大香线蕉综合69| 亚洲国产日韩欧美在线图片| 日韩视频在线永久播放| 黑人巨大精品欧美一区二区 | 欧美国产视频在线| 欧美午夜精品电影| 美女主播一区| 国产精品入口夜色视频大尺度| 久久伊人免费视频| 国产精品yjizz| 欧美电影免费观看网站| 国产毛片一区二区| 亚洲欧洲三级电影| 国产综合色在线| 亚洲手机成人高清视频| 亚洲人体偷拍| 久久久久久久综合| 欧美一区二区精品久久911| 欧美精品成人在线| 欧美成人午夜| 国语自产精品视频在线看一大j8| 一区二区电影免费在线观看| 在线日韩欧美| 久久国产精品久久久久久久久久| 亚洲夜晚福利在线观看| 欧美国产视频日韩| 欧美成人综合在线| 黄网站免费久久| 亚洲愉拍自拍另类高清精品| 在线视频一区二区| 欧美黄色日本| 亚洲高清视频一区| 亚洲黄网站黄| 可以免费看不卡的av网站| 久久久欧美精品| 欧美日韩一级黄| 欧美性视频网站| 亚洲精品免费一区二区三区| 1024成人| 久久综合九色欧美综合狠狠| 久久久久欧美精品| 国产一区二区三区在线观看精品 | 亚洲黄色在线视频| 亚洲精品久久久久久久久久久久久| 久久精品国产亚洲一区二区| 久久人人精品| 悠悠资源网亚洲青| 免费一级欧美片在线播放| 欧美大片专区| 日韩一级大片| 欧美色精品天天在线观看视频| 亚洲精品韩国| 亚洲欧美日韩综合一区| 国产精品视频yy9099| 午夜在线精品偷拍| 美女脱光内衣内裤视频久久影院 | 亚久久调教视频| 国产日韩欧美在线播放| 久久国产精品99精品国产| 久久久亚洲高清| 亚洲精品1区2区| 欧美日韩亚洲天堂| 亚洲欧美欧美一区二区三区| 久久精品国产一区二区三| 一区二区三区在线不卡| 欧美高清不卡在线| 中文av一区二区| 久久久久久久久久久久久久一区 | 欧美韩日高清| 亚洲小说区图片区| 含羞草久久爱69一区| 蜜乳av另类精品一区二区| 亚洲日韩成人| 欧美资源在线观看| 亚洲激情校园春色| 欧美天堂在线观看| 久久精品国产久精国产爱| 欧美韩国在线| 性欧美大战久久久久久久免费观看| 国内精品国语自产拍在线观看| 欧美韩日精品| 久久国产视频网| 99精品久久| 免费成人在线观看视频| 亚洲一区久久久| 在线 亚洲欧美在线综合一区| 欧美日韩亚洲不卡| 老司机午夜精品视频| 亚洲视频在线观看| 亚洲人成久久| 美女尤物久久精品| 欧美一级久久| 99精品欧美| 精品1区2区3区4区| 国产精品久久久久久久第一福利| 久久久视频精品| 亚洲欧美另类久久久精品2019| 亚洲韩国日本中文字幕| 亚洲一区bb| 性欧美长视频| 亚洲国产精品久久久久婷婷884 | 伊人久久成人| 国产精品免费看片| 欧美日韩国产综合视频在线观看中文| 欧美一区二区在线观看| 一区二区激情小说| 亚洲精品小视频| 欧美激情网友自拍| 免费久久精品视频| 久久精品99国产精品酒店日本| 亚洲午夜电影网| 在线视频一区观看| aa级大片欧美三级| 亚洲乱码国产乱码精品精| 亚洲电影av| 亚洲黄色av| 91久久夜色精品国产网站| 在线观看欧美精品| 激情综合自拍| 1769国产精品| 亚洲福利专区| 亚洲欧洲一区二区三区久久| 亚洲福利视频一区| 亚洲国产一区视频| 亚洲精品视频啊美女在线直播| 亚洲国内自拍| 99re6热在线精品视频播放速度| 亚洲精品久久在线| 亚洲美女精品久久| 中文国产一区| 性欧美1819性猛交| 久久精品电影| 欧美成人网在线| 亚洲精品日产精品乱码不卡| 亚洲欧洲一区二区在线观看| 亚洲乱码日产精品bd| 亚洲一区二区三区四区中文| 亚洲欧美日韩精品一区二区| 欧美一区二区三区播放老司机| 久久国产免费| 男女激情视频一区| 欧美视频在线观看免费| 国产精品久久久久久久久婷婷| 国产欧美在线视频| 在线成人国产| 日韩视频在线免费观看| 亚洲在线日韩| 久久精品国产亚洲一区二区| 欧美成人激情在线| 9色精品在线| 久久精品色图| 欧美日韩二区三区| 国产一区二区视频在线观看| 亚洲欧洲综合另类在线| 亚洲砖区区免费| 欧美成人有码| 亚洲永久免费观看| 美女国内精品自产拍在线播放| 欧美日韩成人在线| 影音先锋亚洲精品| 亚洲影院一区| 亚洲电影天堂av| 亚洲在线一区| 欧美二区在线| 国产一区二区三区在线免费观看| 亚洲看片一区| 久久男人av资源网站| 一区二区不卡在线视频 午夜欧美不卡在 | 在线精品视频一区二区三四| 日韩视频免费在线| 久久国产欧美| 亚洲看片一区| 久久久久在线观看| 国产女主播一区二区| 艳女tv在线观看国产一区| 久久精品欧美日韩精品| 亚洲最新在线视频| 欧美黄色大片网站| 樱桃成人精品视频在线播放| 午夜一区二区三区在线观看| 亚洲精品欧美激情| 蜜臀va亚洲va欧美va天堂| 国产一区99|