Algorithmus für ein Symbolpuzzle

[Blaubart]

Tach.

Ich suche einen Algorithmus für eine Art Symbolpuzzle. Falls die folgende Beschreibung "zu mathematisch" ist, versuch ich es auch gerne nochmal anders ...

Aus einem Vorrat von N verschiedenen Symbolen

z. B. {a, b, c, d, e, f, g, h} für N = 8

läß sich eine Abfolge bilden, in der jedes Symbol jeweils genau einem Index von 0 bis N-1 zugeordnet ist:

Index:  0  1  2  3  4  5  6  7
    Symbol: b  d  a  f  g  c  e  h

Sei in einer solchen Abfolge nun S(X,Y) der Abstand zwischen zwei Symbolen X und Y, der die Anzahl der Schritte angibt, die man von X aus vorwärts gehen muß, um zu Y zu gelangen. Für die obige Beispielabfolge:

S(b,a) = 2
    S(f,h) = 4
    S(e,d) = 3
    ...

Gezählt wird der Abstand S(X,Y) dabei modulo N, wodurch immer

0 <= S(X,Y) < N

gilt. Mehrere dieser Abstandsangaben lassen sich nun als Sequenzen der Form

[bage], [ah], [bfe], ...

schreiben, wobei z. B. [bage] ausgeschrieben

S(b,a) = S(a,g) = S(g,e)

bedeutet. Mehrere dieser Sequenzen (auch unterschiedlicher Länge) sollen in einer Menge zusammengefaßt werden. Der Symbolabstand aller Sequenzen einer Menge soll dabei jeweils gleich sein, also beispielsweise

Menge M_1 = {[bage], [df], [hd]}

-> S(b,a) = S(a,g) = S(g,e) = S(d,f) = S(h,d) = 2

für die obige Beispielabfolge. In den anderen Mengen kann der Abstand natürlich einen anderen Wert als 2 annehmen.

Nach dem formellen Vorgeplänkel hier meine Problemstellung:

Gegeben ist ein bekannter Symbolvorrat mit N Symbolen, außerdem eine Handvoll Sequenzmengen M_1, M_2, ...

Gesucht ist nun eine Abfolge der Symbole (Zuordnung zu den Indizes 0 bis N-1), die die Bedingungen aller gegebenen Sequenzen erfüllt. Die Symbolabstände in den Sequenzen einer Menge sind zwar jeweils gleich, aber nicht bekannt -- sonst wäre das Finden der Abfolge ja nicht so schwer.

Einige Spezialfälle helfen beim "Lösen durch Ausprobieren". Aus der zyklischen Symbolfolge [bgb] folgt beispielsweise für gerades N, daß S(b,g) = S(g,b) = N/2 ist, und somit auch die Abstände der anderen Symbole in den Sequenzen der gleichen Menge N/2 betragen.

Einen rechnertauglichen Algorithmus zur Lösung dieses Problems konnte ich bisher nicht entwickeln. Hat jemand von euch eine Idee oder kennt ein ähnliches Problem aus der Mathematik/Informatik, das als Ansatz dienen könnte?

[oma]

Du hast doch schon geschrieben was zu tun ist, ("'Pseudo-Code'") das setzt du jetzt in konkreten Code um. Hast du damit Probleme?

[Blaubart]

Tach.

An welcher Stelle hast du die Beschreibung eines konkreten Algorithmus ("was zu tun ist") erkannt? Und um eine Brute-Force-Methode geht es mir auch nicht (falls es sich auch anders lösen läßt).

Reden wir wirklich vom gleichen Ziel?

[seth_not@home]

gudn tach!

mein sitznachbar hatte soeben spontan eine auf den ersten blick sehr gute idee:

Sym:={'a','b','c',...} = menge der symbole
  p:Sym->{0,...,n-1} = position der symbole (gesucht)

geg. sind die mengen M_i, durch welche die unbekannten abstaende c_i charakterisiert sind.

z.b. ergaeben sich aus M_1={[abc], [de]}, M_2={[fe]} die gleichungen

