扩大和缩小集合列表

Question

好吧，这是一个很难解释的问题。正是我在解释它时遇到的困难使得创建我想要的循环变得困难。你知道吗

考虑一下这10套的清单

my_list_of_sets = [ 
{0,1,2,3,4,5,7,9},
{0,1,2,4,5,6,7}, 
{0,1,2,3,4,8,9},
{1,3,4,5,6,7,8,9}, 
{1,2,3,4,5,6}, 
{3,4,5,6,7,8,9}, 
{1,2,3,5,6,8,9},
{2,3,4,5,6,7,8}, 
{2,5,6,7,8,9}, 
{3,4,6,7,8,9}]

我想应用以下类型的规则来展开这些列表的交集积。你知道吗

规则1:集合[0]的列表可以与索引为0,1,2,3,4,5,7,9的集合列表相交。你知道吗

规则2:集合[1]的列表可以与索引为0,1,2,4,5,6,7的集合的列表相交

你知道吗RuleX:我的集合列表[x] 可以与我的\u列表\u集合相交，索引在我的\u列表\u集合中[x]

规则n:集合的集合列表[1]不能与集合的集合列表[3]或集合的集合列表[8]或集合的集合列表[9]共存。你知道吗

在我展开一个可以“共存”的集合的输出列表之前，我一直在递归中这样做。你知道吗

我执行的循环流

my_output_list_item = my_list_of_sets[0] & my_list_of_sets[0]

{0,1,2,3,4,5,7,9}

my_output_list_item = my_output_list_item & my_list_of_sets[1] #Skipped no index

{1,2,4,5,7}

然后我可以继续与索引2，4，5，7相交。。。你知道吗

my_output_list_item = my_output_list_item & my_list_of_sets[2] 

{0,1,2,4}

my_output_list_item = my_output_list_item & my_list_of_sets[4]  

{1,2,4}

直到我沿着我的\u列表\u集合[0]作为索引进入我的\u列表\u集合，并找到一个没有“异议”{1,2,4}的集合。对不起，我想不出一个更好的词来形容可以相交的集合。你知道吗

第1期 您会注意到，如果循环的第一次迭代是任意的，则索引3会在第一次迭代中被删除。如果第一个过程是任意的，我将得到一个不同的结果。你知道吗

my_output_list_item = my_list_of_sets[0] & my_list_of_sets[2] #Skipped one index

{0,1,2,3,4,9}

my_output_list_item = my_output_list_item & my_list_of_sets[3]

{1,3,4,9}

my_output_list_item = my_output_list_item & my_list_of_sets[4]

{1,3,4}

my_output_list_item = my_output_list_item & my_list_of_sets[1]

{1,4}

我得到了{1,2,4}和{1,4}，基于我开始交叉点的索引。 这意味着我的输入数据顺序与结果相关，它是一个集合，没有固有的顺序。你知道吗

因此，我试图通过使用滚动切片窗口沿着集合执行从所有起始索引开始的交集来解决问题1。 这是我目前掌握的代码。你知道吗

my_output_list = set()
for i in range(len(my_list_of_sets)):
    set_as_list = list(my_list_of_sets[i])  #need a list here because it will be indexed from various offsets
    for slice_index in range(0, len(set_as_list)):  # the index is used to make sure all items are started with every other bd
        new_item = my_list_of_sets[i]
        for bd in set_as_list[slice_index::] + set_as_list[:slice_index:]:
            if bd in new_item:  # need this if statement as new_item is getting smaller each loop of bd.
                new_item = new_item.intersection(my_list_of_sets[bd])
        my_output_list.add(frozenset(new_item))

这将枚举到一个由15个集合组成的my\u output\u列表中。你知道吗

问题2： 但是，此代码仍然缺少一些组合

my_output_list_item = my_list_of_sets[0] 
my_output_list_item = my_output_list_item & my_list_of_sets[2] #Skipped one index
my_output_list_item = my_output_list_item & my_list_of_sets[4] #Skipped one index
my_output_list_item = my_output_list_item & my_list_of_sets[1]

{1,2,4}

my_output_list_item = my_list_of_sets[0] 
my_output_list_item = my_output_list_item & my_list_of_sets[2] #Skipped one index
my_output_list_item = my_output_list_item & my_list_of_sets[9] #Skipped two index
my_output_list_item = my_output_list_item & my_list_of_sets[3]
my_output_list_item = my_output_list_item & my_list_of_sets[4]

{3,4}

my_output_list_item = my_list_of_sets[0] 
my_output_list_item = my_output_list_item & my_list_of_sets[2] #Skipped one index
my_output_list_item = my_output_list_item & my_list_of_sets[0] #Skipped three index
my_output_list_item = my_output_list_item & my_list_of_sets[1]
my_output_list_item = my_output_list_item & my_list_of_sets[2]
my_output_list_item = my_output_list_item & my_list_of_sets[4]

{1,2,4} 等等。你知道吗

我相信这种缺失是由于滚动片{3,4}在索引值上顺序增加，忽略了一些可能的组合。你知道吗

因此，虽然我已经有了循环迭代0的滚动片bd，但我想我还需要一个itertools来遍历我的集合的所有组合中的索引。你知道吗

几次编辑。我不能用暴力来强制所有的连击并移除非法的连击。这是len 100列表，它是100^100个组合，而计算机不能这样做。 我知道我的答案可能在itertools中，但我并没有想象它适用于列表长度大于2的产品。你知道吗

Answer 1

从AIconstraint satisfaction的角度来看可能值得一试。如果你计算一个集合排除了多少东西，以及有多少集合排除了那个集合，你可以从约束最小的集合开始，向上计算。你知道吗

对于上面的示例（右轴是集合排除的对象数，下轴是集合排除的对象数）

   0 1 2 3 4 5 6 7 8 9
0: 1 1 1 1 1 1 0 1 0 1 | 2
1: 1 1 1 0 1 1 1 1 0 0 | 3
2: 1 1 1 1 1 0 0 0 1 1 | 3
3: 0 1 0 1 1 1 1 1 1 1 | 2
4: 0 1 1 1 1 1 1 0 0 0 | 4
5: 0 0 0 1 1 1 1 1 1 1 | 3
6: 0 1 1 1 0 1 1 0 1 1 | 3
7: 0 0 1 1 1 1 1 1 1 0 | 3
8: 0 0 1 0 0 1 1 1 1 1 | 4
9: 0 0 0 1 1 0 1 1 1 1 | 4
   - - - - - - - - - - 
   7 4 3 2 2 2 3 2 3 3 

约束和：

• 0=9
• 1=7
• 2=6
• 3=4
• 4=6
• 5=5
• 6=6
• 7=5
• 8=7
• 9=7

既然你已经解决了你的限制条件：

1. 从最小约束集开始：3
2. 三次擦去0，2，8
3. 添加下一个仍然有效的最小约束：5
4. 5擦去1，9，2
5. 添加下一个最小约束仍然有效：7
6. 7擦去4和6
7. 没有有效的了

你只剩下一组人：3，5，7