集覆盖启发式

Question

套盖问题在这里解释。

我使用的列表被视为集。正如我所发现的，在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有一个洗牌函数。但是，我不确定，它是否能够生成列表的所有排列；如果它在一个时间循环中永远运行。到目前为止已经足够了。

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使用哪些变量名？

因为，我把编码作为一种爱好，有什么更好的方式让你更容易阅读和理解呢？

Answer 1

验证

这是：

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

如果这是一个概念脚本的证明，对您的目的来说可能是好的，但是如果您需要严格的输入验证，loads允许太多的变化。您还需要检查这是一个整数列表，而不是其他任何东西。否则，用户可能会提供一本字典字典，其中包含字符串字典列表，将字符串映射为nulls，您的程序就会突然崩溃。

阴影

您有一个大的混合全局代码交错(没有空行)与函数定义。在其他方面，您将从代码中看到奇怪的效果，例如

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应用于输入理解，并对超过一次的计数提出警告(或错误)。如果您希望将重复元素悄悄折叠到sets中，这可以在一行中完成。

另一个令人惊叹的街区是

# 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检查。我将把它作为一种练习，让你知道这个生物的计算复杂性是什么，以及如果你转换成真实的集合，它将如何被减少。