Δημιουργία συνδυασμών

Έστω ότι έχουμε συνδυασμό k από n αντικείμενα. {a1, a2,,ak}. Κατά τη λεξικογραφική διάταξη o επόμενος συνδυασμός {b1, b2,,bk} θα είναι τέτοιος ώστε:

  1. ai=bi, 1£ i£ m-1 και am<bm για το μεγαλύτερο δυνατό m
  2. bm= am+1
  3. bj+1=bj+1 για m £ j£ k-1

Η μεθοδολογία έχει ως εξής: Στο συνδυασμό {a1, a2,,ak} ορίζουμε τη μέγιστη δυνατή τιμή του αj να είναι n-k+j. Το μέγιστο m που ικανοποιεί την (1) είναι αυτό για το οποίο το am δεν είναι ίσο με τη μέγιστη τιμή του. Έτσι προσδιορίζουμε τη θέση m εξετάζοντας ένα προς ένα τα στοιχεία ενός συνδυασμού από δεξιά προς τα αριστερά.. Στη συνέχεια καθορίζουμε τα bmbm+1…bn σύμφωνα με τα 2 και 3.

Παράδειγμα: Καταγράψτε όλους τους συνδυασμούς 4 από 6 αντικείμενα κατά τη λεξικογραφική διάταξη.

 

{1,2,3,4}, {1,2,3,5}, {1,2,3,6}, {1,2,4,5}, {1,2,4,6}, {1,2,5,6}, {1,3,4,5}, {1,3,4,6}, {1,3,5,6}, {1,4,5,6}, {2,3,4,5}, {2,3,4,6}, {2,3,5,6}, {2,4,5,6}, {3,4,5,6}