Информация об изменениях

Сообщение Re: Задачке 45+ лет. от 26.02.2020 17:42

Изменено 26.02.2020 18:22 Erop

Re: Задачке 45+ лет.
Здравствуйте, NovaMind, Вы писали:


NM>Есть 12 монет.

NM>Одна отличается по весу.
NM>За 3(три) взвешиваня найти эту монету и определить тяжелее она или легче.

NM>Image: Libra2.jpg


Нашлось у меня два-три часика свободного времени у компа сына с питоном на ходу.
Так что попробуем решить грубой силой, а не всякими там рассуждениями на две недели
Ну, поехали.

Разберёмся с порядком перебора.
Нам надо уметь перебирать уникальные наборы монет вида "три монеты из множества против двух монет из того же множества). при этом их стоит перебирать в порядке возрастания суммарного числа элементов множеств, так как чем больше монет в деле, тем, больше шансов, что в этой группе больше наборов.

  "для начала решим более простую задачу: напишем генератор таких пар подмножеств."
Начнём с того, что построим список пар размеров подмножеств.
Можем заметить, что может можно написать и поумнее, но мне лень, тем более, что время работы этого генератора, очевидно, очень маленькое.

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())]


Итого, нам осталось написать только сам перебор взвешиваний.
Самую муторнуя часть -- генератор варинтов расположения монет на чашках весов, мы уже написали!


Нам надо перебирать разные стратегии взвешивания, и искать такую, в результате которой у нас в каждом листе дерева будет один исход (такая-то монета фальшивая и мы знаем тяжелее она или легче)

При этом понятно, что на каждом этапе у нас есть какой-то набор монет, про который мы уже знаем, что они не фальшивые, и какой-то набор, про которые ещё не ясно.
Соответственно, ясно, что любое осмысленное взвешивание -- это взвешивание какого-то количества монет, про которые мы пока не знаем, фальшивы ли они против какого-то количества монет из того же множества. При этом число монет на чашах, перед взвешиванием, надо уровнять монетами, которые уже точно нефальшивые.

Итого, любое взвешивание -- это два набора монет (левая и правая чашка), про которые мы пока не знаем, фальшивые ли они. При этом число монет в наборах, может отличаться не больше, чем на количество уже установленных нефальшивых.

Как раз генератор таких множеств мы и написали выше

Теперь надо формализовать саму задачу про взвешивания.

Для удобства занумеруем монеты числами от 1 до числа монет, а возможные результаты поиска фальшивой монеты (какая монета фальшивая и легче она ли тяжелее) за отрицательные номера монет (значит эта фальшивая монета легче) и положительные (значит эта монета тяжелее)

Зачем это надо? Что бы не перебирать, по возможности, эквивалентные стратегии. Например не перебирать разные способы разложить уже установленные нефальшивые монеты.

Итак.
Опишем нашу задачу на языке python 3.
COINS_COUNT = 12 # число монет
SCALE_RESULTS = "<=>" # возможные результаты взвешивания

ALL_COINS = set(range(1,COINS_COUNT+1)) # просто множество всех имеющихся у нас монет   
ALL_STATES = ALL_COINS | {-s for s in ALL_COINS} # а это множество возможных исходов. 

MAX_SPLIT_SIZE = COINS_COUNT // 3 + 1 # Это эвристика, на самом деле её, наверное можно доказать, но можно попробовать запустить с COINS_COUNT.


Обсудим эвристику MAX_SPLIT_SIZE = COINS_COUNT // 3 + 1
На мой взгляд, её можно доказать (если решение существует с полным перебором, то существует и с таким ограничением), но строго доказывать мне лень.
Я пробовал запускать нерешаемые версии задачи (что бы перебирать всё до конца) с этой эвристикой и без неё. Без неё примерно в два раза дольше, так что если очень надо, можно просто отказаться.

Ещё есть эвристика, что если взвешивание не последнее (есть неразличимые состояния), а какой-то результат взвешивания получить нельзя, то эту ветку можно отсечь.
Я пробовал запускать нерешаемую задачу с ней и без неё -- эффект не более 10%. Так что её, для простоты, можно просто не использовать.
В окончательном варианте функции я её закомментировал.

