Δημιουργία μεταθέσεων

Λεξικογραφική διάταξη: Για δύο μεταθέσεις a1a2…an, b1b2…bn θα λέμε ότι η a1a2…an προηγείται της b1b2…bn στη λεξικογραφική διάταξη, αν για κάποιο 1£ m<n έχουμε a1=b1, a2=b2,…, am-1=bm-1 και am<bm.

 

Έστω ότι έχουμε τη μετάθεση a1a2…an. Κατά τη λεξικογραφική διάταξη η επόμενη μετάθεση b1b2…bn θα είναι τέτοια ώστε:

  1. ai=bi, 1£ i£ m-1 και am<bm για το μεγαλύτερο δυνατό m
  2. Το bm είναι το ελάχιστο στοιχείο ανάμεσα στα am+1, am+2,…, an το οποίο είναι μεγαλύτερο από am
  3. bm+1<bm+2<< bn

Με βάση τα παραπάνω μπορούμε να βρούμε όλες τις μεταθέσεις n αντικειμένων κατά τη λεξικογραφική διάταξη ξεκινώντας από τη μετάθεση 123…n και καταλήγοντας στη μετάθεση n…321. Η μεθοδολογία έχει ως εξής:

 

Εξετάζουμε ένα προς ένα τα στοιχεία μίας μετάθεσης από δεξιά προς τα αριστερά. Τη πρώτη φορά που θα συναντήσουμε μία ελάττωση προσδιορίζουμε την τιμή του m. Στη συνέχεια καθορίζουμε τα bmbm+1…bn σύμφωνα με τα 2 και 3.

Παράδειγμα: Καταγράψτε όλες τις μεταθέσεις 4 αντικειμένων κατά τη λεξικογραφική διάταξη.

1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321