Suche Algorithmus für "Binärproblem"

[Andreas G. (andreasguter)]

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

[Volker Z. (vza)]

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.

[Du (Gast)]

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.

[Peter (Gast)]

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.

[Stefan H. (stefanhennig)]

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

[Andreas G. (andreasguter)]

Hallo Stefan,
genau so meine ich es.

[Michael S. (fandjango)]

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.