일련의 n양수가 2^n하위 집합을. 해당 부분 집합이 동일한 합계를 갖지 않으면 “nice”세트를 호출합니다. {2, 4, 5, 8}그런 멋진 세트 중 하나입니다. 부분 집합 중 동일한 합계를 가진 하위 집합이 없기 때문에 부분 집합을 합계로 정렬 할 수 있습니다.

[{}, {2}, {4}, {5}, {2, 4}, {2, 5}, {8}, {4, 5}, {2, 8}, {2, 4, 5}, {4, 8}, {5, 8}, {2, 4, 8}, {2, 5, 8}, {4, 5, 8}, {2, 4, 5, 8}]

숫자 순서대로 [2, 4, 5, 8]기호 [a, b, c, d]에 숫자 를 붙이면 다음과 같은 추상 순서가 나타납니다.

[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}]

또 다른 좋은 양수 집합은 동일한 추상 순서 또는 다른 순서를 가질 수 있습니다. 예를 들어 [3, 4, 8, 10]추상 순서가 다른 멋진 세트입니다.

[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}]

이 도전에서, 당신은 좋은 n양수 세트의 별개의 추상 순서의 수를 세어야합니다 . 이 순서는 OEIS A009997 이며로 시작하는 알려진 값 n=1은 다음과 같습니다.

1, 1, 2, 14, 516, 124187, 214580603

예를 들어, n=3다음은 가능한 두 가지 추상 순서입니다.

[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}]

의 경우 n=4, 다음은 14 가지 가능한 추상 순서와 그 순서를 가진 멋진 세트의 예입니다.

