@@Matthias Apsel
Eine allgemeine Lösung:
Wo eure Katzen aus dem Sack sind, lass ich meine auch raus.
n ist die Anzahl der vorhandenen Slots,
Wobei in dem Fall n = Länge / Gridbreite = 54mm / 2mm = 27.
k die Anzahl der zu platzierenden Items und
b die Anzahl der durch ein Item blockierten Slots
Hatte ich ursprünglich nicht mit drin, sondern in dem Fall b = Pfeilbreite / Gridbreite = 4mm / 2 mm = 2 fest drin.
Nochmal hingeschaut: ja, ich kann problemlos auf beliebiges b verallgemeinern.
Die Anzahl der Möglichkeiten bezeichne ich mit C(n, k, b).
Um überhaupt k Pfeile der Breite b plazieren zu können, braucht man verständlicherweise mindestens b · k Slots. Anders gesagt:
für n < b · k ist C(n, k, b) = 0.
Wie man leicht sieht 😏, hat man für einen Pfeil n − b + 1 Möglichkeiten, d.h.
C(n, 1, b) = n − b + 1.
(So kamt ihr auf 26.)
Den ersten Pfeil kann man nun an Position 1 (Slots 1 bis b) setzen. Dann gibt es C(n − b, k − 1, b) Möglichkeiten, die übrigen k − 1 Pfeile in den übrigen n − b Slots unterzubringen.
Den ersten Pfeil kann man auch an Position 2 (Slots 2 bis b + 1) setzen. Dann gibt es C(n − b − 1, k − 1, b) Möglichkeiten, die übrigen k − 1 Pfeile in den übrigen n − b − 1 Slots unterzubringen, usw.
Man muss also aufsummieren: C(n − b, k − 1, b) + C(n − b − 1, k − 1, b) + C(n − b − 2, k − 1, b) + … + C(1, k − 1, b)
(Die letzten Summanden C(i, k − 1, b) sind 0 wegen i < b · (k − 1). Man könnte sich auch überlegen, was der letzte von 0 verschiedene Summand ist und die Berechnung dort abbrechen. Muss man aber nicht.)
$$C(n, k, b) = \begin{cases}0, & \text{wenn } n < b \cdot k \ n - b + 1, & \text{wenn } k = 1 \ \sum_{i=1}^{n-b} C(i, k-1, b), & \text{sonst} \end{cases} $$
Das kann man direkt so implementieren, bspw. in JavaScript:
function C(n, k, b)
{
if (n < b * k)
{
return 0;
}
else if (k == 1)
{
return n - b + 1;
}
else
{
for (var s = 0, i = n - b; i > 0; i--)
{
s += C(i, k - 1, b);
}
return s;
}
}
console.log(C(27, 3, 2));
Oder man überlegt sich halt, dass
C(n, 2, 2) = C(n − 2, 1, 2) + C(n − 3, 1, 2) + … C(1, 1, 2)
= (n − 3) + (n − 4) + … + 1 + 0
= ½ · (n − 3)(n − 2)
(Da isser, der Gauß.)
Für C(27, 3, 2) ergibt sich dann ½ · 22 · 23 + ½ · 21 · 22 + … + ½ · 1 · 2
Und das war die Stelle, wo ich am Ende vergessen hatte, durch 2 zu teilen.
LLAP 🖖
--
“I love to go to JS conferences to speak about how to avoid using JavaScript. Please learn CSS & HTML to reduce your JS code bloat.” —Estelle Weyl