k-Kombination von n Elementen in x Reihen von n Elementen optimal packen |
| 25.07.2017, 15:48 | niconico | Auf diesen Beitrag antworten » |
| k-Kombination von n Elementen in x Reihen von n Elementen optimal packen Wie nennt man es, wenn man alle möglichen Kombinationen von k Elementen aus einer Menge mit n Elementen so auf möglichst wenige Untermengen mit n Elementen verteilt, dass in jeder Untermenge jede Position nur einmal vorkommt? Hintergrund: Ich will das Vorkommen von allen denkbaren Bitkombinationen von Bits in einer binär dargstellten Zahl in einer Datenbank abfragen. Bei 4 Bits entspricht das den Zahlen 0-15 (0000, 0010, 0011... 1111). Dafür ergeben sich die möglichen Bitkombinationen für zwei Bits (die Bits zeigen nur die zu betrachtende Position an): a:0011, b:0101, c:0110, d:1001, e:1010, f:1100. Für 2 Bit gibt es 4 verschiedene Wertekombinationen, also 6 x 4 Abfragen. Bei den Abfragen bleiben jeweils die 00-Positionen ungenutzt. Packt man die Bits für die Abfrage über die große Datenmenge so zusammen, dass jedes Bit genutzt wird, reduziert man die Laufzeit der Abfragen erheblich. Beim angegebenen Beispie (senkrecht paarweise)l: a:0011 b:0101 c:0110 f:1100 e:1010 d:1001 Die Positionsmasken können so kombiniert werden, dass nur 3 x 4 Abfragen notwendig sind. Diese Optimierung wirkt sich mit wachsendem n natürlich wesentlich stärker aus. Nach programmierbarem Muster funktioniert das sehr gut für k=2 für n, die 2-er Potenzen von k sind. (Experimentell nachgewiesen bis 64 Bit). Bei höheren k und n-Werten wird es jedoch schwierig, solche optimal gepackten Muster zu berechnen. Gibt es für dieses Problem einen Namen? Mit Zykeln, Permutationen usw. komme ich nicht weiter, oder ich habe nicht kapiert, dass und wie sie mit meinem Problem zusammenhängen. |
||
| 25.07.2017, 16:17 | HAL 9000 | Auf diesen Beitrag antworten » |
Ich verstehe in deinem Begleittext nicht, was das ganze mit "Abfragen" zu tun hat - egal. Ich schildere einfach mal, wie ich das ganze abstrahiere: Du betrachtest -stellige Bitmuster mit genau Einsen, davon gibt es genau . Jetzt willst du gewisse dieser Bitmuster so zu Gruppen zusammenfassen, dass in jeder Gruppe an jeder der Bitpositionen eine 1 nur in maximal einem Mitglied der Gruppe vorkommen darf - ist das soweit erstmal richtig? 
Nun, offenkundig kann dann jede Gruppe nur maximal Bitmuster enthalten, und die Anzahl solcher Gruppen ist dann mindestens . Deine Frage ist jetzt wohl, inwieweit diese untere Schranke auch tatsächlich eine untere Grenze ist, bzw. wie eine bessere (realistischere) Abschätzung für diese Anzahl aussieht? |
||
| 25.07.2017, 17:08 | niconico | Auf diesen Beitrag antworten » |
HAL 9000, danke für die prompte Antwort! Was meine ich mit "Abfragen"? Abfragen in einer Datenbank über viele Datensätze, zwischen denen ich logische Beziehungen vermute. Diese Abfragen will ich optimieren... aber das ist nicht wirklich wichtig. Du hast das mathematische Grundproblem richtig umrissen, aber meine Frage ist eine andere. Ich brauche nicht die Anzahl, sondern einen Anpack, wie man die optimalen Pakete berechnet (und sei es nur einen Namen für das Problem - das ist doch sicher eine gängige Aufgabenstellung in der Mathematik, oder?). Am Beispiel wird es deutlicher. Sei n = 6, k = 3. Arrangiert man alle Kombinationen nach folgendem Prinzip: 111000 A 110100 B 110010 C 110001 D 101100 E 101010 F 101001 G 100110 H 100101 I 100011 J 011100 j 011010 i 011001 h 010110 g 010101 f 010011 e 001110 d 001101 c 001011 b 000111 a kann man Aa, Bb, Cc... Jj kombinieren. Bei n = 9 finde ich nicht so einfach ein Prinzip - es müsste wohl ein Dreieck sein. Rein rechnerisch kann es bei n = 9 wieder optimal sein (jedes Bit genutzt, nix doppelt). |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
