Skip to content

Instantly share code, notes, and snippets.

@4ft35t

4ft35t/result.txt

Forked from quxiaowei/matching.py
Last active January 14, 2025 08:32
Show Gist options
  • Save 4ft35t/814b5ba8bba6cf1a2fc3dc14db818cb9 to your computer and use it in GitHub Desktop.
Save 4ft35t/814b5ba8bba6cf1a2fc3dc14db818cb9 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. 4ft35t revised this gist Jan 14, 2025. 1 changed file with 3 additions and 5 deletions.
    8 changes: 3 additions & 5 deletions v2ex_895464_v2.py
    View file
    Original file line number Diff line number Diff line change
    @@ -32,12 +32,10 @@ def resolve(n, lst):

    uniq_elem = set(new_lst)
    # count for each element
    elem_count = {}
    max_repeat = 1
    for k in uniq_elem:
    c = new_lst.count(k)
    elem_count[k] = c
    max_repeat = max(max_repeat, new_lst.count(k))

    max_repeat = max(elem_count.values())
    # 用最小重复次数求解，如果不行，元素重复次数加1，再求解
    min_lst = []
    for i in range(1, max_repeat+1):
    @@ -47,7 +45,7 @@ def resolve(n, lst):
    min_lst.append(k)
    if sum(min_lst) == n:
    return min_lst
    print('round:', i, len(min_lst))
    print('round:', i, 'len(lst):', len(min_lst))

    # 减少排列组合次数
    for i in sorted(uniq_elem, reverse=True):
  2. 4ft35t revised this gist Jan 14, 2025. 1 changed file with 4 additions and 0 deletions.
    4 changes: 4 additions & 0 deletions v2ex_895464_v2.py
    View file
    Original file line number Diff line number Diff line change
    @@ -13,8 +13,11 @@
    a = [round(i*100) for i in a]
    b = [round(i*100) for i in b]


    def comb(n, lst):
    new_lst = [i for i in lst if i <= n]
    if sum(new_lst) == n:
    return new_lst

    for i in range(1, len(new_lst)+1):
    # print(f'C({len(new_lst)}, {i})')
    @@ -44,6 +47,7 @@ def resolve(n, lst):
    min_lst.append(k)
    if sum(min_lst) == n:
    return min_lst
    print('round:', i, len(min_lst))

    # 减少排列组合次数
    for i in sorted(uniq_elem, reverse=True):
  3. 4ft35t revised this gist Jan 14, 2025. 1 changed file with 0 additions and 2 deletions.
    2 changes: 0 additions & 2 deletions v2ex_895464_v2.py
    View file
    Original file line number Diff line number Diff line change
    @@ -13,8 +13,6 @@
    a = [round(i*100) for i in a]
    b = [round(i*100) for i in b]


    # @lru_cache(maxsize=10240)
    def comb(n, lst):
    new_lst = [i for i in lst if i <= n]

  4. 4ft35t revised this gist Jan 14, 2025. 1 changed file with 66 additions and 0 deletions.
    66 changes: 66 additions & 0 deletions v2ex_895464_v2.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,66 @@
    #!/usr/bin/env python3
    # coding: utf-8
    # vim: set expandtab tabstop=4 shiftwidth=4 softtabstop=4:

    import itertools as it

    a = [52.7,8.96]
    b = [21.44,6.72,5.44,5.12,4.48,3.20,2.24,1.92,1.92,1.92,1.28,1.28,1.00,0.96,0.50,0.32,0.32,0.32,0.32,0.32,0.32,0.32]

    a = [62.13,26.67,17.76]
    b = [24.92,5.88,5.04,3.64,3.45,3.36,2.8,2.8,2.52,2.24,2.24,2.24,1.96,1.96,1.8,1.68,1.4,1.4,1.4,1.2,1.2,1.15,1.12,1.12,1.12,1.12,1.12,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.4,0.4,0.4,0.4,0.4,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28]

    a = [round(i*100) for i in a]
    b = [round(i*100) for i in b]


    # @lru_cache(maxsize=10240)
    def comb(n, lst):
    new_lst = [i for i in lst if i <= n]

    for i in range(1, len(new_lst)+1):
    # print(f'C({len(new_lst)}, {i})')
    for j in it.combinations(new_lst, i):
    if sum(j) == n:
    return j

    def resolve(n, lst):
    new_lst = [i for i in lst if i <= n]
    if sum(new_lst) == n:
    return new_lst

    uniq_elem = set(new_lst)
    # count for each element
    elem_count = {}
    for k in uniq_elem:
    c = new_lst.count(k)
    elem_count[k] = c

    max_repeat = max(elem_count.values())
    # 用最小重复次数求解，如果不行，元素重复次数加1，再求解
    min_lst = []
    for i in range(1, max_repeat+1):
    for k in uniq_elem:
    if k in new_lst:
    new_lst.remove(k)
    min_lst.append(k)
    if sum(min_lst) == n:
    return min_lst

    # 减少排列组合次数
    for i in sorted(uniq_elem, reverse=True):
    n0 = min_lst[0]
    n1 = n - n0
    ans = comb(n1, min_lst[1:])
    if ans:
    return [n0] + list(ans)

    a.sort()
    # b.sort(reverse=True)
    assert sum(a) == sum(b)

    for i in a:
    ans = resolve(i, b)
    if ans:
    print(f'{i} = {" + ".join(map(str, ans))}')
    [ b.remove(i) for i in ans ]
  5. 4ft35t revised this gist Nov 16, 2022. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion result.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -55,7 +55,7 @@ a = 6213 , len(b) = 64, sum(b) = 6213
    40
    40
    40
    56
    56
    56
    56
    56
  6. 4ft35t revised this gist Nov 16, 2022. 1 changed file with 88 additions and 0 deletions.
    88 changes: 88 additions & 0 deletions result.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,88 @@
    sum(a): 10656
    sum(b): 10656
    a = 1776 , len(b) = 83, sum(b) = 10656
    588
    504
    280
    224
    180
    a = 2667 , len(b) = 78, sum(b) = 8880
    364
    336
    280
    252
    224
    224
    196
    196
    140
    140
    120
    115
    40
    40
    a = 6213 , len(b) = 64, sum(b) = 6213
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    28
    40
    40
    40
    56
    56
    56
    56
    56
    56
    56
    56
    56
    56
    56
    56
    84
    84
    84
    84
    84
    84
    84
    84
    84
    112
    112
    112
    112
    112
    120
    140
    168
    345
    2492
  7. 4ft35t renamed this gist Nov 16, 2022. 1 changed file with 0 additions and 0 deletions.
    0 matching.py → v2ex_895464.py
    View file
    File renamed without changes.
  8. 4ft35t revised this gist Nov 16, 2022. 1 changed file with 26 additions and 41 deletions.
    67 changes: 26 additions & 41 deletions matching.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,66 +1,51 @@
    import decimal
    from decimal import Decimal
    from functools import lru_cache

    a = ['23.17', '3.2', '1.22', '0.32']
    b = ['7.36', '4.16', '3.2', '1.69', '1.28', '1.28', '0.96', '0.96', '0.90', '0.64', '0.64', '0.64', '0.50', '0.50', '0.32', '0.32', '0.32', '0.32', '0.32', '0.32', '0.32', '0.32', '0.32', '0.32']
    a = [17.76,62.13,26.67] #62.13,17.76,]
    b = [24.92,5.88,5.04,3.64,3.45,3.36,2.8,2.8,2.52,2.24,2.24,2.24,1.96,1.96,1.8,1.68,1.4,1.4,1.4,1.2,1.2,1.15,1.12,1.12,1.12,1.12,1.12,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.4,0.4,0.4,0.4,0.4,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28]

    a = ["52.7", "8.96"]
    b = ["21.44", "6.72", "5.44", "5.12", "4.48", "3.20", "2.24", "1.92", "1.92", "1.92", "1.28", "1.28", "1.00", "0.96", "0.50", "0.32", "0.32", "0.32", "0.32", "0.32", "0.32", "0.32"]

    a = ['17.76','62.13','26.67'] #'62.13','17.76',]
    b = ['24.92','5.88','5.04','3.64','3.45','3.36','2.8','2.8','2.52','2.24','2.24','2.24','1.96','1.96','1.8','1.68','1.4','1.4','1.4','1.2','1.2','1.15','1.12','1.12','1.12','1.12','1.12','0.84','0.84','0.84','0.84','0.84','0.84','0.84','0.84','0.84','0.56','0.56','0.56','0.56','0.56','0.56','0.56','0.56','0.56','0.56','0.56','0.56','0.4','0.4','0.4','0.4','0.4','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28']

    a = [Decimal(aa) for aa in a]
    b = [Decimal(bb) for bb in b]
    a = [round(i*100) for i in a]
    b = [round(i*100) for i in b]

    a.sort()
    b.sort()

    def _sum( a ):
    _s = Decimal(0)
    for i in a:
    _s += i
    return _s

    print("sum(a):", _sum(a))
    print("sum(b):", _sum(b))
    print("sum(a):", sum(a))
    print("sum(b):", sum(b))

    def main(a):
    for i, aa in enumerate(a[:4]):
    print(f"a = { aa } , len(b) = { len(b) }, sum(b) = { _sum(b) }")
    for aa in a:
    print(f"a = { aa } , len(b) = { len(b) }, sum(b) = { sum(b) }")
    # print(b)
    findAinB(aa, 0)


    @lru_cache(maxsize=10240)
    def findAinB(a1, ib):
    # print(ib)
    # print(a1, ib)
    if ib >= len(b):
    return False

    if a1 == sum(b[ib:]):
    for i in b[ib:]:
    print('\t', i)
    b.remove(i)
    return True

    b1 = b[ib]
    if a1 < b1:
    return False
    elif a1 == b1:
    print('\t', b1)
    b.pop(ib)
    return True
    elif a1 > b1:
    ii = ib+1
    for i, bb in enumerate( b[ib+1:] ):
    if bb > b1 :
    ii += i
    break

    if findAinB(a1, ii):
    return True
    elif findAinB(a1-b1, ib+1):
    print('\t', b1)
    b.pop(ib)
    return True

    if findAinB(a1, ib+1):
    return True
    elif findAinB(a1-b1, ib+1):
    print('\t', b1)
    b.pop(ib)
    return True

    return False


    main(a)



    main(a)
  9. @quxiaowei quxiaowei created this gist Nov 16, 2022.
    66 changes: 66 additions & 0 deletions matching.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,66 @@
    import decimal
    from decimal import Decimal

    a = ['23.17', '3.2', '1.22', '0.32']
    b = ['7.36', '4.16', '3.2', '1.69', '1.28', '1.28', '0.96', '0.96', '0.90', '0.64', '0.64', '0.64', '0.50', '0.50', '0.32', '0.32', '0.32', '0.32', '0.32', '0.32', '0.32', '0.32', '0.32', '0.32']

    a = ["52.7", "8.96"]
    b = ["21.44", "6.72", "5.44", "5.12", "4.48", "3.20", "2.24", "1.92", "1.92", "1.92", "1.28", "1.28", "1.00", "0.96", "0.50", "0.32", "0.32", "0.32", "0.32", "0.32", "0.32", "0.32"]

    a = ['17.76','62.13','26.67'] #'62.13','17.76',]
    b = ['24.92','5.88','5.04','3.64','3.45','3.36','2.8','2.8','2.52','2.24','2.24','2.24','1.96','1.96','1.8','1.68','1.4','1.4','1.4','1.2','1.2','1.15','1.12','1.12','1.12','1.12','1.12','0.84','0.84','0.84','0.84','0.84','0.84','0.84','0.84','0.84','0.56','0.56','0.56','0.56','0.56','0.56','0.56','0.56','0.56','0.56','0.56','0.56','0.4','0.4','0.4','0.4','0.4','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28','0.28']

    a = [Decimal(aa) for aa in a]
    b = [Decimal(bb) for bb in b]

    a.sort()
    b.sort()

    def _sum( a ):
    _s = Decimal(0)
    for i in a:
    _s += i
    return _s

    print("sum(a):", _sum(a))
    print("sum(b):", _sum(b))

    def main(a):
    for i, aa in enumerate(a[:4]):
    print(f"a = { aa } , len(b) = { len(b) }, sum(b) = { _sum(b) }")
    # print(b)
    findAinB(aa, 0)

    def findAinB(a1, ib):
    # print(ib)
    if ib >= len(b):
    return False

    b1 = b[ib]
    if a1 < b1:
    return False
    elif a1 == b1:
    print('\t', b1)
    b.pop(ib)
    return True
    elif a1 > b1:
    ii = ib+1
    for i, bb in enumerate( b[ib+1:] ):
    if bb > b1 :
    ii += i
    break

    if findAinB(a1, ii):
    return True
    elif findAinB(a1-b1, ib+1):
    print('\t', b1)
    b.pop(ib)
    return True

    return False


    main(a)