Anzahl Permutationen? ==> Algorithmus / Formel gesucht

[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-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)); // 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 🖖