Auswahlproblem (Designtheorie?)

30/05/2008 - 19:48 von Siegbert Steinlechner | Report spam
Hallo,

beim Versuch einer optimalen technischen Umsetzung eines Verfahrens aus
der Codierungstheorie bin ich auf folgendes mathematische Problem gestoßen:

Gegeben ist eine Matrix A der Dimension 4 x 1240.
Jede der 1240 Spalten enthàlt 4 unterschiedliche ganze Zahlen aus dem
Bereich 1..32.
Jede der 32 Zahlen kommt in der Matrix gleich hàufig vor, nàmlich
in genau 1240*4/32 = 155 Spalten.
Jedes beliebige Zahlenpaar (aus 1..32) kommt in den Spalten der Matrix
gleich hàufig vor, nàmlich 1240*(4 über 2)%(32 über 2) = 15 mal.
Jedes beliebige Zahlentripel (aus 1..32) kommt in den Spalten der Matrix
gleich hàufig vor, nàmlich 1240*(4 über 3)%(32 über 3) = 1 mal.

Gesucht ist eine Auswahl von 48 Spalten der Matrix A. Die Auswahl wird
durch eine Matrix B der Dimension 4 x 48 beschrieben. B soll folgende
Eigenschaft besitzen:
Jede der Zahlen in B kommt genau 48*4/32 = 6 mal vor.
Zwei beliebige Spalten von B haben höchstens einen gemeinsamen Eintrag.

Frage: existiert B, und wie kann man B in vertretbarer Zeit finden?
Eine simple Absuche führt zu (1240 über 48) ~ 10^87 Möglichkeiten =>
keine Chance auf diesem Weg.
Ein etwas intelligenteres Suchprogramm fand nach ca. 30h Rechenzeit in
Matlab immerhin schon mal eine Kombination von 46 Spalten, was mich in
der Annahme bestàrkt, dass B existiert.

Wer sich nàher mit dem Problem befassen will: die Matrix A könnte ich
als Mail (gezippte Textdatei) versenden.

Gruß
Siegbert
 

Lesen sie die antworten

#1 Michael Steyer
03/06/2008 - 04:09 | Warnen spam
Hallo Siegbert,

kommt es darauf an, dass die Zeilen von B tatsàchlich aus A stammen ?

Es wàre denkbar, dass man ohne Kenntnis von A versucht B zu finden, denn die
Forderungen für A sind nicht m.E. nicht einschrànkend für B.

Dem ersten Gefühl nach würde ich dann die Zeilen nicht aus A auswàhlen,
sondern B versuchen von Beginn an aufzubauen. Oft findet man in Designs
Eigenschaften von orthogonalen lateinischen Quadraten wieder - siehe z.B.
http://groups.google.de/group/de.sc...01e7a16ca6

Unter Umstànden kann man nach scharfem Nachdenken argumentieren, dass es
keine Lösung geben kann, siehe z.B.
http://groups.google.de/group/rec.p...24484a1835

Ich werde mal darüber nachdenken. In der Zwischenzeit empfehle ich ein
wunderbares Buch zu dem Thema, nàmlich das CRC Handbook of Combinatorial
Design.

Michael


"Siegbert Steinlechner" schrieb im Newsbeitrag
news:g1pei5$o68$
Hallo,

beim Versuch einer optimalen technischen Umsetzung eines Verfahrens aus
der Codierungstheorie bin ich auf folgendes mathematische Problem
gestoßen:

Gegeben ist eine Matrix A der Dimension 4 x 1240.
Jede der 1240 Spalten enthàlt 4 unterschiedliche ganze Zahlen aus dem
Bereich 1..32.
Jede der 32 Zahlen kommt in der Matrix gleich hàufig vor, nàmlich
in genau 1240*4/32 = 155 Spalten.
Jedes beliebige Zahlenpaar (aus 1..32) kommt in den Spalten der Matrix
gleich hàufig vor, nàmlich 1240*(4 über 2)%(32 über 2) = 15 mal.
Jedes beliebige Zahlentripel (aus 1..32) kommt in den Spalten der Matrix
gleich hàufig vor, nàmlich 1240*(4 über 3)%(32 über 3) = 1 mal.

Gesucht ist eine Auswahl von 48 Spalten der Matrix A. Die Auswahl wird
durch eine Matrix B der Dimension 4 x 48 beschrieben. B soll folgende
Eigenschaft besitzen:
Jede der Zahlen in B kommt genau 48*4/32 = 6 mal vor.
Zwei beliebige Spalten von B haben höchstens einen gemeinsamen Eintrag.

Frage: existiert B, und wie kann man B in vertretbarer Zeit finden?
Eine simple Absuche führt zu (1240 über 48) ~ 10^87 Möglichkeiten => keine
Chance auf diesem Weg.
Ein etwas intelligenteres Suchprogramm fand nach ca. 30h Rechenzeit in
Matlab immerhin schon mal eine Kombination von 46 Spalten, was mich in der
Annahme bestàrkt, dass B existiert.

Wer sich nàher mit dem Problem befassen will: die Matrix A könnte ich als
Mail (gezippte Textdatei) versenden.

Gruß
Siegbert


Ähnliche fragen