Teilmenge Summenbestellungen

22

Eine Reihe npositiver Zahlen enthält 2^nTeilmengen. Wir nennen eine Menge "nice", wenn keine dieser Teilmengen dieselbe Summe hat. {2, 4, 5, 8}ist so ein schönes Set. Da keine der Teilmengen dieselbe Summe hat, können wir die Teilmengen nach Summe sortieren:

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

Wenn wir die Zahlen in aufsteigender Reihenfolge [2, 4, 5, 8]mit den Symbolen beschriften [a, b, c, d], erhalten wir die folgende abstrakte Reihenfolge:

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

Ein anderer netter Satz positiver Zahlen kann dieselbe oder eine andere abstrakte Reihenfolge haben. Ist zum Beispiel [3, 4, 8, 10]ein schönes Set mit einer anderen abstrakten Reihenfolge:

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

In dieser Herausforderung müssen Sie die Anzahl der eindeutigen abstrakten Anordnungen von netten Sätzen npositiver Zahlen zählen. Diese Sequenz ist OEIS A009997 , und die bekannten Werte, beginnend mit n=1, sind:

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

Zum Beispiel sind n=3die folgenden zwei möglichen abstrakten Ordnungen:

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

Im n=4Folgenden sind die 14 möglichen abstrakten Ordnungen sowie ein Beispielsatz mit dieser Ordnung aufgeführt:

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

Folgendes ist keine gültige abstrakte Reihenfolge:

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

Diese Bestellung impliziert, dass:

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

Die Summe dieser Ungleichungen ergibt:

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

Das ist ein Widerspruch. Ihr Code darf diese Bestellung nicht mitzählen. Solche Gegenbeispiele tauchen zunächst bei auf n=5. Beispiel aus diesem Artikel , Beispiel 2.5 auf Seite 3.

Diese Reihenfolge ist ungültig , trotz der Tatsache , dass A < Bdas bedeutet A U C < B U C, für jeden Cdisjunkt Aund B.


Ihr Code oder Programm muss schnell genug sein, damit Sie es bis zur Fertigstellung ausführen können, n=4bevor Sie es senden.

Einsendungen können wie gewohnt Programme, Funktionen usw. sein.

Standardlücken sind wie immer verboten. Dies ist Codegolf, daher gewinnt die kürzeste Antwort in Bytes. Fühlen Sie sich frei, in den Kommentaren klärende Fragen zu stellen.

isaacg
quelle
Lange nicht gesehen, Isaac!
Orlp
P,QPQPQpP,qQ(pq)abc
pP,qQ(pq){a,c},{b,c}
@orlp Schön, wieder dabei zu sein! Ich denke, ich werde auf absehbare Zeit hauptsächlich Fragen stellen
isaacg
Könnten Sie auch die 14 möglichen Ordnungen für n = 4 hinzufügen?
Peter Taylor

Antworten:

11

Python 3 + SciPy, 396 390 385 351 336 355 Bytes

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

Probieren Sie es online!

Dies dauert nun n = 5 in ca. 5 Sekunden. Das if~-(v in u):kann für −18 Bytes entfernt werden, ist aber eine enorme Leistungseinbuße.

Wenn Sie alle abstrakten Ordnungen drucken möchten, anstatt sie nur zu zählen, fügen Sie sie if c:print(s.x.round(),y)vor der forSchleife hinzu. (Teilmengen werden durch binäre Ganzzahlen dargestellt, wobei jedes Bit dem Vorhandensein oder Fehlen eines Elements entspricht: { a , c , d } ↔ 1101₂ = 13.)

Wie es funktioniert

fzählt rekursiv die abstrakten Ordnungen, die eine gegebene Liste von Beschränkungen erfüllen. Wir beginnen mit den Bedingungen na , a + nb , b + nc , c + nd . Mit linearer Programmierung finden wir eine Lösung für die Einschränkungen (oder geben 0 zurück, wenn es keine gibt) - in diesem Fall erhalten wir a = 4, b = 8, c = 12, d = 16. Wir runden die Lösung auf ganze Zahlen Berechnen Sie dann eine Referenzreihenfolge, indem Sie alle Teilmengen nach ihrer Summe sortieren:

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

Die Rundung kann nicht dazu führen, dass Einschränkungen um mehr als n / 2 verletzt werden. Aus diesem Grund haben wir einen Rand von n hinzugefügt .

Da Python's sortedstabil ist, werden alle Bindungen zwischen den Teilmengen in derselben umgekehrten lexikografischen Reihenfolge unterbrochen, in der wir sie generiert haben. Wir könnten uns also vorstellen, { a , b , c , d } durch { a · 2 ^ n + 2 ^ 0, b · 2 ^ n + 2 ^ 1, c · 2 ^ n + 2 ^ 2, d · 2 ^ zu ersetzen n + 2 ^ 3}, um die gleiche Bestellung ohne Krawatten zu erhalten.

