Zbiór nliczb dodatnich ma 2^npodzbiory. Nazwiemy zestaw „ładnym”, jeśli żaden z tych podzbiorów nie ma takiej samej sumy. {2, 4, 5, 8}to jeden taki fajny zestaw. Ponieważ żaden z podzbiorów nie ma takiej samej sumy, możemy sortować podzbiory według sumy:

[{}, {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}]

Jeśli oznaczymy liczby [2, 4, 5, 8]symbolami [a, b, c, d]w porządku rosnącym, otrzymamy następującą abstrakcyjną kolejność:

[{}, {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}]

Kolejny ładny zestaw liczb dodatnich może mieć tę samą abstrakcyjną kolejność lub inną. Na przykład [3, 4, 8, 10]jest ładny zestaw z innym abstrakcyjnym uporządkowaniem:

[{}, {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}]

W tym wyzwaniu musisz policzyć liczbę odrębnych abstrakcyjnych porządków ładnych zbiorów nliczb dodatnich. Sekwencja ta to OEIS A009997 , a znane wartości, począwszy od n=1, są następujące:

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

Na przykład, dla n=3następujących są dwa możliwe abstrakcyjne porządki:

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

Dla n=4dodaje to 14 możliwych abstrakcyjne uporządkowania, plus przykładem ładny zestaw z tym zamawiającego:

[{}, {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]

Poniższe informacje nie są prawidłowym porządkiem abstrakcyjnym:

{}, {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}

To zamówienie oznacza, że:

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

Podsumowanie tych nierówności daje:

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

co jest sprzecznością. Twój kod nie może liczyć tego zamówienia. Takie kontrprzykłady pojawiają się po raz pierwszy w n=5. Przykład z tego artykułu , przykład 2.5 na stronie 3.

To zamówienie jest nieważne, mimo że A < Bimplikuje to A U C < B U C, że w przypadku Crozłączenia z Ai B.

Twój kod lub program musi być wystarczająco szybki, abyś mógł go uruchomić do końca n=4przed przesłaniem.

Zgłoszenia mogą być jak zwykle programami, funkcjami itp.

Standardowe luki są jak zawsze zabronione. To jest kod golfowy, więc wygrywa najkrótsza odpowiedź w bajtach. Zapraszam do zadawania wyjaśnień w komentarzach.

Python 3 + SciPy, 396 390 385 351 336 355 bajtów

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]))

Wypróbuj online!

Działa to teraz przez n = 5 za około 5 sekund. if~-(v in u):Mogą być usunięte do -18 bajtów ale ogromne kary wydajności.

Jeśli chcesz wydrukować wszystkie abstrakcyjne uporządkowania w takiej postaci, w jakiej są znalezione, zamiast je tylko zliczać, dodaj if c:print(s.x.round(),y)przed forpętlą. (Podzbiory są reprezentowane przez binarne liczby całkowite, przy czym każdy bit odpowiada obecności lub nieobecności jednego elementu: { a , c , d } ↔ 1101₂ = 13.)

Jak to działa

frekurencyjnie zlicza uporządkowania abstrakcyjne spełniające daną listę ograniczeń. Zaczynamy od ograniczeń n ≤ a , a + n ≤ b , b + n ≤ c , c + n ≤ d . Stosując programowanie liniowe, znajdujemy rozwiązanie dla ograniczeń (lub zwracamy 0, jeśli nie ma takiego) - w tym przypadku otrzymujemy a = 4, b = 8, c = 12, d = 16. Zaokrąglamy rozwiązanie do liczb całkowitych , a następnie oblicz porządkowanie referencji, sortując wszystkie jego podzbiory według ich sumy:

{ 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 }

Zaokrąglenie nie może powodować naruszenia żadnych ograniczeń o więcej niż n / 2, dlatego dodaliśmy margines n .

Ponieważ Python sortedjest stabilny, wszelkie powiązania między podzbiorami są zrywane w tej samej kolejności odwrotnej leksykografii, w której je wygenerowaliśmy. Więc możemy sobie wyobrazić zastąpienie { a , b , c , d } przez { a · 2 ^ n + 2 ^ 0, b · 2 ^ n + 2 ^ 1, c · 2 ^ n + 2 ^ 2, d · 2 ^ n + 2 ^ 3}, aby uzyskać to samo zamówienie bez żadnych powiązań.

Planuje się kategoryzowanie wszystkich innych abstrakcyjnych porządków według analizy przypadków w oparciu o to, gdzie najpierw nie zgadzają się z porządkiem referencyjnym:

Albo { a }> { b },
albo { a } <{ b }> { c },
lub { a } <{ b } <{ c }> { a , b }
lub { a } <{ b } < { c } <{ a , b }> { d },
⋮

W każdym przypadku dodajemy nowe ograniczenia z marginesem n i rekurencyjnie wywołujemy je fz dodanymi nowymi ograniczeniami.

Notatki

Przez pewien czas przypuszczałem (ale nie zakładałem), że rozwiązania programu liniowego z marginesem 1 na ograniczeniach zawsze będą liczbami całkowitymi. To okazuje się fałszywe: kontrprzykład n = 7 to {2,5, 30, 62,5, 73,5, 82, 87,5, 99,5}.

Python, 606 bajtów (szybszy, brak bibliotek zewnętrznych)

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)))

Wypróbuj online!

Działa to przez n = 5 za kwadrans, a n = 6 za 230 sekund (75 sekund w PyPy).

Zawiera ręcznie zakodowane narzędzie do programowania liniowego z wykorzystaniem matematyki liczb całkowitych w jednorodnych współrzędnych, aby uniknąć problemów z zaokrąglaniem zmiennoprzecinkowym.

Rubinowy, 308 bajtów, znacznie szybciej

Uruchamia obudowę 4 w ~ 150ms. Nie jest używana specjalistyczna biblioteka.

->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)}}}

Na przykład rekurencyjnie przeplata wynik drobnego przypadku

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

z odpowiednimi podzbiorami z dodanym dodatkowym elementem - muszą zachować tę samą względną kolejność. Zapewnia również dodanie nowego singletonu po wszystkich poprzednich singletonach.

Część sprawdzająca zgodność jest taka sama jak poprzednio, ale nie kombinacje do testowania są znacznie mniejsze.

Wersja rozszerzona i komentowana:

->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
}

Rubinowy, 151 bajtów, dość wolny

(przypadek trzech elementów zajmuje << 1s, przypadek czterech nadal trwa)

->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}

Działa na reprezentacji pól bitowych podzbiorów, więc w razie potrzeby konieczne może być masowanie danych wyjściowych, aby wyświetlić same podzbiory.

sformatowany:

-> 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
}