欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

僅利用30行Python代碼來展示X算法

 更新時(shí)間:2015年04月01日 17:08:54   作者:Ali Assaf  
這篇文章主要介紹了僅利用30行Python代碼來展示X算法,同時(shí)還有對算法實(shí)現(xiàn)的復(fù)雜度的說明,需要的朋友可以參考下

假如你對數(shù)獨(dú)解法感興趣,你可能聽說過精確覆蓋問題。給定全集 X 和 X 的子集的集合 Y ,存在一個(gè) Y 的子集 Y*,使得 Y* 構(gòu)成 X 的一種分割。

這兒有個(gè)Python寫的例子。
 

X = {1, 2, 3, 4, 5, 6, 7}
Y = {
  'A': [1, 4, 7],
  'B': [1, 4],
  'C': [4, 5, 7],
  'D': [3, 5, 6],
  'E': [2, 3, 6, 7],
  'F': [2, 7]}

這個(gè)例子的唯一解是['B', 'D', 'F']。

精確覆蓋問題是NP完備(譯注:指沒有任何一個(gè)夠快的方法可以在合理的時(shí)間內(nèi),意即多項(xiàng)式時(shí)間 找到答案)。X算法是由大牛高德納發(fā)明并實(shí)現(xiàn)。他提出了一種高效的實(shí)現(xiàn)技術(shù)叫舞蹈鏈,使用雙向鏈表來表示該問題的矩陣。

然而,舞蹈鏈實(shí)現(xiàn)起來可能相當(dāng)繁瑣,并且不易寫地正確。接下來就是展示Python奇跡的時(shí)刻了!有天我決定用Python來編寫X 算法,并且我想出了一個(gè)有趣的舞蹈鏈變種。
算法

主要的思路是使用字典來代替雙向鏈表來表示矩陣。我們已經(jīng)有了 Y。從它那我們能快速的訪問每行的列元素。現(xiàn)在我們還需要生成行的反向表,換句話說就是能從列中快速訪問行元素。為實(shí)現(xiàn)這個(gè)目的,我們把X轉(zhuǎn)換為字典。在上述的例子中,它應(yīng)該寫為
 

X = {
  1: {'A', 'B'},
  2: {'E', 'F'},
  3: {'D', 'E'},
  4: {'A', 'B', 'C'},
  5: {'C', 'D'},
  6: {'D', 'E'},
  7: {'A', 'C', 'E', 'F'}}

眼尖的讀者能注意到這跟Y的表示有輕微的不同。事實(shí)上,我們需要能快速刪除和添加行到每列,這就是為什么我們使用集合。另一方面,高德納沒有提到這點(diǎn),實(shí)際上整個(gè)算法中所有行是保持不變的。

以下是算法的代碼。
 

def solve(X, Y, solution=[]):
  if not X:
    yield list(solution)
  else:
    c = min(X, key=lambda c: len(X[c]))
    for r in list(X[c]):
      solution.append(r)
      cols = select(X, Y, r)
      for s in solve(X, Y, solution):
        yield s
      deselect(X, Y, r, cols)
      solution.pop()
 
def select(X, Y, r):
  cols = []
  for j in Y[r]:
    for i in X[j]:
      for k in Y[i]:
        if k != j:
          X[k].remove(i)
    cols.append(X.pop(j))
  return cols
 
def deselect(X, Y, r, cols):
  for j in reversed(Y[r]):
    X[j] = cols.pop()
    for i in X[j]:
      for k in Y[i]:
        if k != j:
          X[k].add(i)

真的只有 30 行!
格式化輸入

在解決實(shí)際問題前,我們需要將輸入轉(zhuǎn)換為上面描述的格式??梢赃@樣簡單處理

X = {j: set(filter(lambda i: j in Y[i], Y)) for j in X}

但這樣太慢了。假如設(shè) X 大小為 m,Y 的大小為 n,則迭代次數(shù)為 m*n。在這例子中的數(shù)獨(dú)格子大小為 N,那需要 N^5 次。我們有更好的辦法。
 

X = {j: set() for j in X}
for i in Y:
  for j in Y[i]:
    X[j].add(i)

