Permutation Rechner

🔄 Grundlegende Eigenschaften

Wichtige mathematische Eigenschaften von Permutationen:

\[\text{Definition: } P(n,k) = \frac{n!}{(n-k)!} = n \times (n-1) \times \cdots \times (n-k+1)\] \[\text{Vollständige Permutation: } P(n,n) = n!\] \[\text{Spezialfälle: } P(n,0) = 1, \quad P(n,1) = n\] \[\text{Beziehung zu Kombinationen: } P(n,k) = k! \times C(n,k)\] \[\text{Rekursion: } P(n,k) = P(n-1,k) + k \times P(n-1,k-1)\]

🔄 Unterschied: Permutation vs. Kombination

Abgrenzung zu Kombinationen:

\[\text{Permutation (Reihenfolge wichtig): } P(n,k) = \frac{n!}{(n-k)!}\] \[\text{Kombination (Reihenfolge unwichtig): } C(n,k) = \frac{n!}{k!(n-k)!}\] \[\text{Beziehung: } P(n,k) = k! \times C(n,k)\] \[\text{Beispiel: } P(5,3) = 60, \quad C(5,3) = 10, \quad 60 = 3! \times 10\]

📊 Wichtige Werte

Häufig verwendete Permutationen:

\[\text{Vollständige Permutationen:}\] \[P(3,3) = 3! = 6\] \[P(4,4) = 4! = 24\] \[P(5,5) = 5! = 120\] \[\text{Partielle Permutationen:}\] \[P(5,2) = \frac{5!}{3!} = 20\] \[P(7,3) = \frac{7!}{4!} = 210\] \[P(10,2) = \frac{10!}{8!} = 90\]

📝 Beispiel 1: Wettkampf-Platzierungen

Aufgabe: Anzahl möglicher Platzierungen für die ersten 3 Plätze
Gegeben: 8 Teilnehmer in einem Wettbewerb
Berechnung:

\[\text{Anzahl Möglichkeiten} = P(8,3)\] \[P(8,3) = \frac{8!}{(8-3)!} = \frac{8!}{5!} = 8 \times 7 \times 6 = 336\] \[\text{Erklärung:}\] \[\text{1. Platz: 8 Möglichkeiten}\] \[\text{2. Platz: 7 Möglichkeiten}\] \[\text{3. Platz: 6 Möglichkeiten}\]

Interpretation: 336 verschiedene Möglichkeiten für die ersten drei Plätze

📝 Beispiel 2: Sitzordnung am runden Tisch

Aufgabe: Sitzordnungen von 6 Personen am runden Tisch
Szenario: Zirkuläre Anordnung (Rotation egal)
Berechnung:

\[\text{Lineare Anordnung: } P(6,6) = 6! = 720\] \[\text{Zirkuläre Anordnung: } \frac{6!}{6} = \frac{720}{6} = 120\] \[\text{Allgemein für n Personen: } (n-1)!\] \[\text{Mit fixem Platz für eine Person: } (n-1)! = 5! = 120\]

Anwendung: Unterschied zwischen linearen und zirkulären Permutationen

📝 Beispiel 3: Passwort-Sicherheit

Aufgabe: 4-stelliges Passwort aus 10 Ziffern
Gegeben: Ziffern 0-9, keine Wiederholung erlaubt
Berechnung:

\[\text{Ohne Wiederholung: } P(10,4) = \frac{10!}{6!} = 10 \times 9 \times 8 \times 7 = 5{.}040\] \[\text{Mit Wiederholung: } 10^4 = 10{.}000\] \[\text{Sicherheitsfaktor: } \frac{5{.}040}{10{.}000} = 0.504\] \[\text{Bei 26 Buchstaben: } P(26,4) = 26 \times 25 \times 24 \times 23 = 358{.}800\]

Bedeutung: Ohne Wiederholung reduziert sich die Anzahl möglicher Passwörter

💻 Code-Implementierungen

