Μετάθεση (μαθηματικά)

Στα μαθηματικά, μια μετάθεση ενός συνόλου είναι μια τοποθέτηση των στοιχείων αυτού με μια συγκεκριμένη σειρά.

Για παράδειγμα, για τα στοιχεία του συνόλου $X=\{{\color {red}\alpha },{\color {green}\beta },{\color {blue}\gamma }\}$ υπάρχουν οι εξής έξι μεταθέσεις:

$({\color {red}\alpha },{\color {green}\beta },{\color {blue}\gamma })$

$({\color {red}\alpha },{\color {blue}\gamma },{\color {green}\beta })$

$({\color {green}\beta },{\color {red}\alpha },{\color {blue}\gamma })$

$({\color {green}\beta },{\color {blue}\gamma },{\color {red}\alpha })$

$({\color {blue}\gamma },{\color {red}\alpha },{\color {green}\beta })$

$({\color {blue}\gamma },{\color {green}\beta },{\color {red}\alpha })$

Στην γενική περίπτωση, το πλήθος των μεταθέσεων συνόλου με $\nu$ στοιχεία είναι ${\displaystyle \nu$ !} (νι παραγοντικό, δηλαδή

${\displaystyle \nu$ !=\nu \cdot (\nu -1)\cdot \ldots \cdot 2\cdot 1} .

Οι διατάξεις αφορούν ένα υποσύνολο των στοιχείων του αρχικού συνόλου. Οι διατάξεις με επανάληψη επιτρέπουν επαναλήψεις, ενώ οι συνδυασμοί δεν προϋποθέτουν τα στοιχεία να έχουν κάποια σειρά.

Παραδείγματα

Παράδειγμα 1ο

Σε μία τάξη με $\nu$ μαθητές και $\nu$ θρανία υπάρχουν τόσοι δυνατοί τρόποι να καθίσουν οι μαθητές στα θρανία όσες και οι μεταθέσεις, δηλαδή ${\displaystyle \nu$ !} .

Παράδειγμα 2ο

Μία ομάδα παιδιών θέλει να πει τα κάλαντα σε πέντε σπίτια. Υπάρχουν $5!$ δυνατές σειρές με τις οποίες μπορούν να χτυπήσουν τα κουδούνια.

Πλήθος μεταθέσεων

ν	ν!
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	5040
8	40320
9	362880
10	3628800
11	39916800
12	479001600

Το πλήθος των μεταθέσεων ενός συνόλου με $\nu$ στοιχεία είναι ${\displaystyle \nu$ !} που είναι ίσο με

${\displaystyle \nu$ !=\nu \cdot (\nu -1)\cdot \ldots 2\cdot 1} .

Απόδειξη  

Αυτό προκύπτει επαγωγικά. Για $\nu =1$, υπάρχει μία δυνατή μετάθεση για αυτό το στοιχείο.

Για $\nu \geq 2$, υπάρχουν $\nu$ τρόποι να διαλέξουμε το πρώτο στοιχείο της μετάθεσης (διαλέγοντας οποιοδήποτε από τα $\nu$ στοιχεία) και έπειτα υπάρχουν $\nu -1$ στοιχεία για τις υπόλοιπες θέσεις. Από την επαγωγική υπόθεση υπάρχουν $(\nu -1)!$ τρόποι να διατάξουμε αυτά τα στοιχεία και επομένως συνολικά ${\displaystyle \nu \cdot (\nu -1)!=\nu$ !} τρόποι να διατάξουμε τα $\nu$ στοιχεία.

Αναδρομική κατασκευή μεταθέσεων

Αναδρομική κατασκευή μεταθέσεων με τρία στοιχεία, χρησιμοποιώντας τις μεταθέσεις δύο στοιχείων.

Γενική αναδρομική κατασκευή μεταθέσεων με $\nu$ στοιχεία, έχοντας τις μεταθέσεις για τα $\nu -1$ στοιχεία.

Κατασκευή μεταθέσεων

Αναδρομική κατασκευή

Ο παρακάτω κώδικας βρίσκει τις δυνατές μεταθέσεις στοιχείων με την χρήση αναδρομής, διαλέγοντας κάθε ένα από τα $\nu$ δυνατά στοιχεία να είναι το πρώτο και υπολογίζοντας όλες τις μεταθέσεις για τα υπολοιπόμενα στοιχεία. Έπειτα, ενώνουμε τις μεταθέσεις που λάβαμε από κάθε επιλογή.

Γενική αναδρομική κατασκευή μεταθέσεων με $\nu$ στοιχεία, έχοντας τις μεταθέσεις για τα $\nu -1$ στοιχεία.

# Βοηθητική συνάρτησηη που προσθέτει ένα στοιχείο σε κάθε μία από τις δοσμένες λίστες.
def append_to_all(v, arrs):
  ans = []
  for arr in arrs:
    ans.append([v] + arr)
  return ans

def generate_all_permutations(arr):
  # Βασική περίπτωση: Ο πίνακας δεν έχει άλλα στοιχεία.
  if len(arr) == 0:
    return [[]]
  ans = []
  # Για κάθε στοιχείο το βάζουμε πρώτο και βρίσκουμε αναδρομικά
  #  όλες τις μεταθέσεις για τα υπόλοιπα.
  for i in range(len(arr)):
    rem = generate_all_permutations(arr[:i] + arr[i+1:])
    ans += append_to_all(arr[i], rem)
  return ans

print(generate_all_permutations([1,2,3]))

Λεξικογραφική κατασκευή

Ο προηγούμενος κώδικας βρίσκει όλες τις δυνατές μεταθέσεις. Ο παρακάτω κώδικας βρίσκει τις μεταθέσεις την μία μετά την άλλη σε γραμμικό χρόνο (για την κάθε μία). Αυτό είναι πιο αποδοτικό για την μνήμη που χρησιμοποιεί και πιο αποδοτικό όταν θέλουμε να δούμε ένα μικρό υποσύνολο από τις δυνατές μεταθέσεις.

Δουλεύει με τον εξής τρόπο:

1. Βρίσκουμε το μεγαλύτερο suffix της μετάθεσης που είναι φθίνον.

${\texttt {[6,3,}}{\underline {\texttt {5,4,2,1}}}{\texttt {]}}$

1. Το αντιστρέφουμε

${\texttt {[6,3,}}{\underline {\texttt {1,2,4,5}}}{\texttt {]}}$

1. Αλλάζουμε θέση στο στοιχείο αριστερά από το suffix και στο αμέσως μεγαλύτερό του στα δεξιά

${\texttt {[6,4,}}{\underline {\texttt {1,2,3,5}}}{\texttt {]}}$

Η παραπάνω διαδικασία εγγυάται ότι θα διαπεράσουμε τις μεταθέσεις από την λεξικογραφικά μικρότερη προς την λεξικογραφικά μεγαλύτερη.

def next_permutation(arr):
  i = len(arr) - 1
  prev = -1
  while i >= 0 and arr[i] > prev:
    prev = arr[i]
    i -= 1
  if i == -1:
    arr[:] = reversed(arr[:])
    return
  tmp = arr[i]
  j = i + 1
  arr[j:] = reversed(arr[j:])
  while arr[j] < tmp:
    j += 1
  arr[i] = arr[j]
  arr[j] = tmp

arr = [1,2,3,4]
for i in range(25):
  print(arr)
  next_permutation(arr)

Κατασκευή τυχαίας μετάθεσης

Μία τυχαία μετάθεση μπορεί να δημιουργηθεί με τον εξής αλγόριθμο:

1. Διαλέγουμε τυχαία από τα $\nu$ στοιχεία ποιο θα βάλουμε στην πρώτη θέση.
2. Έπειτα διαλέγουμε μία μετάθεση για τα υπόλοιπα $\nu -1$ στοιχεία.

import random

def shuffle(arr):
  N = len(arr) - 1
  for i in range(N):
    j = random.randint(i, N)
    tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp

arr = [1,2,3,4,5,6]
shuffle(arr)
print(arr)

Δείτε επίσης

• Διάταξη
• Συνδυασμός

Παραπομπές

• Γ. Κοκολάκης, Εισαγωγή στη Θεωρία Πιθανοτήτων και Στατιστική, 1991
• Άλγεβρα Β΄Λυκείου, Ο.Ε.Δ.Β., 1992