Обход списков 0, 1 с ограничением - PullRequest
Новая
       35

Обход списков 0, 1 с ограничением

1 голос
/ 03 августа 2020

приношу свои извинения, если где-то был дан ответ, я попытался выполнить поиск, но я не знаю, есть ли у этой проблемы конкретное c имя, поэтому в моем поиске ничего не нашлось ...

У меня есть список объектов, и каждый из этих объектов может быть принят или отклонен. Каждой комбинации присваивается значение, а некоторые комбинации недействительны. (Так, например, у нас есть 4 объекта, а объекты 1 и 2 не go вместе, тогда каждая комбинация, в которой есть объекты 1 и 2, как принятая, недействительна.) Заранее не известно, какие объекты не go вместе, и невозможно найти недопустимые, просто просматривая пары. (Например, возможно, что объекты 1, 2 действительны вместе, объекты 2,3 действительны, объекты 1,3 действительны, но 1,2,3 недействительны.) Я смоделировал это как списки 0 и 1, поэтому Теперь я хочу пройти по этим спискам, чтобы найти тот, у которого максимальное значение, эффективным способом.

Моя идея состояла в том, чтобы пройти по спискам как по дереву, начиная со всех нулей, а затем на каждом шаге переворачивая ноль в один, поэтому, например, для 3 объектов это дает дерево 

                000
            /    |    \
        100     010     001
        / \     / \     / \
      110 101 110 011 101 011
        \  \   \   /   /   /
                111

, что на самом деле хуже, чем просто перечисление всех параметров 2 ^ n, поскольку есть дубликаты, но на каждом узле я мог бы остановиться, если бы обнаружил, что это недействительно. Сохраняя недопустимые комбинации единиц и сохраняя список всех уже посещенных узлов, я мог убедиться, что я не повторно посещаю уже проверенные узлы. (Но мне все равно пришлось бы их проверить, если бы они уже были посещены)

Есть ли лучший способ сделать это?

1 Ответ

0 голосов
/ 03 августа 2020

Вы можете попытаться построить дерево вариантов (максимум 2 ^ n вариантов, как вы заметили), но вырезать неподходящие ветви как можно раньше.

В примере ниже я установил две бинарные маски - нет 1,2,3 вместе и нет 2,4 вместе 

def buildtree(x, maxsize, level, masks):
    if level == maxsize:
        print("{0:b}".format(x).zfill(maxsize))
    else:
        buildtree(x, maxsize, level + 1, masks)
        t = x | (1 << level)
        good = True
        for m in masks:
            if (t & m) == m:
                good = False
                break
        if good:
            buildtree(t, maxsize, level + 1, masks)

buildtree(0, 4, 0, [7, 10])

0000
1000
0100
1100
0010
0110
0001
1001
0101
1101
0011

Можно также удалить некоторые маски, но код будет более сложным

...