Anzahl Permutationen? ==> Algorithmus / Formel gesucht
bearbeitet von Gunnar Bittersmann@@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-2} C(i, k-1, b), & \text{sonst} \end{cases} $$
Das kann man direkt so implementieren, bspw. in JavaScript:
~~~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)); // 2024
~~~
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.”_{: lang="en"} —Estelle Weyl
Anzahl Permutationen? ==> Algorithmus / Formel gesucht
bearbeitet von Gunnar Bittersmann@@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 ü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-2} C(i, k-1, b), & \text{sonst} \end{cases} $$
Das kann man direkt so implementieren, bspw. in JavaScript:
~~~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)); // 2024
~~~
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)
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.”_{: lang="en"} —Estelle Weyl
Anzahl Permutationen? ==> Algorithmus / Formel gesucht
bearbeitet von Gunnar Bittersmann@@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 😏, kann man für einen Pfeil _n_ − _b_ + 1 Möglichkeiten, d.h.
_C_(_n_, 1, _b_) = _n_ − _b_ + 1.
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 ü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-2} C(i, k-1, b), & \text{sonst} \end{cases} $$
Das kann man direkt so implementieren, bspw. in JavaScript:
~~~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)); // 2024
~~~
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)
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.”_{: lang="en"} —Estelle Weyl