p(b)-p(a) = c_1
  p(c)-p(b) = c_1
  p(e)-p(d) = c_1
  p(f)-p(e) = c_2,

die man in ein LGS Ax=b ueberfuehren koennte.
  x = vektor mit den positionen
  b = vektor mit den konstanten c_i
  A = matrix mit 0, 1, -1 an den entsprechenden stellen

z.b. A=
  -1  1  0  0  0  0
   0 -1  1  0  0  0
   0  0  0 -1  1  0
   0  0  0  0 -1  1

x = (p(a) p(b) p(c) p(d) p(e))^T
  b = (c_1 c_1 c_1 c_2)^T

da die konstanten aber auch noch unbekannt sind, kann man diese auf die andere seite schieben, d.h.

x = vektor mit den positionen und den konstanten c_i
  b = 0
  A = matrix mit 0, 1, -1 an den entsprechenden stellen

als im beispiel

p(b)-p(a)-c_1=0
  p(c)-p(b)-c_1=0
  p(e)-p(d)-c_1=0
  p(f)-p(e)-c_2=0,

somit waere dann b=0, x=(p(a) p(b) p(c) p(d) p(e) c_1 c_2)^T und A noch um 2 spalten erweitert.

das LGS muesste dann modulo n geloest werden.

prost
seth

[Blaubart]

Tach.

Als homogenes LGS hab ich dieses Problem auch schon modelliert. Allerdings hab ich das fast genauso schnell wieder verworfen, da sich zwar Verfahren wie der Gaußalgorithmus wunderbar im Rechner implementieren lassen ...

das LGS muesste dann modulo n geloest werden.

... mir aber genau diese Moduloaddition Kopfzerbrechen bereitet. Gibt es denn für die Lösung solcher Systeme mit Moduloadditionen in den Skalarprodukten auch Standardverfahren?

Ich habe in einigen Versuchen nie auch nur eine Lösung gefunden, wenn ich die Moduloaddition einfach vernachlässigte und das LGS einfach mit dem GALG löste. Sicher gibt es auch Fälle, in denen die gegebenen Gleichungen dafür passen, aber dies sind mit Sicherheit *sehr* seltene Konstellationen.

[Blaubart]

Ich habe in einigen Versuchen nie auch nur eine Lösung gefunden, wenn ich die Moduloaddition einfach vernachlässigte und das LGS einfach mit dem GALG löste.

Damit meinte ich: Ich habe einige Versuche gemacht, aber nie auch nur eine Lösung gefunden ...

[seth_not@home]

gudn tach!

das LGS muesste dann modulo n geloest werden.

... mir aber genau diese Moduloaddition Kopfzerbrechen bereitet.

hmm, ich dachte, man koennte hier einfach gauss anwenden. man muss iirc bloss immer modulo n rechnen und evtl. mal den euklidischen algorithmus anwenden oder so; oder nicht?

Ich habe in einigen Versuchen nie auch nur eine Lösung gefunden, wenn ich die Moduloaddition einfach vernachlässigte und das LGS einfach mit dem GALG löste.

ohne kongruenzrechnung kommen halt meist auch nicht-ganze zahlen heraus und das will man ja nicht.

prost
seth

[Blaubart]

Tach.

hmm, ich dachte, man koennte hier einfach gauss anwenden. man muss iirc bloss immer modulo n rechnen und evtl. mal den euklidischen algorithmus anwenden oder so; oder nicht?

Da könntest du recht haben. Ich glaube, ich hab durch einen Fehler in den Zeilenoperationen beim GALG Moduloaddition und normale Addition etwas inkonsequent durcheinandergeworfen (wegen gelegentlich auftretender negativer Vorzeichen). Wichtig scheint hier nur zu sein, daß man ausschließlich *eins* von beiden durchzieht und ggf. erst am Ende (beim Ablesen der Lösung aus der normierten Zeilenstufenform) durch mod N wieder in den gewünschten Wertebereich kommt.

Dank dir soweit. :)