Effiziente Implementierung von Permutationen:

Python:
import math
from itertools import permutations

def permutation_count(n, k=None):
  """Berechnet P(n,k) = n!/(n-k)!"""
  if k is None:
    k = n # Vollständige Permutation
  if k > n or k < 0:
    return 0
  if k == 0:
    return 1
  
  return math.factorial(n) // math.factorial(n - k)

def permutation_direct(n, k):
  """Direkte Berechnung ohne Fakultät"""
  if k > n or k < 0:
    return 0
  if k == 0:
    return 1
  
  result = 1
  for i in range(n, n - k, -1):
    result *= i
  return result

def generate_permutations(items, k=None):
  """Generiert alle k-Permutationen einer Liste"""
  if k is None:
    k = len(items)
  return list(permutations(items, k))

# Mit itertools (Python standard library)
from itertools import permutations
result = list(permutations([1, 2, 3, 4], 2))
print(f"P(4,2) Permutationen: {result}")

JavaScript:
function permutationCount(n, k = n) {
  if (k > n || k < 0) return 0;
  if (k === 0) return 1;
  
  let result = 1;
  for (let i = n; i > n - k; i--) {
    result *= i;
  }
  return result;
}

function generatePermutations(arr, k = arr.length) {
  if (k === 0) return [[]];
  if (k > arr.length) return [];
  
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    const rest = arr.slice(0, i).concat(arr.slice(i + 1));
    const perms = generatePermutations(rest, k - 1);
    for (const perm of perms) {
      result.push([arr[i], ...perm]);
    }
  }
  return result;
}

C++:
#include <iostream>
#include <vector>
#include <algorithm>

long long permutationCount(int n, int k) {
  if (k > n || k < 0) return 0;
  if (k == 0) return 1;
  
  long long result = 1;
  for (int i = n; i > n - k; --i) {
    result *= i;
  }
  return result;
}

// Mit STL
std::vector<int> items = {1, 2, 3, 4};
std::sort(items.begin(), items.end());
do {
  // Verarbeite Permutation
} while (std::next_permutation(items.begin(), items.end()));

🎯 Erweiterte Permutations-Klasse

Umfassende Permutations-Berechnungen:

Python Permutations-Klasse:
import math
from itertools import permutations
from collections import Counter

class PermutationCalculator:
  @staticmethod
  def simple_permutation(n, k=None):
    """P(n,k) = n!/(n-k)!"""
    if k is None: k = n
    if k > n: return 0
    return math.factorial(n) // math.factorial(n - k)
  
  @staticmethod
  def circular_permutation(n):
    """Zirkuläre Permutationen: (n-1)!"""
    if n <= 1: return 1
    return math.factorial(n - 1)
  
  @staticmethod
  def permutation_with_repetition(n, repetitions):
    """Permutationen mit Wiederholungen: n!/(n1! * n2! * ...)"""
    total = math.factorial(n)
    for count in repetitions:
      total //= math.factorial(count)
    return total
  
  @staticmethod
  def derangement(n):
    """Derangements: !n (Subfakultät)"""
    if n == 0: return 1
    if n == 1: return 0
    return (n - 1) * (PermutationCalculator.derangement(n - 1) +
                             PermutationCalculator.derangement(n - 2))
  
  @staticmethod
  def generate_all_permutations(items, k=None):
    """Generiert alle Permutationen"""
    if k is None: k = len(items)
    return list(permutations(items, k))
  
  @staticmethod
  def lexicographic_rank(permutation, items):
    """Lexikographischer Rang einer Permutation"""
    n = len(items)
    rank = 0
    items_copy = items.copy()
    
    for i in range(n):
      pos = items_copy.index(permutation[i])
      rank += pos * math.factorial(n - 1 - i)
      items_copy.remove(permutation[i])
    
    return rank

