Anzahl Codierungen für n Kontakte und beliebig viele Verbindungen

12/07/2014 - 21:33 von Frank Buss | Report spam
Ich habe mir die Frage gestellt, wieviel Codierungsmöglichkeiten es
gibt, wenn man n Kontakte hat und diese beliebig untereinander per
Dràhte verbinden kann. Abgefragt werden könnte das dann, indem man von
jedem Kontakt zu jedem anderen Kontakt misst, ob eine Verbindung besteht.

Für ein Kontakt gibt es nur eine Möglichkeit. Für zwei Kontakte gibt es
zwei Möglichkeiten (Verbindung zwischen 1 und 2 da oder nicht da). Für
drei Kontakte gibt es 5 Möglichkeiten:

1. keine Verbindung
2. 1-2
3. 2-3
4. 1-2, 2-3
5. 1-3

Zu beachten hierbei, daß z.B. die Kombination [1-3, 2-3] identisch mit
[1-2, 2-3] ist, weil bei beiden Kombinationen alle drei Kontakte
verbunden sind. Daher ist die Anzahl nicht n! .

Da ich schneller beim Programmieren als beim mathematischen Denken war,
habe ich mal ein Programm geschrieben, was die Kombinationen alle
durchtestet:

http://pastebin.com/NxgGsvEg

Rechnet schon bei n=9 ziemlich lange, aber dank OEIS fand ich dann die
passende Sequenz:

https://oeis.org/A000110

Und leider erst dann wurde mir klar, daß es genau das ist, weil die
Bedingung "beliebige Verdrahtungskombination" dasselbe ist, wie
"beliebige Partition" (weil eine Verbindung a-b und eine Verbindung a-c
elektrisch dasselbe ist, wie eine Verbindung a-b-c), was dann natürlich
auch die Berechnung sehr vereinfacht. Ich muß wohl mehr mit
Mathe-Puzzlen üben, oder mir zumindest die ersten paar hundert
OEIS-Eintràge durchlesen :-)

Wàre noch interessant, wieviel Messungen man für n Kontakte braucht, um
die Verdrahtung herauszufinden. Ist die Anzahl nötiger Messungen immer
(n-1)*n/2, also vom ersten Kontakt zu allen folgenden messen, dann vom
zweiten zu allen folgenden usw.? Es gibt zumindest ein paar Abkürzungen,
z.B. wenn man festgestellt hat, daß alle Kontakte verbunden sind, dann
braucht man nicht mehr weiterzumessen.

Am spannendsten wàre noch ein einfacher Algorithmus, um anhand der
Messung die Nummer der Kombination zu ermitteln (angenommen
alle Partitionen für ein gegebenes n wàren nach einem geeigneten
Algorithmus durchnummeriert), ohne alle Partitionen in einer Tabelle
vorher gespeichert zu haben. Also im Beispiel von oben mit 5
Möglichkeiten, wenn man [1-2, 1-3] misst, daß dann 4 als Ergebnis
herauskommt. Besonders für größere n könnte man damit sehr viel mehr
Zahlen mit n Kontakten codieren, als mit einem rein binàren Verfahren,
und das bei noch verhàltnismàßig wenig Messungen, die zudem noch von
einem kleinen Microcontroller ohne viel Speicher durchgeführt werden
könnten.

Frank Buss, http://www.frank-buss.de
C64 MIDI interface, preorder: http://www.frank-buss.de/c64/midi/buy.html
 

Lesen sie die antworten

#1 Hans-Peter Diettrich
13/07/2014 - 02:23 | Warnen spam
Frank Buss schrieb:
Ich habe mir die Frage gestellt, wieviel Codierungsmöglichkeiten es
gibt, wenn man n Kontakte hat und diese beliebig untereinander per
Dràhte verbinden kann. Abgefragt werden könnte das dann, indem man von
jedem Kontakt zu jedem anderen Kontakt misst, ob eine Verbindung besteht.



IMO sieht der optimale Algorithmus so aus:

1. Ersten nicht gemessenen/verbundenen Anschluß suchen.
2. Alle nachfolgenden (und nicht verbundenen) Anschlüsse testen und
Verbindungen in die Tabelle eintragen.
3. Weiter bei 1, bis alle Anschlüsse gemessen oder als verbunden
gefunden wurden.

Die Tabelle könnte dann für jeden Anschluß A (1..n) folgende Werte
enthalten:
0 = nicht gemessen
V = verbunden mit Anschluß V (V>A)
A keine (weitere) Verbindung


Es wàre zu prüfen, ob in [2] nur jeweils der *nàchste* verbundene
Anschluß (N) gesucht werden soll. Das spart den Sonderfall des
Abschlusses einer Kette (ohne weitere Verbindung), die Messung wird dann
mit N fortgesetzt, der dann entweder weiterverbunden oder nicht mehr
verbunden sein kann. Im Detail spielt dann herein, wie lange das
Umschalten zwischen den Anschlüssen dauert.

DoDi

Ähnliche fragen