Ну и осталась всего одна вспомогательная задача:
"Взвесить" какой-то набор возможных исходов (то есть применить его к какому-то множеству состояний
def _scale_all_states( left, right, states ) :
    """
    разбить множество состояний на случаи < = >
    """
    res = { "count":None, '<':[], '=':[], '>':[] }
    for s in states :
        if -s in left or s in right :
            res['<'].append( s )
        elif s in left or -s in right :
            res['>'].append( s )
        else :
            res['='].append( s )
    return res


  "проверим, что получилось"
_scale_all_states( {1, 2, 3, 4}, {5, 6, 7, 8}, ALL_STATES )
Печатает:
{'count': None,
 'vs': ({1, 2, 3, 4}, {5, 6, 7, 8}),
 '<': [5, 6, 7, 8, -1, -4, -3, -2],
 '=': [9, 10, 11, 12, 13, -13, -12, -11, -9, -10],
 '>': [1, 2, 3, 4, -8, -7, -6, -5]}


Ну, что же, осталось только научиться заменять подмножества состояний на следующее взвешивание, добавить перебор множеств в порядке, который мы научились генерировать выше, отсечения и подсчёт максимального числа взвешиваний на каждом из путей.
Мы почти решили задачку!

def get_scale_strategy( states, max_count, coins_count=None, max_split_size=MAX_SPLIT_SIZE ) :
    """
    Возвращает стратегию взвешинвания на двухчашесных весах, или None, если стратегии нет
    позволяющую найти отличающуюся по весу единственную фальшивую монету в наборе
    states -- множество возвожных исходов
    max_count - максимальное число взвешиваний
    coins_count -- общее число монет. Еслидостоверно нефальшивых сначала нет, то определяется по states
    """
    if len(states) <= 1 : # нечего решать, возвращаем некий формальный результат
        return {"count":0, "vs":(set(),set()), "<":[], "=":list(states), ">":[]} 
    
    if len(states) > 3**max_count :
        return None #отсекаем, так как это множество состояний за оставшееся число взвешиваний не разделяется
    
    unknown = {abs(c) for c in states} # множество монет, про которые пока не ясно, фальшивые ли они
    coins_count = coins_count or len( unknown )
    for l, r in gen_sorted_pairs(unknown, coins_count - len(unknown), max_split_size) :
        scale_res = _scale_all_states( l, r, states )
        #if max_count == 3 and len(l) == 4 and len(r) == 4:
        #    print( l, r, scale_res )
        max_state_len = max( len(scale_res[k]) for k in SCALE_RESULTS )
        if max_state_len > 3**(max_count-1) :
            continue #отсекаем, так как это множество состояний за оставшееся число взвешиваний не разделяется
        if max_state_len <= 1 : # Мы нашли решение за одно взвешивание!!!
            scale_res["count"] = 1
            return scale_res
        #if max( len(scale_res[k]) for k in SCALE_RESULTS ) == 0:
        #    continue #Это только эвристика, но правдоподобная!
        if max_count <= 1 :
            continue # больше ничего сделать нельзя
        
        # Итак, с отсечениями покончено, давайте запускать поиск стратегии рекурсивно!
        scale_count = 0
        for k in SCALE_RESULTS :
            substrategy = get_scale_strategy( scale_res[k], max_count-1, coins_count, max_split_size )
            if substrategy is None : # разделить не удалось!
                scale_res = None
                break
            scale_res[k] = substrategy
            scale_count = max(substrategy["count"], scale_count)
        if scale_res : # Нашли решение для всех трёх результатов взвешивания!
            scale_res["count"] = scale_count + 1
            return scale_res 
    return None


  "проверим, что получилось"
get_strategy( ALL_STATES, 3 )
Печатает (174ms):
{'count': 3,
 'vs': ({1, 2, 3, 7}, {4, 5, 6, 8}),
 '<': {'count': 2,
  'vs': ({1, 2}, {3, 4, 7}),
  '<': {'count': 1, 'vs': ({1}, {2}), '<': [-1], '=': [4], '>': [-2]},
  '=': {'count': 1, 'vs': ({5}, {6}), '<': [6], '=': [8], '>': [5]},
  '>': {'count': 1, 'vs': ({3}, set()), '<': [-3], '=': [-7], '>': []}},
 '=': {'count': 2,
  'vs': ({9}, {10, 11}),
  '<': {'count': 1, 'vs': ({10}, {11}), '<': [11], '=': [-9], '>': [10]},
  '=': {'count': 1, 'vs': ({12}, set()), '<': [-12], '=': [], '>': [12]},
  '>': {'count': 1, 'vs': ({10}, {11}), '<': [-10], '=': [9], '>': [-11]}},
 '>': {'count': 2,
  'vs': ({1, 2}, {3, 4, 7}),
  '<': {'count': 1, 'vs': ({3}, set()), '<': [], '=': [7], '>': [3]},
  '=': {'count': 1, 'vs': ({5}, {6}), '<': [-5], '=': [-8], '>': [-6]},
  '>': {'count': 1, 'vs': ({1}, {2}), '<': [2], '=': [-4], '>': [1]}}}

а
COINS_COUNT = 13
SCALE_RESULTS = "<=>" # возможные результаты взвешивания

ALL_COINS = set(range(1,COINS_COUNT+1))    
ALL_STATES = ALL_COINS | {-s for s in ALL_COINS}
MAX_SPLIT_SIZE = COINS_COUNT

get_strategy( ALL_STATES, 3 )

за 2 секунды находит, что решения нет


Теперь можно пробовать решать разные двухчашечные задачи про уникальные монеты.
Например, проверить, а можно ли так же найти фальшивую среди 40 монет за 4 взвешивания?

  "полная версия кода"
COINS_COUNT = 13
SCALE_RESULTS = "<=>" # возможные результаты взвешивания

ALL_COINS = set(range(1,COINS_COUNT+1))    
ALL_STATES = ALL_COINS | {-s for s in ALL_COINS}
MAX_SPLIT_SIZE = COINS_COUNT

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))

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

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

