Установить эвристику обложки

Здесь объясняется проблема набора обложек.

Я использую списки, которые рассматриваются как наборы. Как я обнаружил, в Python управлять списками проще, чем наборами.

Первая часть алгоритма использует проверку ввода.

import json
from copy import deepcopy
import random

s =  input("Input list of integers (no repeating elements) for S with commas (eg. 1,2,3,4...) : ").split(',')
c =  input('enter list for C (eg. [[1,2,3],[4,5,6]]): ')
c = json.loads(c)
s = [int(a) for a in s]

random.seed()
miss = []
delete = []
remove = []
remove_t=[]
no = 0
def input_validation():
    # checking for missing elements.
    no = 0
    for a in range(0, len(c)):
        for b in range(0, len(c[a])):
            miss.append(c[a][b])
    for d in s:
        if d not in miss:
            print('False', d)
            no = 1
            break
    if no == 1:
        quit()
    # Throw out unwanted orderings of sub-lists
    for a in range(0, len(c)):
        c[a] = sorted(c[a])
    # Lists are treated as sets, so lists
    # with repeating elements is thrown out        
    for rem in range(0, len(c)):
        if len(c[rem]) != len(set(c[rem])):
            remove.append(c[rem])
    for rem_two in range(0, len(remove)):
        if remove[rem_two] in c:
            del c[c.index(remove[rem_two])]
    # Throw out lists that have elements that do
    # not exist in s.
    for j in range(0, len(c)):
        for jj in range(0, len(c[j])):
            if any(elem not in s for elem in c[j]):
                remove_t.append(c[j])
    for rem_two in range(0, len(remove_t)):
        if remove_t[rem_two] in c:
            del c[c.index(remove_t[rem_two])]
        

Вторая часть алгоритма использует биективное отображение, которое подготавливает его к основе программы. Я нашел в Интернете функцию, которая перемешивает список. Я уже знаю, что в Python есть функция перетасовки. Но я не был уверен, сможет ли он сгенерировать все перестановки в списке; если он работал вечно в цикле while. Пока этого достаточно.

s_copy = deepcopy(s)
input_validation()
# remove repeating lists
c = [c[x] for x in range(len(c)) if not(c[x] in c[:x])]
c_copy = deepcopy(c)
one_s = []
# See if there is sets
# with one element.
# and check them for a
# cover.
for a in c:
    if len(a) == 1:
        if a not in one_s:
            one_s.append(a)
if len(one_s) == len(s):
    print(one_s)
    quit()
def bijective_mapp():
    s_copy = deepcopy(s)
    for a in range(0, len(s)):
        s[a] = a+1
    for b in range(0, len(c)):
        for bb in range(0, len(c[b])):
            c[b][bb] = s_copy.index(c[b][bb])+1
bijective_mapp()
c = [sorted(y) for y in c]
def shuff(c, n):
    for i in range(n-1,0,-1):
        j = random.randint(0,i)
        c[i],c[j] = c[j],c[i]
c.append(sorted(c[len(c)-1]))

Третья и последняя часть программы сортирует список C особым образом, где все [1,x,x]'s сгруппированы вместе. Так что [4,x,x]'s с другим [4,x,x,...]'s. Когда reset переменная выполняется, список C перемешивается, пока цикл не достигнет steps итераций. По окончании цикла я выведу обложку с наибольшим количеством найденных наборов.

Переменная steps непрактичны; когда вход достаточно велик. Как мне и нужно, самое большое количество наборов найдено без экспоненциального времени. Причина постоянного перемешивания (и сортировки) в том, что кажется, что легче находить обложки.

n = len(s)
steps = n*(2**2)*((n*(2**2))-1)*((n*(2**2))-2)//6
reset = 0
c_elem = set()
set_cover = []
partial = []
for a in range(0, steps + 1):
    reset = reset + 1
    if reset > len(c):
        c_elem = set()
        reset = 0
        shuff(c, len(c))
        c = sorted(c, key=lambda parameter: parameter[0])
        set_cover = []
    c.append(c[0])
    del(c[0])
    for l in c:
        if not any(v in c_elem for v in l):
            set_cover.append(l)
            c_elem.update(l)
    # if exact solution not found,
    # then use partial solution
    if set_cover not in partial:
        partial.append(set_cover)
# get the largest set-cover found
list_of_partials = [len(r) for r in partial]
k = partial[list_of_partials.index(max(list_of_partials))]
# Reversing the Bijective mapping
# to the original input. But, its sorted.
for a in range(0, len(k)):
    for b in range(0, len(k[a])):
        l = s.index(k[a][b])
        k[a][b] = s_copy[l]
# Outputs the largest amount of sets found
print(k)

Какие простые оптимизации для функции input_validation что я мог использовать?

Есть ли более эффективные способы повысить эффективность вложенных циклов в третьей части алгоритма?

Какие имена переменных вы бы рекомендовали использовать для функции input_validation?

Поскольку я пишу код как хобби, что может быть более питоническим, чтобы облегчить вам чтение и понимание?

Проверка

Этот:

c =  input('enter list for C (eg. [[1,2,3],[4,5,6]]): ')
c = json.loads(c)

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

Затенение

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

no = 0
def input_validation():
    no = 0

Эти двое no переменные делают не относятся к одному и тому же, причем последнее следует за первым. Вырежьте свои глобальные объекты и передайте их через параметры функции и возвращаемые значения или создайте класс.

Значения диапазона по умолчанию

Падение 0, от них:

for a in range(0, len(c)):
    for b in range(0, len(c[a])):

Наборы

Я использую списки, которые рассматриваются как наборы. Как я обнаружил, в Python управлять списками проще, чем наборами.

Это … зловеще и немного сбивает с толку? Как мог set() быть худшим представлением реального набора, чем list()?

Среди множества последствий этого решения этот код:

if d not in miss

был увеличен с O (1) до O (n) раз. Вам действительно стоит потратить время на изучение того, как работать с настоящими наборами.

Связанный блок

for rem in range(0, len(c)):
    if len(c[rem]) != len(set(c[rem])):
        remove.append(c[rem])
for rem_two in range(0, len(remove)):
    if remove[rem_two] in c:
        del c[c.index(remove[rem_two])]

что потрясающе:

• Сформировать диапазон по показателям c вместо использования стандартного for x in c
• Временно сделать набор, только чтобы снова выбросить
• Создайте список значений для удаления вместо списка индексов для удаления
• Сформируем еще один диапазон по индексам remove вместо использования стандартного for x in remove
• Вызвать if in c, который выполняется за линейное время в цикле, который умножает его на O (n ^ 2)
• Вызвать линейное время c.index по сохраненному значению, вместо того, чтобы просто запомнить индекс

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

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

Еще один потрясающий блок —

# Throw out lists that have elements that do
# not exist in s.
for j in range(0, len(c)):
    for jj in range(0, len(c[j])):
        if any(elem not in s for elem in c[j]):
            remove_t.append(c[j])

Это цикл, содержащий вложенный цикл, содержащий any генератор, содержащий линейный in s чек. Я оставлю это вам в качестве упражнения, какова вычислительная сложность этого существа и как ее можно уменьшить, если преобразовать в реальные множества.