目次
はじめに
単調増加って「広義」と「狭義」があるみたい。
単調増加・単調減少の意味と覚えておくべき性質 | 高校数学の美しい物語
関数および数列の単調増加，単調減少について，定義，具体例および性質を解説します。
manabitimes.jp
上の記事をまとめると
広義単調増加は
ならば 
※[1, 1, 1]のような重複OK
狭義単調増加は ならば 
※[1, 2, 3]のような、重複許さない増加
※重要 今回は、1桁の数列 [1]…[9]も単調増加数列として考えている。
広義単調増加数列の作成コード
広義はitertools.combinations_with_replacementを使えば簡単にできるみたい
ある範囲で広義単調増加する数列を列挙する
次の条件を満たす数列を列挙する方法はありますか．長さがNの正整数列1 <= A_1 <= A_2 <= ... <= A_N <= M1 <= N, M <= 10再帰関数を用いることにより目的は一先ず達成出来ましたが，配列のコピーのためパ...
ja.stackoverflow.com
import itertools
def make_broad_sense_monotonically_increasing_number_seqs(min_num :int, max_num: int, digit: int) -> list:
"""
条件を満たす広義単調増加数列のリストを作成する。
Parameters
----------
min_num :int
単調増加数列で使う最小の数字。
max_num: int
単調増加数列で使う最大の数字。
digit: int
単調増加数列の桁数。
Returns
-------
list
広義単調増加数列のリスト。
"""
if min_num > max_num or digit < 1:
return []
return list(map(list, list(itertools.combinations_with_replacement(range(min_num, max_num+1), digit))))
使用例) 1-9の数字を使った、3桁の広義単調増加数列を作る
# 1-9の数字を使った、3桁の広義単調増加数列を作る
l = make_broad_sense_monotonically_increasing_number_seqs(1, 9, 3)
[print(i) for i in l]
# 出力結果
# [1, 1, 1]
# [1, 1, 2]
# [1, 1, 3]
# [1, 1, 4]
# ...
# [7, 8, 9]
# [7, 9, 9]
# [8, 8, 8]
# [8, 8, 9]
# [8, 9, 9]
# [9, 9, 9]
print(len(l), "個")
# 出力結果
# 165 個使用例) 1-9の数字を使った、1-9桁の広義単調増加数列を作る
l = []
for i in range(1, 10):
l += make_broad_sense_monotonically_increasing_number_seqs(1, 9, i)
[print(i) for i in l]
# 出力結果
# [1]
# [2]
# [3]
# [4]
# [5]
# [6]
# [7]
# [8]
# [9]
# [1, 1]
# [1, 2]
# [1, 3]
# [1, 4]
# [1, 5]
# [1, 6]
# ...
# [8, 8, 8, 8, 9, 9, 9, 9, 9]
# [8, 8, 8, 9, 9, 9, 9, 9, 9]
# [8, 8, 9, 9, 9, 9, 9, 9, 9]
# [8, 9, 9, 9, 9, 9, 9, 9, 9]
# [9, 9, 9, 9, 9, 9, 9, 9, 9]
print(len(l), "個")
# 出力結果
# 48619 個AtCoderのPython (CPython 3.11.4)での実行速度
狭義単調増加数列の作成コード
狭義単調増加数列 
広義単調増加数列 っぽいので、
広義単調増加数列作って、それをfilterしましょう。
※試していないが、全ての数列を走査するよりも速いはず
import itertools
def is_narrow_sense_monotonic_increasing(l: list):
"""
数列が狭義単調増加かどうかを判定する。
Parameters
----------
l: list
数列。
Returns
-------
bool
数列が狭義単調増加ならTrue、そうでなければFalse。
"""
# 数列の初めの数字から順に見ていく
for i in range(len(l)-1):
# 前の桁 l[i]の数字の方が、後の桁l[i+1]の数字以上になる場合は、狭義単調増加ではない
if l[i] >= l[i+1]:
return False
return True
def make_narrow_sense_monotonically_increasing_number_seqs(min_num :int, max_num: int, digit: int) -> list:
"""
条件を満たす狭義単調増加数列のリストを作成する。
Parameters
----------
min_num :int
単調増加数列で使う最小の数字。
max_num: int
単調増加数列で使う最大の数字。
digit: int
単調増加数列の桁数。
Returns
-------
list
狭義単調増加数列のリスト。
"""
if min_num > max_num or digit < 1:
return []
l = list(map(list, list(itertools.combinations_with_replacement(range(min_num, max_num+1), digit))))
return list(filter(is_narrow_sense_monotonic_increasing, l))
使用例）1-9の数字を使った、3桁の狭義単調増加数列を作る
l = make_narrow_sense_monotonically_increasing_number_seqs(1, 9, 3)
[print(i) for i in l]
# 出力結果
# [1, 2, 3]
# [1, 2, 4]
# [1, 2, 5]
# [1, 2, 6]
# [1, 2, 7]
# ...
# [5, 8, 9]
# [6, 7, 8]
# [6, 7, 9]
# [6, 8, 9]
# [7, 8, 9]
print(len(l), "個")
# 出力結果
# 84 個使用例）1-9の数字を使った、1-9桁の狭義単調増加数列を作る
参考：
Editorial - SuntoryProgrammingContest2023（AtCoder Beginner Contest 321）
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
なので、同じ数字が使われることがない
そのため、数字一つ一つに、「ひとつ使うか使わないか」の2通りを考えると探索可能
さらに、この選択を行った後は数字を照準に並べた数列しか考えなくてよい
そのため、使う数字がn種類存在する場合、作成できる狭義単調増加数列は
通りとなる。
※ 1を引いているのは「何も使わない」組み合わせ
l = []
for i in range(1, 10):
l += make_narrow_sense_monotonically_increasing_number_seqs(1, 9, i)
[print(i) for i in l]
# 出力結果
# [1]
# [2]
# [3]
# [4]
# [5]
# [6]
# [7]
# [8]
# [9]
# [1, 2]
# [1, 3]
# [1, 4]
# [1, 5]
# [1, 6]
# ...
# [2, 3, 4, 5, 7, 8, 9]
# [2, 3, 4, 6, 7, 8, 9]
# [2, 3, 5, 6, 7, 8, 9]
# [2, 4, 5, 6, 7, 8, 9]
# [3, 4, 5, 6, 7, 8, 9]
# [1, 2, 3, 4, 5, 6, 7, 8]
# [1, 2, 3, 4, 5, 6, 7, 9]
# [1, 2, 3, 4, 5, 6, 8, 9]
# [1, 2, 3, 4, 5, 7, 8, 9]
# [1, 2, 3, 4, 6, 7, 8, 9]
# [1, 2, 3, 5, 6, 7, 8, 9]
# [1, 2, 4, 5, 6, 7, 8, 9]
# [1, 3, 4, 5, 6, 7, 8, 9]
# [2, 3, 4, 5, 6, 7, 8, 9]
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(len(l), "個")
# 出力結果
# 511 個AtCoderのPython (CPython 3.11.4)での実行速度
なんか、広義単調増加数列より速いな…
コメント