def _scale_all_states( left, right, states ) :
    """
    разбить множество состояний на случаи < = >
    """
    res = { "count":None, "vs": (left, right), '<':[], '=':[], '>':[] }
    for s in states :
        if -s in left or s in right :
            res['<'].append( s )
        elif s in left or -s in right :
            res['>'].append( s )
        else :
            res['='].append( s )
    return res
    
def get_scale_strategy( states, max_count, coins_count=None, max_split_size=MAX_SPLIT_SIZE ) :
    """
    Возвращает стратегию взвешинвания на двухчашесных весах, или None, если стратегии нет
    позволяющую найти отличающуюся по весу единственную фальшивую монету в наборе
    states -- множество возвожных исходов
    max_count - максимальное число взвешиваний
    coins_count -- общее число монет. Еслидостоверно нефальшивых сначала нет, то определяется по states
    """
    if len(states) <= 1 : # нечего решать, возвращаем некий формальный результат
        return {"count":0, "vs":(set(),set()), "<":[], "=":list(states), ">":[]} 
    
    if len(states) > 3**max_count :
        return None #отсекаем, так как это множество состояний за оставшееся число взвешиваний не разделяется
    
    unknown = {abs(c) for c in states} # множество монет, про которые пока не ясно, фальшивые ли они
    coins_count = coins_count or len( unknown )
    for l, r in gen_sorted_pairs(unknown, coins_count - len(unknown), max_split_size) :
        scale_res = _scale_all_states( l, r, states )
        #if max_count == 3 and len(l) == 4 and len(r) == 4:
        #    print( l, r, scale_res )
        max_state_len = max( len(scale_res[k]) for k in SCALE_RESULTS )
        if max_state_len > 3**(max_count-1) :
            continue #отсекаем, так как это множество состояний за оставшееся число взвешиваний не разделяется
        if max_state_len <= 1 : # Мы нашли решение за одно взвешивание!!!
            scale_res["count"] = 1
            return scale_res
        #if max( len(scale_res[k]) for k in SCALE_RESULTS ) == 0:
        #    continue #Это только эвристика, но правдоподобная!
        if max_count <= 1 :
            continue # больше ничего сделать нельзя
        
        # Итак, с отсечениями покончено, давайте запускать поиск стратегии рекурсивно!
        scale_count = 0
        for k in SCALE_RESULTS :
            substrategy = get_scale_strategy( scale_res[k], max_count-1, coins_count, max_split_size )
            if substrategy is None : # разделить не удалось!
                scale_res = None
                break
            scale_res[k] = substrategy
            scale_count = max(substrategy["count"], scale_count)
        if scale_res : # Нашли решение для всех трёх результатов взвешивания!
            scale_res["count"] = scale_count + 1
            return scale_res 
    return None

