Anzahl der eindeutigen Ausgaben durch Ersetzen von Variablen

9

Bei einer Reihe solcher Formeln:

bacb
bcab
cbba
abbc

Geben Sie einen Algorithmus an, der die Anzahl der eindeutigen Ergebnisse ermittelt, die Sie erhalten können, wenn jede Variable in jeder Formel durch "0" oder "1" ersetzt wird.

Es gibt (k!)^2Formeln mit 2k-1Variablen und k^2Begriffen. Drücken Sie Ihre Asymptotik in Bezug auf aus k.

Der schnellste Algorithmus gewinnt. Im Falle eines Unentschieden gewinnt die Lösung mit geringerer asymptotischer Speichernutzung. Wenn das immer noch ein Unentschieden ist, gewinnt der erste Beitrag.

Für das obige Beispiel können die folgenden Ergebnisse durch Ersetzen der Variablen erhalten werden:

1110, 0110, 1001, 0100, 1000, 0000, 0010, 1101, 1111, 0001, 1011, 0111

Die richtige Antwort lautet also 12. 1010Kann unter anderem nicht mit den oben genannten Formeln gemacht werden.

Ich habe drei weitere Testfälle mit entsprechenden Lösungen von 230 , 12076 und 1446672 erstellt .

combinatorics fastest-algorithm orlp
quelle
Klarstellung: Was ist k in der Frage? Ist es nur eine abstrakte Konstante?
isaacg
@isaacg Ja. Dies soll beispielsweise Verbindungen zwischen Lösungen verhindern, die für weniger, aber größere Formeln schneller sind.
Orlp
Also jeden Buchstaben a, b... ist eine Variable ? Und wir haben immer nur eine ungerade Anzahl von Variablen? Ist es nicht wichtig, wie lang die Folge von Variablen ist und wie viele Formeln Sie erhalten?
Fehler
@flawr Die genaue Beziehung zwischen der Anzahl der Variablen, der Anzahl der Begriffe und der Anzahl der Formeln ist in der Frage angegeben.
Orlp
Bedeutet 'kann sein', dass Sie bis zu $ (k!) ^ 2 $ Formeln erhalten können, oder gibt es genau $ (k!) ^ 2 $ Formeln? Haben Sie außerdem eine Anwendung für einen Algorithmus mit diesen Spezifikationen? Ich frage nur, weil die Spezifikationen ziemlich willkürlich zu sein scheinen.
Fehler

Antworten:

2

Mathematica, O (k ^ 2 (k!) ^ 2) Zeit

Length[Union@@(Fold[Flatten[{StringReplace[#,#2->"0"],StringReplace[#,#2->"1"]}]&,#,Union[Characters[#]]]&/@#)]&

Hoffentlich habe ich die Zeitkomplexität richtig berechnet. Eingabe ist eine Liste von Formeln wie z {"bacb","bcab","cbba","abbc"}. Läuft für jeden Testfall auf meinem Computer in weniger als 30 Sekunden, aber wen interessieren die absoluten Zeiten?

Erläuterung:

  • Zunächst einmal &macht das am Ende es zu einer reinen Funktion, #wobei auf das erste Argument Bezug genommen wird #2, das zweite Argument ist usw.
  • Length[*..*] nimmt die Länge der darin enthaltenen Liste.
  • Union@@(*..*)Nimmt die enthaltene Liste und liefert sie als Argumente für Union, wodurch eine Liste der eindeutigen Elemente in einem ihrer Argumente zurückgegeben wird.
  • *..*&/@#nimmt eine reine Funktion und ordnet sie der Liste der Formeln zu, so dass {a,b,c}wird {f[a],f[b],f[c]}. Beachten Sie, dass in verschachtelten reinen Funktionen #nauf die innersten Argumente verwiesen wird.
  • Fold[*..*&,#,*..*]Nimmt eine Akkumulatorfunktion, einen Startwert und eine Liste und kehrt zurück f[f[...[f[starting value,l_1],l_2],...],l_n].
  • Union[Characters[#]] Nimmt alle Zeichen in der aktuellen Formel und erhält alle eindeutigen Elemente, wodurch wir die Variablen erhalten.
  • Flatten[*..*]glättet sein Argument, so dass das {{{a},b},{{c,{d}}}}wird {a,b,c,d}.
  • {*..*,*..*}ist einfach eine Möglichkeit, die beiden Ergebnisse mit den oben genannten zu kombinieren Flatten.
  • StringReplace[#,#2->"0/1"]Nimmt das vorherige Ergebnis und gibt es zurück, wobei die aktuelle Variable durch entweder 0oder ersetzt wird 1.
LegionMammal978
quelle
Warum verwenden Sie kin Ihrer Zeit als Variable? Trotzdem faktorielle Zeit! Puh!
theonlygusti
Die Operation sagte: "Drücken Sie Ihre Asymptotik in Bezug auf aus k." Außerdem musste ich GeneralUtilities`Benchmarkfür jede verwendete Methode eine machen.
LegionMammal978
Möchten Sie eine einfache englische Beschreibung Ihres Algorithmus hinzufügen? Ich bin mit Mathematica nicht vertraut, daher kann ich Ihre Lösung nicht überprüfen.
Orlp