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

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 尹東斐 閱讀(3441) 評論(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
  回復  更多評論
  
<2010年2月>
31123456
78910111213
14151617181920
21222324252627
28123456
78910111213

常用鏈接

留言簿(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>
            99热在这里有精品免费| 一本高清dvd不卡在线观看| 亚洲欧美日韩系列| 亚洲图片自拍偷拍| 国产精品嫩草影院av蜜臀| 欧美一区二视频| 久久精品国产精品亚洲综合| 亚洲承认在线| 亚洲毛片播放| 国产亚洲一本大道中文在线| 美女91精品| 欧美日韩一视频区二区| 亚洲伊人第一页| 久久黄金**| 一本色道久久88综合亚洲精品ⅰ | 欧美中文在线字幕| 久久伊人亚洲| 一本色道久久加勒比精品| 亚洲一区二区三区高清不卡| 一区在线影院| 99在线热播精品免费| 国产一区二区三区在线观看网站 | 亚洲视频中文字幕| 在线观看日韩av电影| 一本色道88久久加勒比精品| 国产毛片久久| 欧美激情91| 国产精品系列在线| 亚洲第一偷拍| 国产乱码精品一区二区三区五月婷 | 性伦欧美刺激片在线观看| 亚洲免费福利视频| 欧美一站二站| 亚洲一区在线看| 欧美高清在线一区| 久久久亚洲精品一区二区三区| 欧美片在线观看| 欧美mv日韩mv国产网站| 国产精品日韩精品欧美在线| 亚洲韩国青草视频| 激情小说另类小说亚洲欧美| 国产精品狼人久久影院观看方式| 亚洲天堂成人| 欧美凹凸一区二区三区视频| 久久大逼视频| 欧美性猛交一区二区三区精品| 牛夜精品久久久久久久99黑人| 国产精品视频九色porn| 亚洲精选一区| 亚洲国产高清一区| 久久九九99视频| 久久九九免费| 国产日韩欧美成人| 亚洲欧美日本伦理| 午夜一区二区三区不卡视频| 欧美日韩国产一级片| 亚洲激情影院| 最新成人av网站| 欧美va亚洲va日韩∨a综合色| 久久综合久久综合这里只有精品 | 国产麻豆91精品| 亚洲综合国产| 久久精品国产久精国产思思| 国产日韩欧美高清免费| 欧美一区二区三区免费观看视频| 午夜宅男久久久| 国产精品素人视频| 午夜精品电影| 久久综合色88| 亚洲国产精品视频一区| 欧美韩日高清| 日韩亚洲精品在线| 亚洲一区二区三区影院| 欧美午夜激情在线| 亚洲欧美欧美一区二区三区| 欧美在线免费视频| 亚洲第一二三四五区| 欧美高清影院| 中日韩美女免费视频网站在线观看| 亚洲一级在线观看| 国产情人综合久久777777| 午夜精品一区二区三区在线播放| 久久精品视频在线观看| 精品二区久久| 欧美久久久久久蜜桃| 亚洲午夜激情网站| 裸体女人亚洲精品一区| 亚洲精品系列| 国产精品美女久久久久av超清 | 在线亚洲成人| 蜜桃av综合| 亚洲一区二区三区四区在线观看 | 欧美电影在线观看| 亚洲婷婷综合久久一本伊一区| 国产精品色午夜在线观看| 久久精品官网| 99精品热视频只有精品10| 久久尤物视频| 亚洲永久免费av| 在线看视频不卡| 国产精品毛片大码女人| 欧美18av| 在线观看国产欧美| 136国产福利精品导航| 牛牛影视久久网| 亚洲综合日本| 亚洲黑丝在线| 久久精品av麻豆的观看方式 | 精品电影在线观看| 欧美日韩中文字幕在线视频| 久久久女女女女999久久| 在线一区二区三区四区| 亚洲高清网站| 久久婷婷久久| 欧美一区二区高清在线观看| 99精品国产高清一区二区| 加勒比av一区二区| 国产美女精品视频免费观看| 欧美精品福利在线| 久久一区中文字幕| 久久国产精品久久精品国产| 一区二区电影免费在线观看| 亚洲国产日韩欧美| 欧美福利视频网站| 免费成人av在线看| 久久久www成人免费精品| 香蕉久久夜色精品国产| 亚洲欧美日韩国产精品| 亚洲视频精选在线| 夜夜嗨一区二区| 亚洲精品永久免费精品| 亚洲国产精品久久精品怡红院| 国产人久久人人人人爽| 国产精品欧美一区二区三区奶水| 欧美肉体xxxx裸体137大胆| 欧美日韩国产一区| 欧美日韩亚洲一区二| 欧美激情综合色| 欧美美女福利视频| 欧美精品亚洲精品| 欧美日韩一区高清| 欧美三级视频在线观看| 欧美日在线观看| 国产精品日韩欧美大师| 国产精品亚洲аv天堂网| 国产精品亚洲片夜色在线| 国产日韩欧美视频| 极品少妇一区二区| 亚洲精品国产精品久久清纯直播 | 国产一区二区久久久| 海角社区69精品视频| 一区二区三区在线观看视频| 黄色国产精品| 亚洲人成小说网站色在线| 99精品热视频只有精品10| 在线一区免费观看| 亚洲欧美久久久| 久久精品国产第一区二区三区最新章节 | 中国女人久久久| 亚欧成人在线| 六月婷婷一区| 国产精品a级| 国内外成人在线| 亚洲激情视频网站| 亚洲欧美第一页| 久久免费偷拍视频| 亚洲国产综合在线| 亚洲欧美日韩国产精品| 狂野欧美一区| 国产精品高潮在线| 悠悠资源网久久精品| 日韩一二在线观看| 久久成人一区二区| 亚洲人成人99网站| 在线看无码的免费网站| 欧美尤物巨大精品爽| 亚洲男女自偷自拍| 欧美成人精品| 亚洲一区免费网站| 麻豆国产精品一区二区三区| 国产精品地址| 亚洲韩日在线| 久久九九99视频| 99re在线精品| 开元免费观看欧美电视剧网站| 欧美日韩一区二区三区免费看| 国产资源精品在线观看| 亚洲一区综合| 亚洲国产日韩在线一区模特| 久久www成人_看片免费不卡| 欧美日韩免费观看一区二区三区| 国产在线不卡精品| 亚洲在线观看| 亚洲经典在线看| 久久婷婷丁香| 国产一区二区三区久久 | 亚洲男人第一网站| 欧美日韩国产页| 亚洲精一区二区三区| 久久亚洲视频|