Zamówienia sumy podzbiorów

22

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.

isaacg
źródło
Dawno się nie widzieliśmy isaaca!
orlp
Gdy są dwoma podzbiorami, czy istnieje scenariusz, w którym można wywnioskować z dowolnej informacji innej niż lub , nie licząc początkowe ? P Q P Q p P , q Q ( p q ) a b c P,QPQPQpP,qQ(pq)abc
orlp
Odpowiedź: tak. nie jest wystarczająco ciasny, przykład: . { a , c } , { b , c }pP,qQ(pq){a,c},{b,c}
orlp
@orlp Dobrze być z powrotem! Myślę, że będę robił głównie pytania w dającej się przewidzieć przyszłości
isaacg,
Czy możesz również dodać 14 możliwych kolejności dla n = 4?
Peter Taylor

Odpowiedzi:

11

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ń na , a + nb , b + nc , c + nd . 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.

Anders Kaseorg
źródło
390 bajtów .
Pan Xcoder,
@ Mr.Xcoder Pewnie, dziękuję!
Anders Kaseorg,
@Lynn Thanks! Zrobiłem trochę kompromis, ponieważ nie chcę zbytnio go spowalniać - n
wynosi
1
@AlonAmit Wygląda na to, że zajęło około 55 minut dla n = 6. SciPy nie jest najlepszy w LP; Mam wersję używającą GLPK zamiast SciPy, która robi n = 6 w 70 sekund. Mówiąc dokładniej, wersja SciPy ma złą odpowiedź (a GLPK właściwą)… więc… to… ciekawe… Zastanawiam się, czy to SciPy # 6690 ?
Anders Kaseorg,
1
@AlonAmit # 6690, prawda? Ale dodałem options={'tol':.1}, co wydaje się rozwiązywać problem.
Anders Kaseorg,
0

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
}
przepisane
źródło
Nie mogę przetestować go powyżej 3 na moim komputerze, ale ten (139 bajtów) powinien być funkcjonalnie identyczny z twoim rozwiązaniem. Zmiany: ...x-1=> ..x-2, .select{...}.count=> .count{...}, |(x,y)|=> |x,y|, x&~y==0||y&~x!=0=> x&~y<1||y&~x>0ponieważ a&~bnie mogę być negatywny, jeśli się nie mylę
Asone Tuhid
1
Spójrz na n=5właśnie dodany kontrprzykład. Jeśli się nie mylę, twój kod by to zaakceptował.
isaacg,
2
Link TIO pokazujący, że nie działa poprawnie na kontrprzykładzie: Wypróbuj online!
isaacg,
1
Twoja nowsza wersja wydaje się być funkcją rekurencyjną P, więc nie może być anonimowa. Sądzę też, że nadal się nie udaje z powodu opublikowanego przez nas kontrprzykładu.
isaacg
1
Dla szybszego rozwiązania: 280 bajtów Wypróbuj online! . Pamiętaj, że musisz podać nazwę funkcji rekurencyjnej ( P=). Myślę też, że musisz zwrócić liczbę, więc być może będziesz musiał .sizegdzieś tam wpisać.
Asone Tuhid