2022 PUZZLEUP

〇〇

7行4个1能算了
with recursive n as (select i-1 n from generate_series(1,128)t(i))
    ,b as (select 1<<(i-1) b from generate_series(1,7)t(i))
,p as(select n1.n n1,n2.n n2
      ,count(*) cnt
  from n n1, n n2, b
where n1.n<n2.n
       and (n1.n#n2.n)&b.b>0
group by n1.n ,n2.n
having count(*)=4)
,t as(select 1 lv,array[n1,n2]a, n1#n2 n3 from p where n1=0
union all
select lv+1,a||array[n],n3#n from t,n where n>a[lv+1] and n<>127-n3 and array_position(a,127-n)is null  and lv+1= ( select count(*) from p q, unnest(a)

u(c) where n1=c and n2=n)
)
select * from t where lv=7 limit 4;
lv |             a              | n3
----+----------------------------+----
  7 | {0,15,51,60,85,90,102,105} |  0
  7 | {0,15,53,58,83,92,102,105} |  0
  7 | {0,15,51,60,86,89,**,106} |  0
  7 | {0,15,54,57,83,92,**,106} |  0
(4 行记录)


Time: 42621.588 ms (00:42.622)

newkid

你是假设0一定会出现在结果集中？而且这个结果集还是最大的？这要如何证明呢？

newkid

〇〇 发表于 2022-12-6 07:34
同一个数，和全零异或得a，和全一异或得b，ab中必有一个数1的位数少于总位数的一半，题目要求大于总位数一 ...

你这个”同理“，跳跃太大，我看不出如何从全零和全1的情况推理出来。
我是这样证明的：反证法


假设a列1的位数a, b列1的位数为b, a,b互为反码, a+b=9
假设c列有A个1与a重合，有B个1与b重合, c的1位数为A+B
且集合{a,b,c}满足条件

a,c异或后1的个数必须>=5:
a-A+B >=5

b,c异或后1的个数必须>=5:
b-B+A >=5

两边相加：a+b>=10 与a+b=9矛盾, 所以a,b不能同时出现。

〇〇

看7行4个1的二进制表示
mydb=# with t(a) as (values(array[0,15,51,60,85,90,102,105]))
mydb-# select unnest(a)::bit(7) i from t;
    i
---------

　０００００００

　０００１１１１

　０１１００１１

　０１１１１００

　１０１０１０１

　１０１１０１０

　１１００１１０

　１１０１００１

去掉第一行全零

后面7行和7列组成的矩阵按照左上右下对角线对称

应该是碰巧,这个就不是了

with t(a) as (values(array[0,15,53,58,83,92,102,105]))

select unnest(a)::bit(7) i from t;

newkid

〇〇 发表于 2022-12-7 08:36
看7行4个1的二进制表示mydb=# with t(a) as (values(array[0,15,51,60,85,90,102,105]))mydb-# select unne ...

这能说明什么呢？你没有证明为什么全零一定要包含在里面，而且这样得到的集合最大。我看你的SQL里也仅仅考虑了4个1的那些，其他都跳过，这也能证明吗？

〇〇

没有证明,就是发现一些现象,看有没有规律,对称这个已经证明不存在了

〇〇

恢复>=5写法,保留n1=0
8行取5个的结果，用max(lv)+1求出最多4列,显示实际的数如下，把这些数前面统一加一个0，就是9行取5个，至少有4列的结果
with recursive n as (select i-1 n from generate_series(1,256)t(i))
    ,b as (select 1<<(i-1) b from generate_series(1,8)t(i))
,p as(select n1.n n1,n2.n n2
      ,count(*) cnt
  from n n1, n n2, b
where n1.n<n2.n
       and (n1.n#n2.n)&b.b>0
group by n1.n ,n2.n
having count(*)>=5)
,t as(select 1 lv,array[n1,n2]a, n1#n2 n3 from p where n1=0
union all
select lv+1,a||array[n],n3#n from t,n where n>a[lv+1] and n<>255-n3 and array_position(a,255-n)is null  and lv+1= ( select count(*) from p q, unnest(a)

u(c) where n1=c and n2=n)
)
select * from t where lv=3 limit 20;
lv |        a        | n3
----+-----------------+---
  3 | {0,126,185,199} |  0
  3 | {0,125,186,199} |  0
  3 | {0,124,187,199} |  0
  3 | {0,123,188,199} |  0
  3 | {0,122,189,199} |  0
  3 | {0,121,190,199} |  0
  3 | {0,126,181,203} |  0
  3 | {0,125,182,203} |  0
  3 | {0,124,183,203} |  0
  3 | {0,119,188,203} |  0
  3 | {0,118,189,203} |  0
  3 | {0,117,190,203} |  0
  3 | {0,126,179,205} |  0
  3 | {0,123,182,205} |  0
  3 | {0,122,183,205} |  0
  3 | {0,119,186,205} |  0
  3 | {0,118,187,205} |  0
  3 | {0,115,190,205} |  0
  3 | {0,125,179,206} |  0
  3 | {0,123,181,206} |  0
