| | Начнём с того, что построим список пар размеров подмножеств.
Можем заметить, что может можно написать и поумнее, но мне лень, тем более, что время работы этого генератора, очевидно, очень маленькое.
def _get_subsets_sizes( max_size, max_diff, max_sum ) :
"""
Генерируем последовательность размеров пар подмножеств, таких,
что бы каждое следующее можно было получить из какого-то предыдущего
И что бы сначала перебирать группы множеств с меньшей вариативностью.
"""
res = set() # будем строить множество, что бы не париться с повторами, хотя мы и строим каждую пару один раз
for left_size in range(1, max_size+1) : # леове множество всегда не пустое и максимум max_size
for right_size in range( max(0, left_size-max_diff), min(max_size, left_size+max_diff ) + 1 ) :
to_add = left_size, right_size
assert to_add not in res, f"Повторно сгенерировали пару {to_add}" #это для эстетов
# Мы уже итерируем такие значения right_size, что 0 <= right_size <= max_size
# И -max_diff <= right_size - max_size <= max_diff
if sum(to_add) <= max_sum : # Но есть ещё условие на максимальную сумму размеров
res.add( to_add )
# множество построено, осталось отсортировать.
return sorted( res, key=lambda x:(sum(x), max(x), x))
| | "проверим, что получилось" | | | print( f"{( 4, 0, 12 )}:", _get_subsets_sizes( 4, 0, 12 ) )
print( f"{( 4, 2, 12 )}:", _get_subsets_sizes( 4, 2, 12 ) )
print( f"{( 4, 4, 12 )}:", _get_subsets_sizes( 4, 4, 12 ) )
Печатает:(4, 0, 12): [(1, 1), (2, 2), (3, 3), (4, 4)]
(4, 2, 12): [(1, 0), (1, 1), (2, 0), (1, 2), (2, 1), (2, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 4), (4, 2), (3, 4), (4, 3), (4, 4)]
(4, 4, 12): [(1, 0), (1, 1), (2, 0), (1, 2), (2, 1), (3, 0), (2, 2), (1, 3), (3, 1), (4, 0), (2, 3), (3, 2), (1, 4), (4, 1), (3, 3), (2, 4), (4, 2), (3, 4), (4, 3), (4, 4)]
| | | |
Напишем ещё несколько запчастей.
Для того, что бы облегчить себе отсечения множеств, отличающихся только порядком элементов, потребуем, что бы наши элементы были
1) все разными
2) все упорядочены по <
Генерировать будем так.
Будем строить по одному наборы подмножеств одного размера.
При этом запоминать будем не пары подмножеств, а тройки, так как нас интересуют ещё и те элементы, которые ещё можно добавлять.
Кроме того, давайте договоримся, не ограничивая общности, что
1) Пустым может быть только правое множество
2) Самый маленький элемент всегда находится в левом множестве
4) Сами множества будем строить упорядоченными, что бы не получать дубликаты, отличающиеся только порядком элементов. То есть в терминах python'а это будут списки
5) Левое и правое подмножества не могут пересекаться.
6) В целях экономии памяти, третье подмножество (подмножество кандидатов) будем вычислять не каждый раз, а пореже, осуществляя доп. фильтрацию при расширении подмножества
Итак, начнём с функции, которая из набора упорядочиваемых уникальных элементов строит набор троек упорядоченных подмножеств, таких, что в левом один элемент, правое пустое, и в остатке есть только элементы, превышающие элемент левого подмножества
Потом пишем функцию, которая берёт на вход список троек и всеми допустимыми способами расширяет левое (первое) подмножество, элементами третьего
И аналогичную функцию для расширения правого (второго) подмножества.
Функция для правого чуть сложнее, так как из (1) следует, что левое пустым быть не может, а правое может
(2) нам обеспечит изначальное построение соответствующих остатков (третьих множеств)
(5), а так же сокращение перебора в самых массовых подмножествах с относительно коротким остатком, нам обеспечит фильтрация остатка для каждой исходной тройки
def _build_start_1_0_trios( items ) :
"""
Строим самое первое подмножество подмножеств, в котором в левом по одному, а правое пустое
За одно вычисляем в каждом случае упорядоченный rest, все элементы в котором больше,
чем элемент в левом подмножестве
"""
items = tuple( sorted( set(items) ) ) #делаем уникальный упорядоченный набор элемнтов
return [(items[i:i+1], tuple(), items[i+1:]) for i in range(len(items))]
def _gen_add_item_to_left( trios ) :
"""
перечисляет результаты возможного расширения левых подмножества, за счёт остатков из той же тройки
"""
for l, r, rest in trios : #для всех троек
used = set( l ) | set( r ) # строим остаток, в котором нет элемнтов из l и r
rest = [c for c in rest if c not in used]
for c in rest :
if c > l[-1] : #l пустым быть не может. Строим только упорядоченные подмножества
yield l+(c,), r, rest
def _gen_add_item_to_right( trios ) :
"""
перечисляет результаты возможного расширения правых подмножества, за счёт остатков из той же тройки
"""
for l, r, rest in trios : #для всех троек
if r : # правое подможество, в отличии от левого, может быть пустым!
used = set( l ) | set( r ) # строим остаток, в котором нет элемнтов из l и r
rest = [c for c in rest if c not in used]
for c in rest :
if c > r[-1] : # Строим только упорядоченные подмножества
yield l, r+(c,), rest
else : # случай пустого правого подмножества -- некоторые отсечения нельзя выполнить.
used = set( l ) # строим остаток, в котором нет элемнтов из l и r (но оно всё равно пустое)
rest = [c for c in rest if c not in used]
for c in rest :
yield l, (c,), rest
| | "проверим, что получилось" | | | print( _build_start_1_0_trios( "мама мыла раму милым мылом".split(" ") ) )
print( list( _gen_add_item_to_left([
( (1,), tuple(), [2,4]),
( (1, 3), (2,), [2,4,5]),
( (1, 3), (2, 4), [2,4,5,7]),
]) ) )
print( list( _gen_add_item_to_right([
( (1,), tuple(), [2,4]),
( (1, 3), (2,), [2,4,5]),
( (1, 3), (2, 4), [2,4,5,7]),
]) ) )
Печатает:[(('мама',), (), ('милым', 'мыла', 'мылом', 'раму')), (('милым',), (), ('мыла', 'мылом', 'раму')), (('мыла',), (), ('мылом', 'раму')), (('мылом',), (), ('раму',)), (('раму',), (), ())]
[((1, 2), (), [2, 4]), ((1, 4), (), [2, 4]), ((1, 3, 4), (2,), [4, 5]), ((1, 3, 5), (2,), [4, 5]), ((1, 3, 5), (2, 4), [5, 7]), ((1, 3, 7), (2, 4), [5, 7])]
[((1,), (2,), [2, 4]), ((1,), (4,), [2, 4]), ((1, 3), (2, 4), [4, 5]), ((1, 3), (2, 5), [4, 5]), ((1, 3), (2, 4, 5), [5, 7]), ((1, 3), (2, 4, 7), [5, 7])]
| | | |
Ну и теперь можем писать сам генератор подмножеств.
Предлагается генерировать подмножества группами, в каждой из которых их размеры одинаковые.
При этом мы так написали _get_subsets_sizes, что обычно можем генерировать новую группу на основе уже сгенерированных, пополняя левое или правое подмножество.
(мы всегда можем это сделать, так как все наборы с меньшей суммой размеров подмножеств мы генерируем до того, как наборы с большей)
К сожалению, из этого правила есть исключение: это случай, когда max_diff == 0, так как в этом случае мы не можем увеличить сумму на 1. И нам придётся в этом случае "преодолевать пропасть в два прыжка"
def gen_sorted_pairs( items, max_diff, max_size ) :
"""
Генерирует множество пар упорядоченных подмножеств items
"""
if max_size < 1 : # нечего генерировать
return
trios_1_0 = _build_start_1_0_trios(items)
if max_diff < 1 : # особый случай, когда надо "преодолевать пропасть в два прыжка"
cur_trios = list( _gen_add_item_to_right(trios_1_0) ) #построили тройки для множеств 1х1
for t in cur_trios :
yield (set(t[0]), set(t[1]))
for i in range(2, max_size+1) :
# Прыжок №1. Сортируем, что бы удобнее было ориентироваться
tmp = _gen_add_item_to_left( sorted( cur_trios ) ) # в генерируемых множествах
# Прыжок №2. Выдаём множества по одному, что бы у перебора была возможность отсечься
cur_trios = [] # Но, если, нам потребуется и более поздняя группа, сохраняем выданное только что множество
for t in _gen_add_item_to_right( tmp ):
cur_trios.append( t )
yield (set(t[0]), set(t[1]))
else : # max_diff >= 1 -- можем позволить себе строить подмножества увеличивая их по одному!
cache = { (1,0):trios_1_0 } # в этом словаре будем хранить наборы множеств, которые планируем расширять
for size in _get_subsets_sizes(max_size, max_diff, len(items)) :
left_size, right_size = size
tmp = []
if size in cache :
for t in cache[size] :
yield (set(t[0]), set(t[1]))
elif (left_size, right_size-1) in cache :
for t in _gen_add_item_to_right( cache[(left_size, right_size-1)] ) :
yield (set(t[0]), set(t[1]))
tmp.append(t)
tmp.sort()
cache[size] = tmp
elif (left_size-1, right_size) in cache :
for t in _gen_add_item_to_left( cache[(left_size-1, right_size)] ) :
yield (set(t[0]), set(t[1]))
tmp.append(t)
tmp.sort()
cache[size] = tmp
else :
assert False
| | "проверим, что получилось" | | | print( len( list(gen_sorted_pairs([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], 0, 4)) ) ) # первое взвешивание
print( len( list(gen_sorted_pairs([1, 2, 3, 4, 5, 6, 7, 8], 4, 4)) ) ) # второе взвешивание
list( gen_sorted_pairs("папа мама я спортивная семья".split(" "), 5, 5 ) )
Печатает:28116
2703
[({'мама'}, set()),
({'папа'}, set()),
({'семья'}, set()),
({'спортивная'}, set()),
({'я'}, set()),
({'мама'}, {'папа'}),
({'мама'}, {'семья'}),
({'мама'}, {'спортивная'}),
({'мама'}, {'я'}),
({'папа'}, {'семья'}),
({'папа'}, {'спортивная'}),
({'папа'}, {'я'}),
({'семья'}, {'спортивная'}),
({'семья'}, {'я'}),
({'спортивная'}, {'я'}),
({'мама', 'папа'}, set()),
({'мама', 'семья'}, set()),
({'мама', 'спортивная'}, set()),
({'мама', 'я'}, set()),
({'папа', 'семья'}, set()),
({'папа', 'спортивная'}, set()),
({'папа', 'я'}, set()),
({'семья', 'спортивная'}, set()),
({'семья', 'я'}, set()),
({'спортивная', 'я'}, set()),
({'мама'}, {'папа', 'семья'}),
({'мама'}, {'папа', 'спортивная'}),
({'мама'}, {'папа', 'я'}),
({'мама'}, {'семья', 'спортивная'}),
({'мама'}, {'семья', 'я'}),
({'мама'}, {'спортивная', 'я'}),
({'папа'}, {'семья', 'спортивная'}),
({'папа'}, {'семья', 'я'}),
({'папа'}, {'спортивная', 'я'}),
({'семья'}, {'спортивная', 'я'}),
({'мама', 'папа'}, {'семья'}),
({'мама', 'папа'}, {'спортивная'}),
({'мама', 'папа'}, {'я'}),
({'мама', 'семья'}, {'папа'}),
({'мама', 'семья'}, {'спортивная'}),
({'мама', 'семья'}, {'я'}),
({'мама', 'спортивная'}, {'папа'}),
({'мама', 'спортивная'}, {'семья'}),
({'мама', 'спортивная'}, {'я'}),
({'мама', 'я'}, {'папа'}),
({'мама', 'я'}, {'семья'}),
({'мама', 'я'}, {'спортивная'}),
({'папа', 'семья'}, {'спортивная'}),
({'папа', 'семья'}, {'я'}),
({'папа', 'спортивная'}, {'семья'}),
({'папа', 'спортивная'}, {'я'}),
({'папа', 'я'}, {'семья'}),
({'папа', 'я'}, {'спортивная'}),
({'семья', 'спортивная'}, {'я'}),
({'семья', 'я'}, {'спортивная'}),
({'мама', 'папа', 'семья'}, set()),
({'мама', 'папа', 'спортивная'}, set()),
({'мама', 'папа', 'я'}, set()),
({'мама', 'семья', 'спортивная'}, set()),
({'мама', 'семья', 'я'}, set()),
({'мама', 'спортивная', 'я'}, set()),
({'папа', 'семья', 'спортивная'}, set()),
({'папа', 'семья', 'я'}, set()),
({'папа', 'спортивная', 'я'}, set()),
({'семья', 'спортивная', 'я'}, set()),
({'мама', 'папа'}, {'семья', 'спортивная'}),
({'мама', 'папа'}, {'семья', 'я'}),
({'мама', 'папа'}, {'спортивная', 'я'}),
({'мама', 'семья'}, {'папа', 'спортивная'}),
({'мама', 'семья'}, {'папа', 'я'}),
({'мама', 'семья'}, {'спортивная', 'я'}),
({'мама', 'спортивная'}, {'папа', 'семья'}),
({'мама', 'спортивная'}, {'папа', 'я'}),
({'мама', 'спортивная'}, {'семья', 'я'}),
({'мама', 'я'}, {'папа', 'семья'}),
({'мама', 'я'}, {'папа', 'спортивная'}),
({'мама', 'я'}, {'семья', 'спортивная'}),
({'папа', 'семья'}, {'спортивная', 'я'}),
({'папа', 'спортивная'}, {'семья', 'я'}),
({'папа', 'я'}, {'семья', 'спортивная'}),
({'мама'}, {'папа', 'семья', 'спортивная'}),
({'мама'}, {'папа', 'семья', 'я'}),
({'мама'}, {'папа', 'спортивная', 'я'}),
({'мама'}, {'семья', 'спортивная', 'я'}),
({'папа'}, {'семья', 'спортивная', 'я'}),
({'мама', 'папа', 'семья'}, {'спортивная'}),
({'мама', 'папа', 'семья'}, {'я'}),
({'мама', 'папа', 'спортивная'}, {'семья'}),
({'мама', 'папа', 'спортивная'}, {'я'}),
({'мама', 'папа', 'я'}, {'семья'}),
({'мама', 'папа', 'я'}, {'спортивная'}),
({'мама', 'семья', 'спортивная'}, {'папа'}),
({'мама', 'семья', 'спортивная'}, {'я'}),
({'мама', 'семья', 'я'}, {'папа'}),
({'мама', 'семья', 'я'}, {'спортивная'}),
({'мама', 'спортивная', 'я'}, {'папа'}),
({'мама', 'спортивная', 'я'}, {'семья'}),
({'папа', 'семья', 'спортивная'}, {'я'}),
({'папа', 'семья', 'я'}, {'спортивная'}),
({'папа', 'спортивная', 'я'}, {'семья'}),
({'мама', 'папа', 'семья', 'спортивная'}, set()),
({'мама', 'папа', 'семья', 'я'}, set()),
({'мама', 'папа', 'спортивная', 'я'}, set()),
({'мама', 'семья', 'спортивная', 'я'}, set()),
({'папа', 'семья', 'спортивная', 'я'}, set()),
({'мама', 'папа'}, {'семья', 'спортивная', 'я'}),
({'мама', 'семья'}, {'папа', 'спортивная', 'я'}),
({'мама', 'спортивная'}, {'папа', 'семья', 'я'}),
({'мама', 'я'}, {'папа', 'семья', 'спортивная'}),
({'мама', 'папа', 'семья'}, {'спортивная', 'я'}),
({'мама', 'папа', 'спортивная'}, {'семья', 'я'}),
({'мама', 'папа', 'я'}, {'семья', 'спортивная'}),
({'мама', 'семья', 'спортивная'}, {'папа', 'я'}),
({'мама', 'семья', 'я'}, {'папа', 'спортивная'}),
({'мама', 'спортивная', 'я'}, {'папа', 'семья'}),
({'мама'}, {'папа', 'семья', 'спортивная', 'я'}),
({'мама', 'папа', 'семья', 'спортивная'}, {'я'}),
({'мама', 'папа', 'семья', 'я'}, {'спортивная'}),
({'мама', 'папа', 'спортивная', 'я'}, {'семья'}),
({'мама', 'семья', 'спортивная', 'я'}, {'папа'}),
({'мама', 'папа', 'семья', 'спортивная', 'я'}, set())]
| | | |
Итого, нам осталось написать только сам перебор взвешиваний.
Самую муторнуя часть -- генератор варинтов расположения монет на чашках весов, мы уже написали! |
(точнее, в течение первого же дня)
