2次元配列を複数のKeyでソートする --- Python3

• Goal
  2次元配列を複数のKeyでソートしたい
  
• How
  itemgetterを使う。
  
• Example
  入力）
  Udon 500 大阪店
  Udon 700 東京店
  Ramen 1000 大阪店
  Ramen 1200 大阪店
  Udon 500 福岡店
  Apple 100 福岡店
  
  これを、メニュー(ABC順)→値段(高いものから)並べたい。
• Source
  
  

  	# -*- coding: utf-8 -*-
  	import sys
  	from operator import itemgetter
  	# input
  	a = []
  	for i in range(6):
  	a1, a2, a3 = map(str, input().split())
  	a.append([a1, int(a2), a3])
  	# ソート前
  	print('Before Sort')
  	print(a)
  	print('\nSort by Price')
  	a.sort(key=itemgetter(1), reverse=True)
  	print(a)
  	print('\nThen sort by menu')
  	a.sort(key=itemgetter(0))
  	print(a)

  view raw sort_itemgetter.py hosted with ❤ by GitHub
  
  
• Result
  % python sort_itemgetter.py
  Udon 500 大阪店
  Udon 700 東京店
  Ramen 1000 大阪店
  Ramen 1200 大阪店
  Udon 500 福岡店
  Apple 100 福岡店
  Before Sort
  [['Udon', 500, '大阪店'], ['Udon', 700, '東京店'], ['Ramen', 1000, '大阪店'], ['Ramen', 1200, '大阪店'], ['Udon', 500, '福岡店'], ['Apple', 100, '福岡店']]
  
  Sort by Price
  [['Ramen', 1200, '大阪店'], ['Ramen', 1000, '大阪店'], ['Udon', 700, '東京店'], ['Udon', 500, '大阪店'], ['Udon', 500, '福岡店'], ['Apple', 100, '福岡店']]
  
  Then sort by menu
  [['Apple', 100, '福岡店'], ['Ramen', 1200, '大阪店'], ['Ramen', 1000, '大阪店'], ['Udon', 700, '東京店'], ['Udon', 500, '大阪店'], ['Udon', 500, '福岡店']]

素因数分解 (試し割り法) の根本理解 - Python3

競技プログラミングサイトで遊んでいると、素因数分解の知識が必要となり、再勉強をした。

１．素因数分解を思い出す。
小さい素数から、割り算を繰り返して、これ以上どの数字でも割れないとなったら終了という理解。(以下の画像のイメージ)

これを、試し割り法というとの事。

２．試し割り法のアルゴリズムの理解を深める。
以下のサイトを参考にさせて頂いて、試し割り法のアルゴリズムを見た。
Thanks!!
・Pythonで素因数分解する
・素数と仲良しになる3つのプログラム

が、素人の為、正直良くわからない部分があり、１行づつ理解を深めて見た。

私の理解としては。。。

ある数（素数候補）として、初期値を２とする。

①”ある数（素数候補）”で割り切れるかどうかを見る？
②入力数字を”ある数”で実際に割り、商に置き換える。

①と②を割りきれなくなるまで繰り返す。

割り切れなくなったら、
③次に、”ある数”を１つ大きくして、①と②を繰り返す。

で、④残りの数を、”ある数”で割った商が、”ある数”よりも小さくなったら終わり。
何故なら、２から初めて、１づつ”ある数”を大きくしながらで割っていくので、
これより先、割り切れる事はない。（割り切れるなら、この段階にくるまでに割り切れているはず。）

。。。。ということで、説明は上手くないが、以下を実行して、腹落ちした。

	# -*- coding: utf-8 -*-
	#　ColabのPython3（Python 3.6.7）で実行
	################
	# 素因数分解　　　試し割り法
	################
	def factorization(n):
	i = 2
	l = []
	while i * i <= n:
	print(f'CP1: {i}で割り切れるかどうか調べる。') ## CheckPoint1
	while n % i == 0:
	n /= i
	print(f'CP2: {i}で割り切れたから、{i}を出力する。') ## CheckPoint2
	l.append(i)
	print(f'この時点の商：{int(n)}')
	print(f'この時点の出力予定：{l}')
	print(f'まだ、{i}で割り切れるかどうかを確認する。\n')
	print(f'CP3: {i}では、もう割り切れなくなったので、') ## CheckPoint3
	i += 1
	print(f'次は、{i}で割り切れるかどうかを試す。\n')
	print(f'CP4: {int(n)}を{i}で、割ったとしても、商は{i}より小さくなるので、これ以上は検討不要。') ## CheckPoint4
	print(f'残っている数を、最後の約数として追加する。ただし、１の場合は、無視する。')
	if n > 1:
	l.append(int(n))
	print(f'{int(n)}を出力して計算終了。\n')
	return l
	# input
	a = int(input())
	#a = 10000000000
	print(f'{a}の素因数分解をする。\n')
	# calc
	o = factorization(a)
	# output
	print('output----')
	print(o)

view raw explain_factorization.py hosted with ❤ by GitHub

以下、上記プログラムの実行結果。３６０を素因数分解している。

-> % python factorization.py
３６０
360の素因数分解をする。

CP1: 2で割り切れるかどうか調べる。
CP2: 2で割り切れたから、2を出力する。
この時点の商：180
この時点の出力予定：[2]
まだ、2で割り切れるかどうかを確認する。

CP2: 2で割り切れたから、2を出力する。
この時点の商：90
この時点の出力予定：[2, 2]
まだ、2で割り切れるかどうかを確認する。

CP2: 2で割り切れたから、2を出力する。
この時点の商：45
この時点の出力予定：[2, 2, 2]
まだ、2で割り切れるかどうかを確認する。

CP3: 2では、もう割り切れなくなったので、
次は、3で割り切れるかどうかを試す。

CP1: 3で割り切れるかどうか調べる。
CP2: 3で割り切れたから、3を出力する。
この時点の商：15
この時点の出力予定：[2, 2, 2, 3]
まだ、3で割り切れるかどうかを確認する。

CP2: 3で割り切れたから、3を出力する。
この時点の商：5
この時点の出力予定：[2, 2, 2, 3, 3]
まだ、3で割り切れるかどうかを確認する。

CP3: 3では、もう割り切れなくなったので、
次は、4で割り切れるかどうかを試す。

CP4: 5を4で、割ったとしても、商は4より小さくなるので、これ以上は検討不要。
残っている数を、最後の約数として追加する。ただし、１の場合は、無視する。
5を出力して計算終了。

output----
[2, 2, 2, 3, 3, 5]