AOJトライに関する知識知見の記録共有：ITP2_11_D

タスク概要

Enumeration of Combinations

コード実装例

TIPS

1. 例外処理含む評価パターンを追加

import pprint, sys, time
import itertools

def agg(lst):
    return sum([2**v for v in lst])

def core(arg, adv=True, n_ret=10):
    ret = []
    n = arg[0]
    k = arg[1] if len(arg) > 1 else int(n/2)

    if adv:
        ret = sorted([[agg(array), array] for array in itertools.combinations(range(n), k)], 
                key=lambda x: x[0])[:n_ret]
    else:
        for array in itertools.combinations(range(n), k):
            ret.append([agg(array), array])
        ret = sorted(ret, key=lambda x: x[0])[:n_ret]

    return ret

def app(*args):
    ret = []
    for arg in args:
        s = []
        for adv in [True, False]:
            st = time.time()
            try:
                r = core(arg, adv=adv)
            except Exception as e:
                r = e
            s.append([adv, round(time.time() - st, 6), r])
        ret.append([arg, s])
    return ret

print(sys.version)
pprint.pprint(app(
    # basic examples
    [5, 3],
    # additional examples
    [5],
    [20, 5],
    # exceptional examples
    "例外入力"
))

実行結果

各種補足情報出力（入力値FB、デバッグログ等）含む

3.8.10 
[GCC 9.3.0]
[[[5, 3],
  [[True,
    2.5e-05,
    [[7, (0, 1, 2)],
     [11, (0, 1, 3)],
     [13, (0, 2, 3)],
     [14, (1, 2, 3)],
     [19, (0, 1, 4)],
     [21, (0, 2, 4)],
     [22, (1, 2, 4)],
     [25, (0, 3, 4)],
     [26, (1, 3, 4)],
     [28, (2, 3, 4)]]],
   [False,
    9.2e-05,
    [[7, (0, 1, 2)],
     [11, (0, 1, 3)],
     [13, (0, 2, 3)],
     [14, (1, 2, 3)],
     [19, (0, 1, 4)],
     [21, (0, 2, 4)],
     [22, (1, 2, 4)],
     [25, (0, 3, 4)],
     [26, (1, 3, 4)],
     [28, (2, 3, 4)]]]]],
 [[5],
  [[True,
    1.8e-05,
    [[3, (0, 1)],
     [5, (0, 2)],
     [6, (1, 2)],
     [9, (0, 3)],
     [10, (1, 3)],
     [12, (2, 3)],
     [17, (0, 4)],
     [18, (1, 4)],
     [20, (2, 4)],
     [24, (3, 4)]]],
   [False,
    1e-05,
    [[3, (0, 1)],
     [5, (0, 2)],
     [6, (1, 2)],
     [9, (0, 3)],
     [10, (1, 3)],
     [12, (2, 3)],
     [17, (0, 4)],
     [18, (1, 4)],
     [20, (2, 4)],
     [24, (3, 4)]]]]],
 [[20, 5],
  [[True,
    0.03452,
    [[31, (0, 1, 2, 3, 4)],
     [47, (0, 1, 2, 3, 5)],
     [55, (0, 1, 2, 4, 5)],
     [59, (0, 1, 3, 4, 5)],
     [61, (0, 2, 3, 4, 5)],
     [62, (1, 2, 3, 4, 5)],
     [79, (0, 1, 2, 3, 6)],
     [87, (0, 1, 2, 4, 6)],
     [91, (0, 1, 3, 4, 6)],
     [93, (0, 2, 3, 4, 6)]]],
   [False,
    0.030134,
    [[31, (0, 1, 2, 3, 4)],
     [47, (0, 1, 2, 3, 5)],
     [55, (0, 1, 2, 4, 5)],
     [59, (0, 1, 3, 4, 5)],
     [61, (0, 2, 3, 4, 5)],
     [62, (1, 2, 3, 4, 5)],
     [79, (0, 1, 2, 3, 6)],
     [87, (0, 1, 2, 4, 6)],
     [91, (0, 1, 3, 4, 6)],
     [93, (0, 2, 3, 4, 6)]]]]],
 ['例外入力',
  [[True,
    1.6e-05,
    TypeError("'str' object cannot be interpreted as an integer")],
   [False,
    3e-06,
    TypeError("'str' object cannot be interpreted as an integer")]]]]

補遺

残課題（Pull Request絶賛募集中！）

1. 実行速度の改善（枝刈り、データ構造の見直し等）
2. コア関数の汎用化