Wieviele verschiedene Zahlen in Binärzahlen?

Wissenschaft Mathematik
#1

Dies ist das eigenliche Problem, das ‚mehrfache Elemente aus Mengen filtern‘ zugrundelag. Ich denke, ich muss hier das eigentliche Problem erklären, damit klar wird, was ich wissen möchte.

PROBLEM:

ich habe z.B. 3 Binärzahlen, wobei NICHT ALLE ZIFFERN fest gegeben sind (jede Ziffer ist entweder 0 oder 1 oder ? (? für ‚wahlfrei 0 oder 1‘)).

Beispiel:

A=100?0?101?0
B=?1?00?1000?
C=100??00?0??

Alle Binärzahlen haben die selbe Länge, in der Praxis 10000. Davon ist ca. die Hälfte der Länge wahlfrei, d.h. ?.

Frage: WIEVIELE (NICHT welche!!!) VERSCHIEDENE Zahlen werden durch diesen 3 Binärzahlen beschrieben???

Leichtes Beispiel:

A=00?
B=?00

Wenn man alle so codierten Binärzahlen hinschreibt, bekommt man:
A=000,001
B=000,100

Man sieht, dass DREI UNTERSCHIEDLICHE Zahlen beschrieben werden, nämlich 000,001,100. Die 000 kommt doppelt vor, wobei das nicht offensichtlich ist.
Aber doppelte Zahlen in den Binärzahlen sollen nur EIN MAL gezählt werden.

Anmerkung:
Man kann leicht, feststellen, WIEVIELE (und ich denke auch welche) Zahlen in ZWEI Binärzahlen gleichzeitig vorkommen, dabei muss man die Zahlen (Zahlen mit Wahloption ‚?‘) ‚überlagern‘. Das entspricht im etwa der Schnittmenge.

Beispiel:
A=00?
B=?00

Das Überlagern funktioniert so (Ziffer Zahl 1,entspr. Ziffer Zahl 2):
(0,?)=>(0,0), (1,?)=>(1,1), (?,0)=>(0,0), (?,1)=>(1,1), (?,?)=>(?,?)

Man ersetzt also beim ‚Überlagern‘ (so etwas wie die Schnittmenge) alle ‚?‘ durch die entsprechende Ziffer der anderen Zahl.

A=00?
B=?00

überlagern=>000

Also ist 000 die Zahl, die in beiden Binärzahlen vorkommt, was auch stimmt (s.o.)

Noch ein Beispiel für Überlagerung („Schnittmenge“):
A=?1? = 010,011,110,111
B=?10 = 010,110

überlagern=>?10

Also kommt 010,110 in beiden Zahlen vor. Stimmt.

Anmerkung: wenn mindestens 1 Mal das Paar (0,1) oder (1,0) vor dem Überlagern vorkommt, gibt es keine Schnittmenge, d.h. die beiden Binärzahlen beschreiben keine gemeinsamen Zahlen.

Beispiel:
A=?10
B=?0?
haben keine gemeinsamen Zahlen.

WEIß JEMAND, WIE ICH NUN bei gegebenen Binärzahlen (mit Ziffern 0/1/?) feststellen kann, wieviele VERSCHIEDENE Zahlen durch sie codiert werden?

Schwer, aber ich hoffe, dass man mich versteht.

Vielen Dank!!!

#2

Hallo =)

Also, ich versuche nochmal dein Problem zusammen zufassen, damit du merkst, ob ich das verstanden habe.

Also du hast zwei Zahlen A und B

A=001011?100?
B=0010?101?01

Nun willst du wissen, wiviele Zahlen sich dadurch darstellen lassen, wenn A und B übereinstimmen sollen…

Ich unterscheide nun zwischen „entschieden“ e (also 1 oder 0) und „unentschieden“ u (also ?).

So ist jede Zahl darstellbar durch:

A=eeeueu…ueu
B=eeueue…uee

Als erstes muss getestet werden, ob sich durch A und B die selbe Zahl darstellen lässt.

Nun ist a1 die erste Zahl (also ist es 0, 1 oder ?, bzw. e oder u) von A, a2 die zweite Zahl etc. Genauso bei b1…

Also:
A=a1.a2.a3.a4…an
B=b1.b2.b3.b4…bn

Also muss verglichen werden, ob a1=b1, wenn a1 und b1 entschieden sind, muss die eigenliche Zahl (0 oder 1) übereinstimmen, wenn nicht, ist die Ziffer sowieso korrekt. Das muss dann für alle Ziffern überprüft werden.