[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}, {d}, {a, d}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 4, 2, 1]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {d}, {a, b, c}, {a, d}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 6, 3, 2]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 7, 4, 2]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {d}, {a, d}, {b, c}, {a, b, c}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 4, 1]
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 8, 4, 3]
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 7, 4, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}, {d}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 4, 3, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {d}, {a, b, c}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 4, 3, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 5, 4, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {a, d}, {b, c}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 7, 6, 2]
[{}, {a}, {b}, {c}, {a, b}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 4, 3]
[{}, {a}, {b}, {c}, {a, b}, {d}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 8, 6, 3]
[{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {b, c}, {a, d}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 5, 4]
[{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [7, 6, 5, 3]

다음은 유효한 추상 순서가 아닙니다.

{}, {a}, {b}, {c}, {d}, {a,b}, {e}, {a,c}, {b,c}, {a,d}, {a,e}, {b,d}, {b,e}, {c,d}, {a,b,c}, {a,b,d}, {c,e}, {d,e}, {a,b,e}, {a,c,d}, {a,c,e}, {b,c,d}, {b,c,e}, {a,d,e}, {b,d,e}, {a,b,c,d}, {c,d,e}, {a,b,c,e}, {a,b,d,e}, {a,c,d,e}, {b,c,d,e}, {a,b,c,d,e}

이 순서는 다음을 의미합니다.

d < a + b
b + c < a + d
a + e < b + d
a + b + d < c + e

이 불평등을 합하면 다음과 같습니다.

2a + 2b + c + 2d + e < 2a + 2b + c + 2d + e

모순입니다. 코드는이 순서를 계산해서는 안됩니다. 이러한 반례는 먼저에 나타납니다 n=5. 실시 예에서 이 종이 , 3 페이지 예 2.5.

이 순서는 사실에도 불구하고 잘못된 A < B것을 의미한다 A U C < B U C어떤을 위해, C에서 해체 A하고 B.

코드 나 프로그램은 n=4제출하기 전에 완료 할 수있을 정도로 빠르지 않아야 합니다.

제출은 평소와 같이 프로그램, 기능 등이 될 수 있습니다.

표준 허점 은 항상 금지되어 있습니다. 이것은 코드 골프이므로 바이트 단위의 최단 답변이 이깁니다. 의견에 명확한 질문을 자유롭게하십시오.

답변

from scipy.optimize import*
n=int(input())
r=range(n)
def f(u):
 s=linprog(r,u,[-n]*len(u),options={'tol':.1});c=s.success;y=sorted(range(c<<n),key=lambda a:s.x.round()@[a>>i&1for i in r])
 for a,b in zip(y,y[1:]):
  v=[(a>>i&1)-(b>>i&1)for i in r]
  if~-(v in u):c+=f(u+[[-z for z in v]]);u+=v,
 return+c
print(f([[(i==j-1)-(i==j)for i in r]for j in r]))

n=int(input())
r=range(n)
e=enumerate
def l(u,x):
 for i,v in e(u):
  for j,a in e(v):
   if a<0:break
  else:return[0]*len(x)
  if sum(b*x[k]for k,b in e(v))>0:
   x=l([[b*w[j]-a*w[k]for k,b in e(v)if k!=j]for w in u[:i]],x[:j]+x[j+1:]);x.insert(j,0)
   for k,b in e(v):
    if k!=j:x[j]+=b*x[k];x[k]*=-a
 return x
def f(u,x):
 x=l(u,x);c=any(x);y=sorted(range(c<<n),key=lambda a:sum(x[i]*(a>>i&1)for i in r))
 for a,b in zip(y,y[1:]):
  v=[(a>>i&1)-(b>>i&1)for i in r]+[1]
  if~-(v in u):c+=f(u+[[-z for z in v[:-1]]+[1]],x);u+=v,
 return+c
print(f([[(i==j-1)-(i==j)for i in r]+[1]for j in r],[1]*(n+1)))

->n{t=2**(n-1)
n==0 ?[[0]]:P[n-1].map{|a|b=a.map{|i|i+t}
[*0..t].repeated_combination(t).select{|m|m[0]>=a.index(n-1)}.map{|m|c,d=a.dup,b.dup;m.reverse.map{|i|c.insert(i,d.pop)};c}}.flatten(1).select{|p|p.combination(2).all?{|(x,y)|x&~y==0||y&~x!=0&&n.times.all?{|i|x!=y<<i+1}&&p.index(x&~y)<p.index(y&~x)}}}

->n{
    t=2**(n-1)
    if n==0
        [[0]]
    else
        # for each one of the previous nice orderings
        P[n-1].map { |a|
            # create the missing sets, keep order
            b = a.map{|i|i+t}
            # intersperse the two sets
            [*0..t].repeated_combination(t) # select t insertion points
                .select do |m|
                    # ensure the new singleton is after the old ones
                    m[0] >= a.index(n-1)
                end
                .map do |m|
                    # do the interspersion
                    c,d=a.dup,b.dup
                    m.reverse.map{|i|c.insert(i, d.pop)}
                    c
                end
        }.flatten(1).select{ |p|
            # check if the final ordering is still nice
            p.combination(2).all? { |(x,y)|
                (x&~y==0) ||
                (y&~x!=0) &&
                n.times.all?{|i|x!=y<<i+1} &&
                (p.index(x&~y)<p.index(y&~x))
            }
        }
    end
}

->n{[*1...2**n-1].permutation.select{|p|p.combination(2).all?{|(x,y)|x&~y==0||y&~x!=0&&n.times.all?{|i|x!=y<<i+1}&&p.index(x&~y)<p.index(y&~x)}}.count}

-> n {
  [*1...2**n-1]. # prepare permutations of non-empty and non-full sets
    permutation.
    select { |p|
      p.combination(2). # check all ordered pairs
        all? { |(x, y)|
          # first is subset of second
          x &~ y == 0 ||
          # second is not subset of first
          y &~ x != 0 &&
          # first is not a right shift of second
          # (this normalizes the ordering on atoms)
          n.times.all? { |i| x != y << i+1 } &&
          # after taking out common elements, ordering agrees
          p.index(x &~ y) < p.index(y &~ x)
        }
    }.
    count
}