這還是 O(m*n) 的復(fù)雜度,但是是最壞情況。平均情況下它的性能會(huì)好很多,因?yàn)樗恍枰闅v所有的空格位。在數(shù)獨(dú)的例子中,矩陣中每行恰好有 4 個(gè)條目,無論大小,因此它有N^3的復(fù)雜度。
優(yōu)點(diǎn)

  •     簡單: 不需要構(gòu)造復(fù)雜的數(shù)據(jù)結(jié)構(gòu),所有用到的結(jié)構(gòu)Python都有提供。
  •     可讀性: 上述第一個(gè)例子是直接從Wikipedia上的范例直接轉(zhuǎn)錄下來的!
  •     靈活性: 可以很簡單得擴(kuò)展來解決數(shù)獨(dú)。

求解數(shù)獨(dú)

我們需要做的就是把數(shù)獨(dú)描述成精確覆蓋問題。這里有完整的數(shù)獨(dú)解法代碼,它能處理任意大小,3×3,5×5,即使是2×3,所有代碼少于100行,并包含doctest?。ǜ兄xWinfried Plappert 和 David Goodger的評論和建議)

相關(guān)文章

  • 學(xué)習(xí)Python,你還不知道m(xù)ain函數(shù)嗎

    學(xué)習(xí)Python,你還不知道m(xù)ain函數(shù)嗎

    Python?中的?main?函數(shù)充當(dāng)程序的執(zhí)行點(diǎn),在?Python?編程中定義?main?函數(shù)是啟動(dòng)程序執(zhí)行的必要條件。本文就來帶大家深入了解一下main函數(shù),感興趣的可以了解一下
    2022-09-09
  • 使用Python將xmind腦圖轉(zhuǎn)成excel用例的實(shí)現(xiàn)代碼(一)

    使用Python將xmind腦圖轉(zhuǎn)成excel用例的實(shí)現(xiàn)代碼(一)

    這篇文章主要介紹了使用Python將xmind腦圖轉(zhuǎn)成excel用例的實(shí)現(xiàn)代碼(一),本文給大家介紹的非常詳細(xì)對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2020-10-10
  • 看看如何用Python繪制小米新版天價(jià)logo

    看看如何用Python繪制小米新版天價(jià)logo

    這篇文章主要介紹了看看如何用Python繪制小米新版天價(jià)logo,幫助大家更好的理解和學(xué)習(xí)使用python,感興趣的朋友可以了解下
    2021-04-04
  • python面試題之列表聲明實(shí)例分析

    python面試題之列表聲明實(shí)例分析

    這篇文章主要介紹了python面試題之列表聲明,結(jié)合實(shí)例形式分析了Python列表的聲明、計(jì)算相關(guān)操作技巧,需要的朋友可以參考下
    2019-07-07
  • python 中的列表解析和生成表達(dá)式

    python 中的列表解析和生成表達(dá)式

    優(yōu)雅、清晰和務(wù)實(shí)都是python的核心價(jià)值觀,如果想通過操作和處理一個(gè)序列(或其他的可迭代對象)來創(chuàng)建一個(gè)新的列表時(shí)可以使用列表解析( List comprehensions)和生成表達(dá)式,通過這兩個(gè)操作,我們可以看到這三個(gè)觀點(diǎn)是如何在python中和諧統(tǒng)一起來的。
    2011-03-03
  • jupyter默認(rèn)工作目錄的更改方法

    jupyter默認(rèn)工作目錄的更改方法

    jupyter notebook是一個(gè)以網(wǎng)頁形式來使用的python編輯器,很多小伙伴在第一次安裝它的時(shí)候選擇的都是默認(rèn)安裝,那么jupyter默認(rèn)工作目錄如何更改,本文就來介紹一下
    2023-08-08
  • Jmeter并發(fā)執(zhí)行Python 腳本的完整流程

    Jmeter并發(fā)執(zhí)行Python 腳本的完整流程

    這篇文章主要介紹了Jmeter并發(fā)執(zhí)行 Python 腳本的問題詳解,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-09-09
  • 關(guān)于NumPy中asarray的用法及說明

    關(guān)于NumPy中asarray的用法及說明

    這篇文章主要介紹了關(guān)于NumPy中asarray的用法及說明,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-07-07
  • 最新評論