get_strategy( ALL_STATES, 3 )
Re: Задачке 45+ лет.
Здравствуйте, NovaMind, Вы писали:


NM>Есть 12 монет.

NM>Одна отличается по весу.
NM>За 3(три) взвешиваня найти эту монету и определить тяжелее она или легче.

NM>Image: Libra2.jpg


Нашлось у меня два-три часика свободного времени у компа сына с питоном на ходу.
Так что попробуем решить грубой силой, а не всякими там рассуждениями на две недели
Ну, поехали.

Разберёмся с порядком перебора.
Нам надо уметь перебирать уникальные наборы монет вида "три монеты из множества против двух монет из того же множества). при этом их стоит перебирать в порядке возрастания суммарного числа элементов множеств, так как чем больше монет в деле, тем, больше шансов, что в этой группе больше наборов.

  "для начала решим более простую задачу: напишем генератор таких пар подмножеств."
Начнём с того, что построим список пар размеров подмножеств.
Можем заметить, что может можно написать и поумнее, но мне лень, тем более, что время работы этого генератора, очевидно, очень маленькое.

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())]


Итого, нам осталось написать только сам перебор взвешиваний.
Самую муторнуя часть -- генератор варинтов расположения монет на чашках весов, мы уже написали!


Нам надо перебирать разные стратегии взвешивания, и искать такую, в результате которой у нас в каждом листе дерева будет один исход (такая-то монета фальшивая и мы знаем тяжелее она или легче)

При этом понятно, что на каждом этапе у нас есть какой-то набор монет, про который мы уже знаем, что они не фальшивые, и какой-то набор, про которые ещё не ясно.
Соответственно, ясно, что любое осмысленное взвешивание -- это взвешивание какого-то количества монет, про которые мы пока не знаем, фальшивы ли они против какого-то количества монет из того же множества. При этом число монет на чашах, перед взвешиванием, надо уровнять монетами, которые уже точно нефальшивые.

Итого, любое взвешивание -- это два набора монет (левая и правая чашка), про которые мы пока не знаем, фальшивые ли они. При этом число монет в наборах, может отличаться не больше, чем на количество уже установленных нефальшивых.

Как раз генератор таких множеств мы и написали выше

Теперь надо формализовать саму задачу про взвешивания.

Для удобства занумеруем монеты числами от 1 до числа монет, а возможные результаты поиска фальшивой монеты (какая монета фальшивая и легче она ли тяжелее) за отрицательные номера монет (значит эта фальшивая монета легче) и положительные (значит эта монета тяжелее)

Зачем это надо? Что бы не перебирать, по возможности, эквивалентные стратегии. Например не перебирать разные способы разложить уже установленные нефальшивые монеты.

Итак.
Опишем нашу задачу на языке python 3.
COINS_COUNT = 12 # число монет
SCALE_RESULTS = "<=>" # возможные результаты взвешивания

ALL_COINS = set(range(1,COINS_COUNT+1)) # просто множество всех имеющихся у нас монет   
ALL_STATES = ALL_COINS | {-s for s in ALL_COINS} # а это множество возможных исходов. 

MAX_SPLIT_SIZE = COINS_COUNT // 3 + 1 # Это эвристика, на самом деле её, наверное можно доказать, но можно попробовать запустить с COINS_COUNT.


Обсудим эвристику MAX_SPLIT_SIZE = COINS_COUNT // 3 + 1
На мой взгляд, её можно доказать (если решение существует с полным перебором, то существует и с таким ограничением), но строго доказывать мне лень.
Я пробовал запускать нерешаемые версии задачи (что бы перебирать всё до конца) с этой эвристикой и без неё. Без неё примерно в два раза дольше, так что если очень надо, можно просто отказаться.

Ещё есть эвристика, что если взвешивание не последнее (есть неразличимые состояния), а какой-то результат взвешивания получить нельзя, то эту ветку можно отсечь.
Я пробовал запускать нерешаемую задачу с ней и без неё -- эффект не более 10%. Так что её, для простоты, можно просто не использовать.
В окончательном варианте функции я её закомментировал.