(20 行记录)

〇〇

import numpy as np
from communities.algorithms import bron_kerbosch

data=[[0,5]
,[1,4]
,[0,3]
,[0,6]
,[2,4]
,[3,4]
,[5,6]
,[2,7]
,[2,5]
,[1,6]
,[0,7]
,[3,5]
,[3,6]
,[1,7]
,[1,2]
,[4,7]]


adj_matrix = np.zeros((8, 8), dtype='int8')

for i in range(8):
  for j in range(8):
    if [i,j] in data: adj_matrix[ i][j]=1

print(adj_matrix)
[[0 0 0 1 0 1 1 1]
[0 0 1 0 1 0 1 1]
[0 0 0 0 1 1 0 1]
[0 0 0 0 1 1 1 0]
[0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]]

communities = bron_kerbosch(adj_matrix, pivot=True)
print(communities)
[{0, 3, 5, 6}, {0, 7}, {1, 2, 4, 7}, {1, 6}, {2, 4, 7}, {2, 5}, {4, 7}]

〇〇

把算邻居的语句也加入了
https://finance.sina.com.cn/tech ... ftssap8050893.shtml

def f_bk(a,m):
  n=1<<a
  adj_matrix = np.zeros((n, n), dtype='int8')
  for i in range(n):
    for j in range(n):
      cnt1=0
      d=i^j
      for k in range(a):
        if d&(1<<k)!=0:cnt1+=1
      if cnt1>=m: adj_matrix[ i][j]=1
  print(adj_matrix)
  communities = bron_kerbosch(adj_matrix)
  longest=0
  result=[]
  for i in communities:
    if len(i)>longest:
      longest=len(i)
      result=i
  return (longest,result)
>>> f_bk(3,2)
[[0 0 0 1 0 1 1 1]
[0 0 1 0 1 0 1 1]
[0 1 0 0 1 1 0 1]
[1 0 0 0 1 1 1 0]
[0 1 1 1 0 0 0 1]
[1 0 1 1 0 0 1 0]
[1 1 0 1 0 1 0 0]
[1 1 1 0 1 0 0 0]]
(4, {0, 3, 5, 6})
>>> f_bk(7,4)
[[0 0 0 ... 1 1 1]
[0 0 0 ... 1 1 1]
[0 0 0 ... 1 1 1]
...
[1 1 1 ... 0 0 0]
[1 1 1 ... 0 0 0]
[1 1 1 ... 0 0 0]]
(8, {0, 51, 85, 102, 105, 90, 60, 15})

〇〇

9，5实在太慢，其他几个也都对得上SQL的结果
>>> f_bk(8,5)
[[0 0 0 ... 1 1 1]
[0 0 0 ... 1 1 1]
[0 0 0 ... 1 1 1]
...
[1 1 1 ... 0 0 0]
[1 1 1 ... 0 0 0]
[1 1 1 ... 0 0 0]]
(4, {0, 227, 252, 31})
>>> f_bk(9,7)
[[0 0 0 ... 1 1 1]
[0 0 0 ... 1 1 1]
[0 0 0 ... 1 1 1]
...
[1 1 1 ... 0 0 0]
[1 1 1 ... 0 0 0]
[1 1 1 ... 0 0 0]]
(2, {0, 382})
>>> f_bk(9,6)
[[0 0 0 ... 1 1 1]
[0 0 0 ... 1 1 1]
[0 0 0 ... 1 1 1]
...
[1 1 1 ... 0 0 0]
[1 1 1 ... 0 0 0]
[1 1 1 ... 0 0 0]]
(4, {0, 504, 455, 63})