# Beispiele
calc = PermutationCalculator()
print(f"P(7,3) = {calc.simple_permutation(7, 3)}") # 210
print(f"Zirkulär 5 Personen: {calc.circular_permutation(5)}") # 24
print(f"AABBCC Permutationen: {calc.permutation_with_repetition(6, [2, 2, 2])}") # 90
print(f"Derangement von 4: {calc.derangement(4)}") # 9

# Alle Permutationen von [1,2,3] mit k=2
perms = calc.generate_all_permutations([1, 2, 3], 2)
print(f"P(3,2) Permutationen: {perms}") # [(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)]

🎯 Anwendungs-Simulator

Simulation praktischer Permutations-Probleme:

Python Anwendungs-Simulator:
import random
import math
from itertools import permutations

class PermutationSimulator:
  @staticmethod
  def tournament_simulator(participants, podium_places=3):
    """Simuliert Turnier-Platzierungen"""
    n = len(participants)
    total_arrangements = math.factorial(n) // math.factorial(n - podium_places)
    
    print(f"Turnier mit {n} Teilnehmern:")
    print(f"Mögliche Top-{podium_places} Platzierungen: {total_arrangements}")
    
    # Beispiel-Platzierung generieren
    shuffled = participants.copy()
    random.shuffle(shuffled)
    podium = shuffled[:podium_places]
    
    print(f"Beispiel-Platzierung: {podium}")
    return total_arrangements
  
  @staticmethod
  def password_security_analysis(alphabet_size, password_length, allow_repetition=False):
    """Analysiert Passwort-Sicherheit"""
    if allow_repetition:
      total_combinations = alphabet_size ** password_length
      method = "mit Wiederholung"
    else:
      if password_length > alphabet_size:
        return 0 # Unmöglich ohne Wiederholung
      total_combinations = math.factorial(alphabet_size) // math.factorial(alphabet_size - password_length)
      method = "ohne Wiederholung"
    
    print(f"Passwort-Analyse ({method}):")
    print(f"Alphabet-Größe: {alphabet_size}")
    print(f"Passwort-Länge: {password_length}")
    print(f"Mögliche Kombinationen: {total_combinations:,}")
    
    # Brute-Force Zeit schätzen
    attempts_per_second = 1000000 # 1 Million Versuche/Sekunde
    seconds = total_combinations // (2 * attempts_per_second) # Durchschnittlich die Hälfte
    hours = seconds // 3600
    days = hours // 24
    years = days // 365
    
    if years > 0:
      print(f"Geschätzte Brute-Force Zeit: {years:,} Jahre")
    elif days > 0:
      print(f"Geschätzte Brute-Force Zeit: {days:,} Tage")
    elif hours > 0:
      print(f"Geschätzte Brute-Force Zeit: {hours:,} Stunden")
    else:
      print(f"Geschätzte Brute-Force Zeit: {seconds:,} Sekunden")
    
    return total_combinations
  
  @staticmethod
  def seating_arrangement(people, round_table=False):
    """Berechnet Sitzordnungen"""
    n = len(people)
    
    if round_table:
      arrangements = math.factorial(n - 1) if n > 0 else 1
      table_type = "runder Tisch"
    else:
      arrangements = math.factorial(n)
      table_type = "linearer Tisch"
    
    print(f"Sitzordnung ({table_type}):")
    print(f"Personen: {people}")
    print(f"Mögliche Anordnungen: {arrangements:,}")
    
    return arrangements

# Beispiel-Simulationen
simulator = PermutationSimulator()

# Turnier-Simulation
teilnehmer = ["Alice", "Bob", "Charlie", "David", "Eva"]
simulator.tournament_simulator(teilnehmer, 3)

# Passwort-Analyse
simulator.password_security_analysis(26, 4, False) # 4 Buchstaben ohne Wiederholung
simulator.password_security_analysis(36, 6, True) # 6 Zeichen mit Wiederholung

# Sitzordnung
personen = ["Anna", "Ben", "Clara", "Daniel"]
simulator.seating_arrangement(personen, False)
simulator.seating_arrangement(personen, True)