Ну и осталась всего одна вспомогательная задача:
"Взвесить" какой-то набор возможных исходов (то есть применить его к какому-то множеству состояний
def _scale_all_states( left, right, states ) :
    """
    разбить множество состояний на случаи < = >
    """
    res = { "count":None, '<':[], '=':[], '>':[] }
    for s in states :
        if -s in left or s in right :
            res['<'].append( s )
        elif s in left or -s in right :
            res['>'].append( s )
        else :
            res['='].append( s )
    return res


  "проверим, что получилось"
_scale_all_states( {1, 2, 3, 4}, {5, 6, 7, 8}, ALL_STATES )
Печатает:
{'count': None,
 'vs': ({1, 2, 3, 4}, {5, 6, 7, 8}),
 '<': [5, 6, 7, 8, -1, -4, -3, -2],
 '=': [9, 10, 11, 12, 13, -13, -12, -11, -9, -10],
 '>': [1, 2, 3, 4, -8, -7, -6, -5]}


Ну, что же, осталось только научиться заменять подмножества состояний на следующее взвешивание, добавить перебор множеств в порядке, который мы научились генерировать выше, отсечения и подсчёт максимального числа взвешиваний на каждом из путей.
Мы почти решили задачку!

def get_scale_strategy( states, max_count, coins_count=None, max_split_size=MAX_SPLIT_SIZE ) :
    """
    Возвращает стратегию взвешинвания на двухчашесных весах, или None, если стратегии нет
    позволяющую найти отличающуюся по весу единственную фальшивую монету в наборе
    states -- множество возвожных исходов
    max_count - максимальное число взвешиваний
    coins_count -- общее число монет. Еслидостоверно нефальшивых сначала нет, то определяется по states
    """
    if len(states) <= 1 : # нечего решать, возвращаем некий формальный результат
        return {"count":0, "vs":(set(),set()), "<":[], "=":list(states), ">":[]} 
    
    if len(states) > 3**max_count :
        return None #отсекаем, так как это множество состояний за оставшееся число взвешиваний не разделяется
    
    unknown = {abs(c) for c in states} # множество монет, про которые пока не ясно, фальшивые ли они
    coins_count = coins_count or len( unknown )
    for l, r in gen_sorted_pairs(unknown, coins_count - len(unknown), max_split_size) :
        scale_res = _scale_all_states( l, r, states )
        #if max_count == 3 and len(l) == 4 and len(r) == 4:
        #    print( l, r, scale_res )
        max_state_len = max( len(scale_res[k]) for k in SCALE_RESULTS )
        if max_state_len > 3**(max_count-1) :
            continue #отсекаем, так как это множество состояний за оставшееся число взвешиваний не разделяется
        if max_state_len <= 1 : # Мы нашли решение за одно взвешивание!!!
            scale_res["count"] = 1
            return scale_res
        #if max( len(scale_res[k]) for k in SCALE_RESULTS ) == 0:
        #    continue #Это только эвристика, но правдоподобная!
        if max_count <= 1 :
            continue # больше ничего сделать нельзя
        
        # Итак, с отсечениями покончено, давайте запускать поиск стратегии рекурсивно!
        scale_count = 0
        for k in SCALE_RESULTS :
            substrategy = get_scale_strategy( scale_res[k], max_count-1, coins_count, max_split_size )
            if substrategy is None : # разделить не удалось!
                scale_res = None
                break
            scale_res[k] = substrategy
            scale_count = max(substrategy["count"], scale_count)
        if scale_res : # Нашли решение для всех трёх результатов взвешивания!
            scale_res["count"] = scale_count + 1
            return scale_res 
    return None


  "проверим, что получилось"
get_scale_strategy( ALL_STATES, 3 )
Печатает (174ms):
{'count': 3,
 'vs': ({1, 2, 3, 7}, {4, 5, 6, 8}),
 '<': {'count': 2,
  'vs': ({1, 2}, {3, 4, 7}),
  '<': {'count': 1, 'vs': ({1}, {2}), '<': [-1], '=': [4], '>': [-2]},
  '=': {'count': 1, 'vs': ({5}, {6}), '<': [6], '=': [8], '>': [5]},
  '>': {'count': 1, 'vs': ({3}, set()), '<': [-3], '=': [-7], '>': []}},
 '=': {'count': 2,
  'vs': ({9}, {10, 11}),
  '<': {'count': 1, 'vs': ({10}, {11}), '<': [11], '=': [-9], '>': [10]},
  '=': {'count': 1, 'vs': ({12}, set()), '<': [-12], '=': [], '>': [12]},
  '>': {'count': 1, 'vs': ({10}, {11}), '<': [-10], '=': [9], '>': [-11]}},
 '>': {'count': 2,
  'vs': ({1, 2}, {3, 4, 7}),
  '<': {'count': 1, 'vs': ({3}, set()), '<': [], '=': [7], '>': [3]},
  '=': {'count': 1, 'vs': ({5}, {6}), '<': [-5], '=': [-8], '>': [-6]},
  '>': {'count': 1, 'vs': ({1}, {2}), '<': [2], '=': [-4], '>': [1]}}}

а
COINS_COUNT = 13
SCALE_RESULTS = "<=>" # возможные результаты взвешивания

ALL_COINS = set(range(1,COINS_COUNT+1))    
ALL_STATES = ALL_COINS | {-s for s in ALL_COINS}
MAX_SPLIT_SIZE = COINS_COUNT

get_strategy( ALL_STATES, 3 )

за 2 секунды находит, что решения нет


Теперь можно пробовать решать разные двухчашечные задачи про уникальные монеты.
Например, проверить, а можно ли так же найти фальшивую среди 40 монет за 4 взвешивания?

  "полная версия кода"
COINS_COUNT = 13
SCALE_RESULTS = "<=>" # возможные результаты взвешивания

ALL_COINS = set(range(1,COINS_COUNT+1))    
ALL_STATES = ALL_COINS | {-s for s in ALL_COINS}
MAX_SPLIT_SIZE = COINS_COUNT

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))

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

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

