iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 24
2
Software Development

活用python- 路遙知碼力,日久練成精系列 第 24

Day24- 魔鏡啊魔鏡,誰是列表中最美麗的元素? (任意規則的排序方法)

路遙知碼力,日久練成精- 只要在程式之路鑽研的夠深,便能夠充分發揮程式碼的力量; 練習的日子夠久,便能夠練成寫出精簡代碼的能力。

大家好,我是心原一馬,
昨天談到說如何視覺化的將數獨的解答印出來,
這邊提供一個參考解法:
(還沒看過題目的朋友歡迎點昨日題目傳送門)

sudoku= \
["5","3",".",".","7",".",".",".",".",
 "6",".",".","1","9","5",".",".",".",
 ".","9","8",".",".",".",".","6",".",
 "8",".",".",".","6",".",".",".","3",
 "4",".",".","8",".","3",".",".","1",
 "7",".",".",".","2",".",".",".","6",
 ".","6",".",".",".",".","2","8",".",
 ".",".",".","4","1","9",".",".","5",
 ".",".",".",".","8",".",".","7","9"]
 
ans = solveSudoku(S) # solveSudoku這個函數於昨天的程式有定義
for a in ans:
    for i in range(9):
        print(s[i*9:i*9+9])
    print('---------------') #若有多組解答畫個分隔線

那麼我們進入正題囉,
我們都知道排序
但你知道任意規則的排序方法嗎?

排序規則由你定義

今天要再次跟大家介紹python內建的sorted()函數囉。
蛤?你說排序不就把數字從小排到大嗎?
這有什麼學問嗎?
不不,真實世界的排序比這個複雜多了,
排序規則我們可以隨意訂的。
比如說撲克牌的排序啦,
比如說大學聯考原始分數較低,
但是因為有某些科目有加權分數使排名在前啦,
或者有一句話不是說「情人眼裡出西施」嗎?
人們對於「美」的排序也許自動把「男女朋友」排第一順位。
究竟寫程式會碰到什麼千奇百怪的排序規則,讓我們來看看。

似魔鏡般的key函數

開始看範例之前,還是先簡介一下語法:

sorted(arr, key= 函數)

參數key可以傳進一個函數,
我們要對arr裡面的元素進行排序,返回列表(list),
但是比較的值是透過key函數轉換得到的值。
key傳進的函數可以將arr裡的元素轉為任何可以比較的結果,
例如: 數字、字串、元組。
這樣講好像有點抽象,我們實際看例子:
譬如說現在我們想要對"elephant", "lion", "tiger"
這三個字串做排序,但不是直接對字串本身做排序,
而是想對字串的長度做排序,如圖示:

https://ithelp.ithome.com.tw/upload/images/20190926/20117114iI5w3EE8iF.png

你可以把key函數想成是一個魔鏡,
透過key函數的映射後,會照出每個元素真正要拿來排序的值。
(圖示: 字串"elephant"長度=8,字串"lion"長度=4、字串"tiger"長度=5)
最後再以這個映射後的數值做排序,如下圖:
https://ithelp.ithome.com.tw/upload/images/20190926/20117114STptBt09EI.png

附上對應的程式供大家參考:

arr = ["elephant", "lion", "tiger"]
print(sorted(arr, key=len))

結果為: ['lion', 'tiger', 'elephant']

技巧1: key參數與lambda的組合技

既然key參數是要傳入一個函數,
我們常常會與Day14所教過的匿名函數lambda
幫助我們更方便的定義排序函數。
比如說我們有一個整數陣列[36,88,125,19]
希望的排序規則是個位數愈大的數字排愈後面,
也就是說除以10餘數愈大的數字排愈後面,
我們程式便可以這樣寫:

arr = [36,88,125,19]
print(sorted(arr, key= lambda x: x%10))

結果為: [125, 36, 88, 19]

技巧2: 將排序值映射為元組

比如一樣剛剛這個陣列[36,88,125,19]
現在我們規定,偶數永遠排在奇數後面,
若奇偶性相同再比尾數大小。
像這種並非只有「單一標準」的排序,
而是有不同優先次序標準的排序,
我們便可以利用把排序值映射為元組的技巧,
將優先次序愈高的屬性放在元組愈前面的位置
程式如下:

arr = [36,88,125,19]
print(sorted(arr,key= lambda x: (x%2==0, x%10)))

結果為: [125, 19, 36, 88]

若一時之間覺得不好理解的話,
你可以寫個列表生成式實際看每個元素的映射值,
範例如下:

arr = [36,88,125,19]
print([(x%2==0, x%10) for x in arr]) 

結果為[(True, 6), (True, 8), (False, 5), (False, 9)]
因為TrueFalse還大,
所以在此規則中,88>36>19>125
我們繼續看更多生動的例子增加感覺吧。

範例24-1 我的喜好由我定義

小新生日的那天收到了許多喜歡的禮物,
以一個列表表示他的禮物:

gifts = ["動感超人", "巧克力餅乾", "球鞋", "百科全書"]

在小新的心目中,
他對每個禮物亦有一個數字,
量化他對這個禮物的喜歡程度,
(由於小新可能也會不小心收到討厭的禮物,這個數字也可能是負值)
以一個字典表示它:

likes = {"動感超人": 2000, "巧克力餅乾":500, "球鞋":800, "百科全書":-100}

