<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    where the amazing happens

    全排列和其他

    昨天上午去面試的一道題,當場沒想出來,回來花了點時間補完了下發回去.

    原題要求用java,用python只是為了方便。用回溯法快,但是還是堅持用遍歷森林來寫,這也是面試時沒想完的思路,呵呵,我就是自找麻煩的硬石頭性格。

    最先想到用無向連通圖進行深度優先搜索,但是沒有考慮到結束條件。對于N個待排列的數字,每個節點都有N-1個出口和入口,而用樹狀結構每個節點只有一個父節點,存在遞歸返回的條件。但是這個方法的實用性只限制在當排列數很少(N < 8)時。當N>8時算法消耗的時間明顯增加(一共8*7*6*5*4*3*2*1=40320種組合),當N>1000時(當然,這種情況是不敢想像的)就會達到python的遞歸極限。所以真正如果要干點什么的話(當然,高中生都知道全排列拿52張撲克牌出來排一下結果集就是個天文數字),這顯然不是個好算法。


    #coding=utf-8

    # 數字全排列
    #
    Chris Zheng 2007-06-05

    import sys, os


    #待排列的數字
    NUMS = [1,2,3,4,5,6]

    #結果集合
    results = []

    EXCLUDES
    = (
    lambda a,b,nums:abs(nums.index(a) - nums.index(b)) == 1, #a,b是否相鄰
    lambda a,b,idx_a,idx_b,nums:nums.index(a) == idx_a and nums.index(b) \
    == idx_b #a,b是否同時符合特定位置
    )

    # 3和4不能相鄰 當2在第1時6不能在第7
    EXT_PARAMS = (
    (
    3,4,NUMS),(2,6,1,7,NUMS)
    )

    #檢查排除條件
    def __check_conditions(nums):
    matchs
    = False
    for f in EXCLUDES:
    for params in EXT_PARAMS:
    try:
    params[
    -1] = nums
    matchs
    = f(*params)
    if matchs: return matchs
    except Exception:continue
    return matchs

    #樹節點
    class node(object):
    def __init__(self, n):
    self.value
    = n
    self.parent
    = None
    self.children
    = []
    def __eq__(self,other):
    return self.value == other.value
    def __str__(self):return str(self.value)

    #主方法
    def get_all(nums):
    trees
    = []
    for n in nums:
    trees.append(create_tree(node(n)))
    for t in trees:
    walk_tree(t)
    global results
    #過濾條件
    return (r for r in results if not __check_conditions(r))

    #生成結果樹
    def create_tree(root):
    parent_elements
    = __parents(root)
    if len(parent_elements) == len(NUMS)+1:return root
    nums
    = (nums for nums in NUMS if node(nums) not in parent_elements)
    for k in nums:
    c
    = node(k)
    c.parent
    = root
    root.children.append(create_tree(c))
    return root

    def __parents(node):
    parent_elements
    = [node]
    while node.parent:
    parent_elements.append(node.parent)
    node
    = node.parent
    return parent_elements

    #遍歷結果樹
    def walk_tree(root):
    if root.children:
    for n in root.children:
    walk_tree(n)
    else:
    k
    = [root.value]
    p
    = root.parent
    while p:
    k.append(p.value)
    p
    = p.parent
    k.reverse()
    results.append(k)

    #測試輸出
    if __name__=='__main__':
    rs
    = get_all(NUMS)
    f
    = open('results.txt','w')
    for k in rs:
    f.write(str(k)
    +'\n')
    f.close()


    .


    posted on 2007-06-05 14:47 where the amazing happens 閱讀(431) 評論(0)  編輯  收藏 所屬分類: 算法&數據結構


    只有注冊用戶登錄后才能發表評論。


    網站導航:
    博客園   IT新聞   Chat2DB   C++博客   博問  
     

    公告

    點擊這里給我發消息

    導航

    <2007年6月>
    272829303112
    3456789
    10111213141516
    17181920212223
    24252627282930
    1234567

    統計

    常用鏈接

    留言簿(3)

    隨筆分類(18)

    隨筆檔案(17)

    文章分類

    相冊

    其他我的blog

    技術Blog

    最新隨筆

    搜索

    最新評論

    閱讀排行榜

    評論排行榜

    主站蜘蛛池模板: 亚洲一级黄色大片| 亚洲麻豆精品国偷自产在线91| 美腿丝袜亚洲综合| 污网站在线免费观看| 国产乱弄免费视频| 亚洲乱色伦图片区小说| 天天天欲色欲色WWW免费| 亚洲六月丁香婷婷综合| 无码免费午夜福利片在线| 久久亚洲AV无码精品色午夜麻豆| 久久青草免费91观看| 蜜芽亚洲av无码精品色午夜| 一级特黄aa毛片免费观看| 久久久久亚洲Av无码专| 69成人免费视频| 亚洲GV天堂GV无码男同| 国产大片91精品免费观看男同| 老司机午夜免费视频| 国产L精品国产亚洲区久久| 中文字幕视频在线免费观看| 久久精品九九亚洲精品天堂| 91青青青国产在观免费影视| 亚洲最大在线观看| 免费毛片网站在线观看| 免费精品国产自产拍在线观看| 国产午夜亚洲精品午夜鲁丝片| 日本免费一区二区三区四区五六区 | 精品亚洲成AV人在线观看| 无码区日韩特区永久免费系列 | 性色av无码免费一区二区三区| 亚洲第一第二第三第四第五第六| 免费A级毛片无码久久版| a级片免费在线播放| 亚洲欧洲久久精品| 婷婷亚洲天堂影院| 午夜免费啪视频在线观看 | 丰满亚洲大尺度无码无码专线| 亚洲伊人久久成综合人影院| 99精品视频在线观看免费播放 | 最近高清中文字幕免费| 亚洲国产成人手机在线观看|