def _scale_all_states( left, right, states ) :
    """
    разбить множество состояний на случаи < = >
    """
    res = { "count":None, "vs": (left, right), '<':[], '=':[], '>':[] }
    for s in states :
        if -s in left or s in right :
            res['<'].append( s )
        elif s in left or -s in right :
            res['>'].append( s )
        else :
            res['='].append( s )
    return res
    
def get_scale_strategy( states, max_count, coins_count=None, max_split_size=MAX_SPLIT_SIZE ) :
    """
    Возвращает стратегию взвешинвания на двухчашесных весах, или None, если стратегии нет
    позволяющую найти отличающуюся по весу единственную фальшивую монету в наборе
    states -- множество возвожных исходов
    max_count - максимальное число взвешиваний
    coins_count -- общее число монет. Еслидостоверно нефальшивых сначала нет, то определяется по states
    """
    if len(states) <= 1 : # нечего решать, возвращаем некий формальный результат
        return {"count":0, "vs":(set(),set()), "<":[], "=":list(states), ">":[]} 
    
    if len(states) > 3**max_count :
        return None #отсекаем, так как это множество состояний за оставшееся число взвешиваний не разделяется
    
    unknown = {abs(c) for c in states} # множество монет, про которые пока не ясно, фальшивые ли они
    coins_count = coins_count or len( unknown )
    for l, r in gen_sorted_pairs(unknown, coins_count - len(unknown), max_split_size) :
        scale_res = _scale_all_states( l, r, states )
        #if max_count == 3 and len(l) == 4 and len(r) == 4:
        #    print( l, r, scale_res )
        max_state_len = max( len(scale_res[k]) for k in SCALE_RESULTS )
        if max_state_len > 3**(max_count-1) :
            continue #отсекаем, так как это множество состояний за оставшееся число взвешиваний не разделяется
        if max_state_len <= 1 : # Мы нашли решение за одно взвешивание!!!
            scale_res["count"] = 1
            return scale_res
        #if max( len(scale_res[k]) for k in SCALE_RESULTS ) == 0:
        #    continue #Это только эвристика, но правдоподобная!
        if max_count <= 1 :
            continue # больше ничего сделать нельзя
        
        # Итак, с отсечениями покончено, давайте запускать поиск стратегии рекурсивно!
        scale_count = 0
        for k in SCALE_RESULTS :
            substrategy = get_scale_strategy( scale_res[k], max_count-1, coins_count, max_split_size )
            if substrategy is None : # разделить не удалось!
                scale_res = None
                break
            scale_res[k] = substrategy
            scale_count = max(substrategy["count"], scale_count)
        if scale_res : # Нашли решение для всех трёх результатов взвешивания!
            scale_res["count"] = scale_count + 1
            return scale_res 
    return None

get_scale_strategy( ALL_STATES, 3 )