請你依照小新的喜好幫這些禮物排序吧。
給你點時間想一下…











想到了嗎?其實就是列表依字典的value值排序,
程式如下:

gifts = ["動感超人", "巧克力餅乾", "球鞋", "百科全書"]
likes = {"動感超人": 2000, "巧克力餅乾":500, "球鞋":800, "百科全書":-100}
print(sorted(gifts, key= lambda x: likes[x]))

結果為: ['百科全書', '巧克力餅乾', '球鞋', '動感超人']

範例24-2 加權分數

大學聯考時,國、英、數成績是重要的三科,
但有時候因為你推甄的科系不同,
重視的科目也不同,
譬如說假設推甄外文系,
國文分數加權2倍,
英文分數加權3倍,
數學分數加權1倍,
也就是說如果你本來的國、英、數成績分別是10、15、8級分,
經過加權計算之後,你的分數為10*2+15*3+8*1=73分。
給你一個列表,用元組(tuple)記錄每個人的國、英、數分數,
例如:

scores= [(9, 6, 11), (10, 9, 6), (13, 8, 14), (13, 8, 11), (14, 15, 8)]

利用加權分數幫大家做排名吧。
一樣給你點時間想一下再往下看哦…











相信若你理解key參數的話便不難,
程式如下:

scores= [(9, 6, 11), (10, 9, 6), (13, 8, 14), (13, 8, 11), (14, 15, 8)]
print(sorted(scores,key= lambda x: x[0]*2+x[1]*3+x[2]))

結果為:[(9, 6, 11), (10, 9, 6), (13, 8, 11), (13, 8, 14), (14, 15, 8)]

範例24-3 撲克牌大老二之花色點數排序

不知道大家平時玩過撲克牌遊戲嗎?
沒有的話讓小馬給各位介紹一下,
在知名撲克牌遊戲-「大老二」,
所有的牌都是有大小順序的,
排序規則為:

  1. 優先比數字點數,數字2最大,其次是Ace,接下來依數字大小做排序
  2. 當數字點數相同時則比較花色,黑桃>紅心>方塊>梅花

舉例來說,黑桃2是最大的牌,梅花3是最小的牌。
(好奇詳細規則者可參考維基百科的說明)

那麼在程式中如何表示一張撲克牌呢?
本題以兩個字的字串來表示撲克牌,先記錄「點數」再來是「花色」,
花色各自取英文字首表示,
如梅花(club)是「c」、方塊(diamond)是「d」、紅心(heart)是「h」、黑桃(spade)是「s」。
數字直接以牌面上點數表示,
較特別的是點數「10」(Ten)以「T」表示,
而J、Q、K、A直接以英文表示。
利如說「梅花3」以"3c"表示,
「方塊J」以"Jd"表示。
現在給你一個字串列表表示你手上的撲克牌,例如:

hands = ["3c", "Qc", "Js", "Kh", "2h", "5c", "As", "Jd"]

請依大老二的規則排序吧。
先想一想,等等告訴你答案。
(提示: 用字典記錄花色或點數的價值,例如黑桃=4, 紅心=3, ...)











希望大家有想到,我們分別將花色與點數依照大小順序賦值,
如梅花=1,方塊=2,紅心=3,黑桃=4,
點數的話,就把Ace當作14,2當作15:

suits = {'c':1, 'd': 2, 'h':3, 's':4}
values= {'3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9, 'T': 10, 'J': 11, 'Q': 12, 'K': 13, 'A': 14, '2': 15}

完整程式如下:

hands = ["3c", "Qc", "Js", "Kh", "2h", "5c", "As", "Jd"]
suits = {'c':1, 'd': 2, 'h':3, 's':4}
values= {'3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9, 'T': 10, 'J': 11, 'Q': 12, 'K': 13, 'A': 14, '2': 15}
print(sorted(hands, key= lambda c: (values[c[0]],suits[c[1]])))

結果為: ['3c', '5c', 'Jd', 'Js', 'Qc', 'Kh', 'As', '2h']

今天就先學到這裡啦,
大家對排序是否大開眼界了呢?

課後練習

小馬覺得自己對於排序的參數使用理解已經非常透澈了,
直到在解題平台Hackerrank上看到這一題
真的開了眼界。
以下問題從Hackerrank上改編而來:
(因為是改編,你直接抄Hackerrank的答案是不對的哦,
考驗讀者對sorted的key參數的理解程度)

習題: 依指定規則重排字串

本練習讀入一個字串並輸出依規則重排後的字串,
input只包含大、小寫字母及數字,規定:

  1. 數字一定排在最右邊
  2. 偶數一定排在奇數的右邊
  3. 大寫字母一定排在小寫字母的右邊
  4. 在上述規則下,儘量保持原本字串的順序(在就是在原來字串的index愈大者排愈右邊)

例如說:

input: "Sorting1234"
output: "ortingS1324"

請在下列程式的???中填入適當的匿名函數使結果正確:

s = input() #測試範例輸入 Sorting1234
L=sorted(s, key= ???) #經排序後,L會變成一個字串的列表
print("".join(L)) #預期結果: ortingS1324

有任何問題或想法歡迎於留言區討論哦。


上一篇
Day23- project3 - 解經典9x9數獨問題
下一篇
Day25- python內建collections模組簡介,更優雅的選擇容器
系列文
活用python- 路遙知碼力,日久練成精30

尚未有邦友留言

立即登入留言