일련의 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
제출하기 전에 완료 할 수있을 정도로 빠르지 않아야 합니다.
제출은 평소와 같이 프로그램, 기능 등이 될 수 있습니다.
표준 허점 은 항상 금지되어 있습니다. 이것은 코드 골프이므로 바이트 단위의 최단 답변이 이깁니다. 의견에 명확한 질문을 자유롭게하십시오.
답변
파이썬 3 + SciPy, 396 390 385 351 336 355 바이트
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]))
이제 약 5 초 동안 n = 5 동안 실행됩니다 . 는 if~-(v in u):
-18 바이트하지만 엄청난 성능 저하에 대한 제거 할 수 있습니다.
계산하는 대신 추상 순서를 모두 인쇄 if c:print(s.x.round(),y)
하려면 for
루프 앞에 추가 하십시오 . (서브 세트는 각 비트가 하나의 요소의 존재 또는 부재에 해당하는 이진 정수로 표시됩니다 : { a , c , d } ↔ 1101₂ = 13)
작동 원리
f
주어진 제약 목록을 만족시키는 추상 순서를 재귀 적으로 계산합니다. 제약 조건 n ≤ a , a + n ≤ b , b + n ≤ c , c + n ≤ d로 시작 합니다. 선형 프로그래밍을 사용하여 제약 조건에 대한 솔루션을 찾습니다 (또는없는 경우 0을 반환).이 경우 a = 4, b = 8, c = 12, d = 16 을 얻 습니다. 솔루션을 정수로 반올림합니다. 그런 다음 모든 하위 집합을 합계로 정렬하여 참조 순서를 계산합니다.
{ 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 }
라운딩은 제약 조건 이상으로 위반되는 원인이없는 N 우리의 마진을 추가 한 이유 / 2, N을 .
파이썬 sorted
은 안정적 이기 때문에 , 부분 집합들 사이의 관계는 우리가 그것들을 생성 한 것과 같은 역 사전 순서로 끊어집니다. 따라서 { a , b , c , d }를 { a · 2 ^ n + 2 ^ 0, b · 2 ^ n + 2 ^ 1, c · 2 ^ n + 2 ^ 2, d · 2 ^로 바꾸는 것을 상상할 수 있습니다. n + 2 ^ 3}은 관계없이 동일한 순서를 갖습니다.
계획은 다른 모든 추상 순서를 참조 순서와 처음 동의하지 않은 위치를 기준으로 사례 분석별로 분류하는 것입니다 .
{ a }> { b }
또는 { a } <{ b }> { c }
또는 { a } <{ b } <{ c }> { a , b }
또는 { a } <{ b } < { c } <{ a , b }> { d },
⋮
각각의 경우에, 우리는이 새로운 제약 조건을 여백 n 으로 추가하고 새로운 제약 조건을 재귀 적으로 호출 f
합니다.
노트
잠시 동안 제약 조건에서 마진 1을 가진 선형 프로그램 솔루션은 항상 정수가 될 것이라고 추측했습니다 (그러나 가정하지는 않았습니다). n = 7 인 반례 는 {2.5, 30, 62.5, 73.5, 82, 87.5, 99.5}입니다.
Python, 606 바이트 (빠른 외부 라이브러리 없음)
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 번째의 분기 = 5 및 N = 6에서 230 초 (75 초 PyPy).
부동 소수점 반올림 문제를 피하기 위해 동종 좌표로 정수 수학을 사용하는 수동 코딩 선형 프로그래밍 솔버가 포함되어 있습니다.
답변
루비, 308 바이트, 훨씬 빠름
~ 150ms에서 사례 4를 실행합니다. 특수 라이브러리가 사용되지 않습니다.
->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)}}}
예를 들어 사소한 경우의 결과를 재귀 적으로 산재합니다.
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}]
추가 요소가 추가 된 해당 서브 세트를 사용하면 동일한 상대 순서를 유지해야합니다. 또한 모든 이전 싱글 톤 이후에 새로운 싱글 톤이 추가되도록합니다.
적합성을 검사하는 부분은 이전과 동일하지만 테스트 할 조합이 훨씬 적습니다.
확장 및 댓글 버전 :
->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
}
루비, 151 바이트, 상당히 느림
(세 요소의 경우 << 1s, 4의 경우 여전히 실행 중)
->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
}