Es ist geplant, alle anderen abstrakten Sortierungen anhand einer Fallanalyse zu kategorisieren, basierend darauf, wo sie zuerst mit der Referenzsortierung nicht übereinstimmen:

Entweder { a }> { b }
oder { a } <{ b }> { c }
oder { a } <{ b } <{ c }> { a , b }
oder { a } <{ b } < { c } <{ a , b }> { d },

In jedem Fall fügen wir diese neuen Bedingungen mit einem Rand von n hinzu und rufen sie rekursiv fmit den neuen hinzugefügten Bedingungen auf.

Anmerkungen

Für eine Weile vermutete ich (aber ging nicht davon aus), dass die linearen Programmlösungen mit Rand 1 für die Einschränkungen immer ganze Zahlen sein werden. Dies stellt sich als falsch heraus: Ein Gegenbeispiel mit n = 7 ist {2,5, 30, 62,5, 73,5, 82, 87,5, 99,5}.

Python, 606 Bytes (schneller, keine externen Bibliotheken)

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

Probieren Sie es online!

Dies dauert n = 5 in einer Viertelsekunde und n = 6 in 230 Sekunden (75 Sekunden in PyPy).

Es enthält einen handcodierten linearen Programmierlöser, der Ganzzahl-Mathematik in homogenen Koordinaten verwendet, um Gleitkomma-Rundungsprobleme zu vermeiden.

Anders Kaseorg
quelle
390 Bytes .
Mr. Xcoder
@ Mr.Xcoder Klar, danke!
Anders Kaseorg
@Lynn Danke! Ich habe ein bisschen Kompromisse gemacht, weil ich es nicht zu sehr verlangsamen möchte - es dauert bereits fast 3 Minuten für n = 5.
Anders Kaseorg
1
@AlonAmit Sieht so aus, als hätte es für n = 6 ungefähr 55 Minuten gedauert. SciPy ist bei LP nicht das Beste. Ich habe eine Version mit GLPK anstelle von SciPy, die in 70 Sekunden n = 6 ist. Genauer gesagt, die SciPy-Version hat die falsche Antwort erhalten (und GLPK die richtige) ... also, das ist ... interessant ... ich frage mich, ob dies SciPy # 6690 ist ?
Anders Kaseorg
1
@AlonAmit # 6690, nicht wahr? Aber ich fügte hinzu options={'tol':.1}, das scheint das Problem zu lösen.
Anders Kaseorg
0

Ruby, 308 Bytes, viel schneller

Läuft der Fall 4 in ~ 150ms. Es wird keine Spezialbibliothek verwendet.

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

Es durchsetzt beispielsweise rekursiv das Ergebnis eines kleinen Falls

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

Mit den entsprechenden Teilmengen, denen ein zusätzliches Element hinzugefügt wurde, muss die relative Reihenfolge beibehalten werden. Außerdem wird sichergestellt, dass der neue Singleton nach allen vorherigen Singletons hinzugefügt wird.

Der Teil, der die Konformität überprüft, ist derselbe wie zuvor, aber die zu testenden Kombinationen sind viel weniger.

Erweiterte und kommentierte Version:

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

Ruby, 151 Bytes, ziemlich langsam

(Der Fall von drei Elementen dauert << 1s, der Fall von vier Elementen läuft noch)

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

Es funktioniert mit der Bitfelddarstellung der Teilmengen, daher muss man möglicherweise die Ausgabe massieren, um die Teilmengen selbst anzuzeigen.

formatiert:

-> 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
}
neu geschrieben
quelle
Ich kann es auf meinem Computer nicht über 3 testen, aber dies (139 Byte) sollte funktional mit Ihrer Lösung identisch sein. Änderungen: ...x-1=> ..x-2, .select{...}.count=> .count{...}, |(x,y)|=> |x,y|, x&~y==0||y&~x!=0=> x&~y<1||y&~x>0da a&~bkann nicht negativ sein, wenn ich mich nicht irre
Asone Tuhid
1
Schauen Sie sich das n=5gerade hinzugefügte Gegenbeispiel an. Wenn ich mich nicht irre, würde Ihr Code dies akzeptieren.
Isaacg
2
TIO-Link, der anzeigt, dass er im Gegenbeispiel nicht richtig funktioniert: Probieren Sie es online aus!
Isaacg
1
Bei Ihrer neueren Version handelt es sich anscheinend um eine rekursive Funktion P, die nicht anonym sein kann. Außerdem denke ich, dass es aufgrund des von mir geposteten Gegenbeispiels immer noch fehlschlägt.
Isaacg
1
Für die schnellere Lösung: 280 Bytes Probieren Sie es online! . Beachten Sie, dass Sie den Namen einer rekursiven Funktion ( P=) angeben müssen . Außerdem denke ich, dass Sie eine Nummer zurückgeben müssen, damit Sie sie möglicherweise .sizeirgendwo einfügen müssen.
Asone Tuhid