mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Suche Algorithmus für "Binärproblem"


Autor: Andreas Guter (andreasguter)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ich habe folgendes Problem und suche für die Lösung einen möglichst 
effizienten Algorithmus:

Gegeben ist eine Länge l, die die Anzahl von Bits in einem "Bitstring" s 
angibt, z.B. l=10:
s=0000000000

Mehrere Bitstrings der Länge l sind zu erzeugen und in einem Array A 
unterzubringen.


Nach Erzeugung soll folgendes möglich sein:
Man findet möglichst genau einen Bitstring mit der Eigenschaft, dass
s[a]=x, sb]=y und s[c]=z 
ist (also drei Positionen), wobei a, b, c drei(!) verschiedene 
Positionen im Bitstring sind und a, b, c die Werte (0 oder 1)
Sucht man zum Beispiel nach s[2]=1, s[5]=0 und s[9]=0, sollte sich 
möglichst genau ein Bitstring mit dieser Eigenschaft finden lassen.

Dabei soll das Array A, in dem die Strings s gespeichert sind, möglichst 
klein sein; doppelte Vorkommnisse von s[a]=x, s[b=y und s[c]=z in 
verschiedenen Strings s soll also vermieden werden.

(Daher ist es nicht ausreichend einfach alle möglichen Strings in A 
abzuspeichern, wie:
A[0]=0000000000
A[1]=0000000001
...
A[2^10 -2]=1111111111
)

Andreas

Autor: Volker Zabe (vza)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Andreas

Wie gross kann l werden?

Wenn l<= 32 (64) ist würde ich Maske setzen und Ergebniss setzen und

for i....
   if(A[i] & Mask == Ergebniss) then ...

linear suchen.

Was meinst du mit A möglichst kurz?
Ist A nich gegeben?

Ansonsten ist in deinem Beispiel der index von A ja gleich der dezimalem 
wert von s.

Autor: Du (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich versehe nur Bahnhof!

Wer erzeugt den die Strings? Woher kommt a,b,c? welche Bedeutung haben 
die Strings?

Sag doch mal was du vorhast, dann kann man sich das besser vorstellen.

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
woher kommen die 1 im dem Bitstring? Die schreibt ja bloss das ein 
bitstring von der Länge l zu erzeugen ist. Aber soll dort was anders als 
0 drin sein? Wenn ja woher kommt dann die Info.

Autor: Stefan Hennig (stefanhennig)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Andreas,

Ich vermute mal, dass Du z.B. 92 10-Bittige Binärstrings brauchst, um 
alle Möglichkeiten von 3 Bits daraus abzudecken, aber mir fällt noch 
kein Beweis dazu ein, nur eine rekursive Formel. Ich werde mal eine 
Nacht drüber schlafen; vielleicht kann ich morgen was konstruktives 
sagen.

Interessantes Problem.

    Stefan

Autor: Andreas Guter (andreasguter)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Stefan,
genau so meine ich es.

Autor: Michael S. (fandjango)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es gilt aus dem Zahlenvorrat (Binär) 0..0 bis 1..1 der Länge l, also 0 
bis 2 hoch (l-1), bei l=10 z.B. 0-1023 oder binär 0000000000-1111111111 
alle "dubletten" herauszustrichen, bei denen die Anzahl der an der 
selben Stelle übereinstimmenden Nuller oder Einser mehr als 2 an der 
Zahl sind.

Bei l = 3 (trivial) sind dies 8 mögliche Kombinationen
l = 4: Ebenfalls 8, und zwar:
0  0000
3  0011
5  0101
6  0110
9  1001
10 1010
12 1100
15 1111
l = 5: Nur noch 4 Kombinationen
0  00000
7  00111
25 11001
30 11110
l = 6: Ebenfalls 4 Kombinationen
0  000000
15 001111
51 110011
60 111100
Ab l = 7 sind es leider immer nur noch 2 Kombinationen nach dem Schema 
(für das Beispiel l = 10)
0   0000000000
255 0011111111

Die a,b,c (x,y,z) Werte sind daran leicht abzulesen.
000
001
011 und leider nur noch
111. Wobei die 000 und die 111 an etlichen Positionen möglich ist, die 
011 aber nicht, nur an einer. Wie man sieht, fehlt die "101" komplett, 
egal an welcher Position, denn sie würde ja andere Kombinationen 
kompromittieren.

Die Forderung war ja, das jede a,b,c (x,y,z) nicht mehr als einmal 
existieren soll.

Wenn man diese Bedingung lockert und sagt, es sollen "Möglichst wenige" 
Dubletten vorkommen, siehts etwas besser aus, aber dann gibt es 
erhebliche Anzahlen von Dubletten für bestimmte a,b,c (x,y,z) 
Kombinationen.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.