• <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>
            隨筆 - 6, 文章 - 0, 評論 - 24, 引用 - 0
            數(shù)據(jù)加載中……

            Permutation—全排列

            Permutation—全排列

            l  簡介

            一個全排列是從一個有限集中選取元素,組成一個有序的序列,并且所有的元素出現(xiàn)且僅出現(xiàn)一次。

            l  全排列的計數(shù)

            n  當集合中元素互異時,顯然全排列總共有n!個。

            n  現(xiàn)在考慮集合中存在重復元素的情況:

            1.     我們首先看一個簡單的例子。

            2.        設例子中的全排列數(shù)為P,那么我們將這P個排列中重復的元素1看成互異的,假設標記為11’,那么對于每種排列都能生成P(2) = 2!個惟一的新排列,而這些新排列恰好構(gòu)成了3個互異元素的全排列,因此P = P(3) ÷P(2) = 3

            3.        假設n個元素的多重集合中有m個互異的元素,各元素出現(xiàn)的次數(shù)分別為a1, a2, … , am,且滿足(a1 + a2 + … + am) = n那么這個集合形成的全排列個數(shù)為

            4.        m = n時,上式的結(jié)果即為n!

            l  生成全排列

            n  遞推生成:每次輸出當前序列的下個全排列,直到生成所有全排列。

            1.     按字典序生成:生成輸入序列按字典序的下個全排列。

            l  尋找從序列A末尾開始的最長非增連續(xù)子列S。保存子列S之前的一個元素為a,在上圖中,S = { 6, 5, 1 }a = 4

            l  容易看出S是其元素的字典序最大全排列,如圖中的{ 6, 5, 1 },因此無法通過在S內(nèi)部交換元素得到A的下個字典序全排列,因此只需找出a + S,即序列{ 4, 6, 5, 1 }中的下個全排列。從序列末尾開始,尋找第一個大于a的元素b,如圖中的5,交換ab。這樣我們更新了S之前的一個元素,只要將S變?yōu)槠湓氐?span style="COLOR: #4f81bd; mso-themecolor: accent1">字典序最小全排列即可得到A的下個字典序全排列;

            l  翻轉(zhuǎn)S,由于S非增的(交換ab后還是如此),那么翻轉(zhuǎn)后自然變成非減序列,即其元素的字典序最小全排列

            l  以上算法即C++std::next_permutation函數(shù)的實現(xiàn)。

            2.     無序生成:生成輸入序列的下個全排列,各全排列間并不遵循特定的順序。

            未完,待續(xù)……

            posted on 2009-03-30 20:56 yuyang7 閱讀(2406) 評論(0)  編輯 收藏 引用 所屬分類: 算法

            久久九九久精品国产免费直播| 久久综合一区二区无码| 久久精品国产99国产精偷| 国产2021久久精品| 一级女性全黄久久生活片免费 | 久久综合久久综合久久| 久久久久久久国产免费看| 久久精品无码专区免费东京热 | 久久久久无码国产精品不卡| 伊人久久综合精品无码AV专区| MM131亚洲国产美女久久| 狠狠色综合网站久久久久久久| 精品人妻伦九区久久AAA片69| 国产精品九九久久精品女同亚洲欧美日韩综合区 | 无码8090精品久久一区| 俺来也俺去啦久久综合网| 一本综合久久国产二区| 久久AⅤ人妻少妇嫩草影院| AAA级久久久精品无码片| 国产成人久久久精品二区三区| 人人狠狠综合久久88成人| 久久天天躁狠狠躁夜夜av浪潮| 99久久无码一区人妻a黑| 色婷婷久久久SWAG精品| 久久精品国产精品亜洲毛片| 国产成人99久久亚洲综合精品| 久久青青草原亚洲av无码app | 精品无码久久久久久午夜| 狠狠色丁香久久婷婷综合| 中文字幕无码久久精品青草| 国产午夜精品久久久久九九电影| 午夜精品久久久久久毛片| 蜜臀久久99精品久久久久久小说| 久久久久久久97| 久久国语露脸国产精品电影| 伊人久久大香线蕉精品不卡| 亚洲精品久久久www| 国产精品久久久久久久app| 亚洲色大成网站WWW久久九九| 新狼窝色AV性久久久久久| 国色天香久久久久久久小说|