Nun muss man „zählen“ wieviele Ziffern es gibt, wenn ai und bi u sind - die Anzahl nenne mich mal x.

Wenn x=0, gibt es eine Zahl, die sich darstellen lässt.
Wenn x=1, gibt es zwei Zahlen, die sich darstellen lassen.
… x=2, … 4 [00, 01, 10, 11]
… x=3, … 8 [000,001,010,100,011,101,110,111]
…
…x=n, 2^n mögliche Zahlen

Ich hoffe mal, dass es das ist, was du gesucht hast.

MfG, Christian

#3

Tut mir Leid, ich verstehe dich nicht ganz.

Ich denke, du hast mir gesagt, dass die Anzahl der Zahlen in so einer
„0/1/?“-Binaerzahl gleich 2^(Anzahl der ?) ist.

Hast du das gemeint?

Das stimmt schon, aber das Problem ist, bei vielen, sagen wir mal 4 „0/1/?-Zahlen“ herauszufinden, wie viele VERSCHIEDENE Zahlen sie beschreiben.

Es kann vorkommen, dass von den 4 Binaerzahlen z.B. die 2. und 4. hundert gemeinsame Zahlen haben, die 1. und 4. sieben und die 1. und 2. achtzehn.

Es funktioniert also nicht, 4 * 2^(#?) als Anzahl aller in den 4 (0/1/?)-Binaerzahlen codierten Zahlen anzugeben, das stimmt nicht (ich habe es per Computer ueberprueft). Da die 4 Binaerzahlen gemeinsame Zahlen haben, funktioniert diese einfache Rechnung nicht.

#4

Hallo,

mathematisch kann ich dein Problem leider nicht lösen. Vielleicht gibt es eine Lösung mittels Kombinatorik, aber da kenne ich mit zu wenig aus.

Du kannst es aber relativ simpel programmieren:

Nimm einfach die erste unvollständige Zahl und schreibe jede Möglichkeit dieser Zahl in einen eindeutigen Index (Dictionary oder sowas).

Dann nimmst du die nächste unvollständige Zahl und prüfst für jede Möglichkeit, ob diese schon vorhanden ist. Falls nicht, hängst du sie an.

Wenn du alle unvollständigen Zahlen abgearbeitet hast, musst du nur noch die Elemente in deinem Index zählen.

#5

Das geht leider nicht.

Eine Binaerzahl mit 5000 wahlfreien Stellen hat ca. 2^5000 Zahlen ‚in sich‘.
Um das zu speichern reicht wahrscheinlich aller Speicher der Welt nicht aus, und da durchzulaufen dauert wahrscheinlich 30 Millionen Jahre oder so.

Trotzdem danke fuer die Antwort!

#6

Stimmt, das hatte ich nicht bedacht.

Cooles Problem übrigens. Werde mal weiter nachdenken und bin auf die Lösung gespannt…

#7

A=100?0?101?0

B=?1?00?1000?

C=100??00?0??

Hallo Rainer,

also durch A und durch B kann ja schonmal nicht dieselbe Zahl dargestellt werden, weil das zweite Bit nicht übereinstimmt. Aus dem gleichen Grund kann durch B und C nicht dieselbe Zahl dargestellt werden. Druch A und C kann auch nicht dieselbe Zahl dargestellt werden, da hier das achte Bit nicht übereinstimmt.
Da A drei ? enthält, ergeben sich 23=8 Möglichkeiten. Für B und C ergeben sich entsprechend 16 Möglichkeiten.
Insegsamt können also 40 verschiedene Zahlen dargestellt werden.

Ob durch zwei Darstellungen dieselbe Zahl dargestellt werden kann, kannst du mit dem „exklusiven oder“ (xor) überprüfen, dafür gibt es in den meisten Programmiersprachen einen Operator. Um zwei Darstellungen A und B zu überprüfen musst du zuerst alle ? in A durch den entsprechenden Wert in B und alle ? in B durch den entsprechenden Wert in A ersetzen. Wenn ein Bit sowohl in A als auch in B ein ? ist, ersetzt du es bei beiden durch 0 (oder 1, wie du willst). Wenn A xor B dann 0 ist, kann durch A und B dieselbe Zahl dargestellt werden, ansonsten nicht.
In deinem Beispiel wird A so zu 1000010100 und B zu 11000010000
A xor B ist dann 0100000100 also ungleich 0, deshalb kann durch A und B (auch mit ?) nie dieselbe Zahl dargestellt werden. Verantwortlich dafür sind das zweite und das achte Bit, also genau die Bits in denen sich A und B auf jeden Fall unterscheiden, unabhängig von den ?.

Das ist zwar keine vollständige Lösung für dein Problem, aber vielleicht hilft es dir trotzdem weiter.

Grüße

hendrik

#8

Hi Hendrik,

dein Vorschlag dürfte genau wie meiner daran scheitern, dass es in einer Zahl u. U. 5000 Stellen mit einem „?“ gibt. Also für eine solche Zahl 2^5000 Möglichkeiten geprüft werden müssten.

Die Lösung kann nur analytisch sein, da alles andere zu viel Zeit und Speicher beanspruchen würde.

Hab allerdings auch noch keine bessere Idee…

#9

Guten Morgen!

Habe über dieses interessante Problem nochmal nachgedacht.

So wie ich das sehe, ist es zu komplex um in einem Schwung gelöst zu werden, darum schlage ich vor, es zu zerlegen.

Folgendes ohne Anspurch auf mathematische Korrektheit, soweit ich das prüfen konnte, passt es aber.

Zunächst bildest Gruppen von Binärzahlen. Zu einer Gruppe gehören alle Zahlen, die an allen Stellen identisch sind, an denen kein „?“ auftaucht.

z. B. so:

1 ? 0 ?
1 0 ? ?
1 ? ? ?

In der ersten Spalte taucht kein „?“ auf, also hierauf die Gruppe bilden.

Bei so einer Gruppe wird die Anzahl der Möglichkeiten nur noch durch die Anzahl der Spalten mit einem „?“ bestimmt. In diesem Fall also 2^3 = 8 unterschiedliche Möglichkeiten.

oder so:
1 1 ? ?
1 1 1 ?
1 1 ? ?

=> 2^2=4 unterschiedliche Möglichkeiten.

Soweit meine bisherigen Überlegungen richtig sind, musst du dann so für jede Gruppe vorgehen und die einzelnen Ergebnisse summieren.

#10

Zunächst bildest Gruppen von Binärzahlen. Zu einer Gruppe
gehören alle Zahlen, die an allen Stellen identisch sind, an
denen kein „?“ auftaucht.

Hi power,

dein Divide & Conquer Ansatz klingt sehr vielversprechend. Ich sehe auf den ersten Blick auch keine Schwachstelle. Selbst vom Aufwand her dürfte das ziemlich zufriedenstellend sein. Und einfach zu implementieren ist es auch noch.
Mal schauen, ob noch jemandem was auffällt.

Gruß

hendrik

#11

Zerlegen in einfaches Problem und dann die Lösungen zusammen setzen - eine sehr gute Idee!

Das ist dann so eine Art Divide-and-Conquer (teile und herrsche) Algorithmus.

Die funktionieren immer einfach und schnell, z.B. beim Sortieren.

Ich werde darüber nachdenken. Danke für den guten Hinweis!

Auch danke an alle anderen, die mir geantwortet haben.

@hendrik: du hast natürlich Recht, die Zahlen haben verschiedene Bits und damit keine gemeinsamen ‚Unterzahlen‘. Das war so nicht gedacht. Das Beispiel von mir war schlecht gewählt. Normalerweise haben viele Binaerzahlen in der Angabe gemeinsame Unterzahlen.

#12

Also ich habe die 2 Vorschläge, die hier gemacht wurden, nicht implementiert, aber ich bin mir durch Ausprobieren einiger Beispiel sehr sicher, dass sie nicht (zuverlässig) funktionieren.

Man teste seinen Algorithmus zum Zählen von Unterzahlen hier:

10-01
–0--
–00-
1----

PROBLEM: die 4 Zeilen oben stellen Binaerzahlen dar. Jedes - (früher ?, war aber schwer zu lesen) heißt „wahlfreie Ziffer“, also entweder 1 oder 0.

FRAGE: wie viele verschiedene (!) „Unterzahlen“ (- durch 0 oder 1 ersetzen) sind durch die 4 Zeilen codiert?

HINWEIS: die 4 Zeilen oben ergeben 42 Zahlen insgesamt. Davon sind 24 Zahlen verschieden, wenn man mehrfach vorkommende Unterzahlen nur ein mal zählt.

Ich habe die 42 und 24 mit dem Computer ermittelt, indem ich alle Unterzahlen durchprobiert habe (- einmal durch 0 und mal durch 1 ersetzt, in allen Kombinationen).

BITTE AN EUCH: wie kommt man auf die 24, OHNE alle Kombinationen durchzuprobieren???

Es sollte einen einfachen Algorithmus (NICHT O(2^n), was beim Durchprobieren der Fall wäre) geben.

Danke für Eure Hilfe!!!

#13

Hi,

eigentlich hat christian im ersten posting die antwort schon gegeben, zumindest aber den richtig Ansatz, würde ich sagen.
Also, gegeben sei:
a_1 = a_11 a_12 a_13 a_14 …
a_2 = a_21 a_22 a_23 a_24 …
…
a_k

und so weiter, wobei aii entweder 0, 1 oder unbekannt (?) ist.
Christian hat jetzt schon ausgeführt, dass a_i bei n_i unbekannten Ziffern 2^(n_i) verschiedene Zahlen gebildet werden können.
D.h. bei k Binärzahlen mit n_k unbekannten Ziffern können maximal 2^(n_1) + 2^(n_2) + … + 2^(n_k) verschiedene Zahlen gebildet werden.

Nun die frage, wie viele es genau sind. Hier macht man sich zunutze, dass genau dann a_i a_j (für i j) ist, wenn nicht alle ? von a_i und a_j an derselben Stelle sind (Eindeutigkeit der Darstellung durch Binäsrzahlen).
Ausnahme: die letzte Stelle ist 0 oder ? und alle ? werden mit 0 ersetzt. (*)
D.h bedeutet aber, dass a_i und a_j entweder nur verschiedene Zahlen erzeugen oder nur dieselben! Also musst du alle Paare a_i und a_j auf Gleichhheit testen. Hier könnte man z.B. zuerst a_i nur mit den a_j vergleichen, die dieselbe Zahl an ? haben um die Anzahl der Vergleiche zu reduzieren. Der Vergleich selber könnte z.B. darüber laufen, dass man alle ? mit 1 ersetzt; kommt dieselbe Zahl heraus sind a_i und a_j ident und man kann eine Zahl von der Liste der k Zahlen streichen.
Und so weiter.
Dadurch erhält man eine Anzahl m A und B erzeugen verschiedene Zahlen
==> m=k=2
==> Z’=2^1+2^1 = 4
step 2: ? mit 0 ersetzen ergibt 000 und 000
==> n=m
==> Z=Z-1=3
(:smile:

#14

ich sehe gerade, dass es nicht passt, weil
??00 und 1?00 durchaus auch gleiche Zahlen erzeugen können …

#15

Ja, aber tröste dich, ich habe auch schon viele Fehler gemacht bei der Suche nach der Lösung dieses Problems.

Man denkt es ist einfach, aber immer passt irgendwas nicht, je nachdem welche Beispielzahlen man wählt.

Fies wird es, wenn man das Ganze auf dem Computer implementiert, da kommt ein Fehler nach dem anderen in den vermeintlichen „Loesungen“ zum Vorschein.

Ich hoffe, dass ich das hier überhaupt hinkriege, aber ich strenge mich an (und Ihr Euch auch :smile: ).

#16

Hallo,

ja, leider hast du recht. Mein Vorschlag war wohl doch zu einfach.

Zwar glaube ich immer noch, dass es sinnvoll ist, Gruppen zu bilden. Aber für dein Beispiel fällt mir keine Lösung ein.

Wie du auf 24 kommst, ist nich so schwer:2^5 = 32 maximal Lösung (mein erster Vorschlag); 24 Kombinationen sind es wirklich, fehlen also 8 (=2^3).

Ich vermute mal, dass es kein Zufall ist, dass die Anzahl der fehlenden Kombinationen eine zweier Potenz ist, aber mir fällt leider nicht ein, wie man auf 2^3 kommt, ohne durchzuprobieren. Ich hab mal versucht, das Ganze als Binärbaum zu modellieren, aber der Rechenaufwand wäre hier auch viel zu hoch…

Sorry, momentan weiß ich da nicht weiter.

#17

Mach dir keinen Kopf, ich komme schon irgendwie drauf. Habe da eine Vermutung, muss sie heute implementieren um sie zu überprüfen…

Trotzdem danke!

#18

Hi,

sag mal Bescheid, wenn du ne Lösung hast, würde mich mal interessieren, wie man es machen kann.

Kannst du vielleicht noch verraten, bei welcher praktischen Anwendung so ein Problem auftritt? Habe keine Idee, wozu man diese unvollständigen Binärzahlen nutzen könnte.

#19

ich hoffe sehr, dass dieses Problem NICHT NP-vollständig ist (d.h. dass es keine schnellere Methode als alle Zahlen ausschreiben gibt).

Ich werde noch mehr Details über die Verwendung posten, aber ich habe gerade keine Zeit (bin im Internet-Cafe)…