Η αρχή πολλαπλασιασμού γίνεται πολύ χρησιμότερη μετά από την εξής παρατήρηση. Δε χρειάζεται οι επί μέρους επιλογές μας να είναι ανεξάρτητες. Μπορούμε να επιτρέψουμε η πρώτη μας επί μέρους επιλογή να επηρεάζει τις δυνατότητές μας για τη δεύτερη (ή κάποια άλλη) επιλογή, αρκεί να μην επηρεάζει το πλήθος των δυνατοτήτων για την επιλογή αυτή. Δεν απαιτούμε δηλ. να μένει το σύνολο δυνατοτήτων της κάθε επί μέρους επιλογής αναλλοίωτο από κάθε προηγούμενή μας απόφαση, αρκεί να μένει το μέγεθος του συνόλου αναλλοίωτο. Λέμε τότε ότι οι επί μέρους επιλογές μας είναι ημι-ανεξάρτητες (ο όρος δεν είναι καθιερωμένος).
Η απάντηση είναι με διαφορετικούς τρόπους. Πρώτα επιλέγεται ο αρχηγός και μετά ο υπαρχηγός. Για τον αρχηγό έχουμε 10 επιλογές. Αφού επιλεγεί αυτός, έστω ο , στη θέση του υπαρχηγού μπορούμε να επιλέξουμε οποιονδήποτε εκτός του , έχουμε δηλ. 9 επιλογές. Παρατηρήστε ότι οι δύο επιλογές δεν είναι ανεξάρτητες αφού η επιλογή του αρχηγού επηρεάζει το σύνολο των δυνατών επιλογών για υπαρχηγό, δεν επηρεάζει όμως το πλήθος των δυνατών υπαρχηγών. Είναι δηλ. οι δύο αυτές επιλογές ημι-ανεξάρτητες.
Υπόδειξη: Επιλέγετε την εικόνα των με τη σειρά. Έχοντας επιλέξει τις εικόνες των πόσες επιλογές έχετε για την εικόνα του ;
def permutations(s): """ Returns a list of all perumatations of the set (list) s. Each element of this list is a permutation of s (again, a list). The list s is assumed to be nonempty. """ n = len(s) if n==1: return [s] # One permutation only else: result = [] # we will return this variable for x in s: # list all permutations of s with first element x ss = s[:] # make a copy of s ss.remove(x) # now ss is the original list with x removed for l in permutations(ss): result.append([x] + l) # we add each of them to result return resultΜπορείτε π.χ. να καλέσετε τη συνάρτηση δίνοντας
print permutations(['a', 'b', 'c', 'd'])οπότε θα πάρετε το output
[['a', 'b', 'c', 'd'], ['a', 'b', 'd', 'c'], ['a', 'c', 'b', 'd'], ['a', 'c', 'd', 'b'], ['a', 'd', 'b', 'c'], ['a', 'd', 'c', 'b'], ['b', 'a', 'c', 'd'], ['b', 'a', 'd', 'c'], ['b', 'c', 'a', 'd'], ['b', 'c', 'd', 'a'], ['b', 'd', 'a', 'c'], ['b', 'd', 'c', 'a'], ['c', 'a', 'b', 'd'], ['c', 'a', 'd', 'b'], ['c', 'b', 'a', 'd'], ['c', 'b', 'd', 'a'], ['c', 'd', 'a', 'b'], ['c', 'd', 'b', 'a'], ['d', 'a', 'b', 'c'], ['d', 'a', 'c', 'b'], ['d', 'b', 'a', 'c'], ['d', 'b', 'c', 'a'], ['d', 'c', 'a', 'b'], ['d', 'c', 'b', 'a']]Το πρόγραμμα είναι αναδρομικό (recursive). Βεβαιωθείτε ότι καταλαβαίνετε πώς δουλεύει.
Γράψτε το πρόγραμμά σας συμπληρώνοντας τα κενά στον παρακάτω κώδικα:
def factorial(n):
# n should be >= 0
if n<0:
.............
else:
t=1
.............
return t
Έχοντας γράψει τη συνάρτησή σας μπορείτε να την ελέγξετε με την εντολή π.χ.
print factorial(5)
Υπόδειξη: Μπορείτε αν θέλετε να χρησιμοποιήσετε το πρόγραμμα της Άσκησης 3.22.
Υπόδειξη: Για το δεύτερο ερώτημα βρείτε πρώτα με πόσους τρόπους μπορούν να μπουν στη σειρά τα σύμβολα 1, 1', 3, 4, 5. Με ποια διαδικασία μπορείτε να πάρετε από αυτούς τους τρόπους όλους τους τρόπους διάταξης των 1, 1, 3, 4, 5;
Με πόσους τρόπους μπορείτε να διατάξετε τα ψηφία 1, 1, 1, 2, 2, 3, 4, 5;
Πόσα αν απαγορεύεται ένα μήνυμα να ξεκινάει ή να τελειώνει με κενό;
Το σύμβολο προφέρεται: ανά .
Παρατηρήστε τώρα ότι σε κάθε μη διατεταγμένη -άδα, σε κάθε δηλ. -μελές υποσύνολο του , αντιστοιχούν ακριβώς διατεταγμένες -άδες, μια και με τόσους τρόπους μπορούν να διαταχθούν τα στοιχεία ενός -μελούς συνόλου (Πόρισμα 3.1). Άρα, στον αριθμό κάθε -μελές υποσύνολο του έχει μετρηθεί ακριβώς φορές. Για να βρούμε συνεπώς το πλήθος των -μελών υποσυνόλων του αρκεί να διαιρέσουμε αυτό τον αριθμό με .
def binomial(n,k): if k<0: print "Error" return -1 else: t=1.0 for i in range(k): t = t*(n-i)/(k-i) return t print binomial(5,2)Βεβαιωθείτε ότι καταλαβαίνετε τον τρόπο λειτουργίας του και τρέξτε μερικά παραδείγματα. Παρατηρήστε ότι αν στη θέση του βάλουμε έναν οποιοδήποτε πραγματικό αριθμό το πρόγραμμα τρέχει κανονικά αλλά προκύπτει σφάλμα αν στη θέση του βάλουμε κάποιον αριθμό που δεν είναι φυσικός αριθμός.
Στην πραγματικότητα το πρόγραμμα αυτό υπολογίζει το πολυώνυμο
Γράψτε μια συνάρτηση σε python που δοθέντος ενός συνόλου (ως μια λίστα python)
να επιστρέφει μια λίστα με όλα τα διμελή υποσύνολα του συνόλου αυτού.
Δουλέψτε συμπληρώνοντας την παρακάτω ημιτελή συνάρτηση.
def subsets2(s):
n = len(s)
ss = []
if n <= 1:
return ss
else:
for i in range(n):
.......
return ss
Η κλήση
s = ['a', 'b', 'c', 'd']
print subsets2(s)
θα πρέπει να σας επιστρέφει
[['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'c'], ['b', 'd'], ['c', 'd']]
Για να μετρήσουμε τους τρόπους σκεφτόμαστε με ποια διαδικασία θα παράγουμε μονοσήμαντα ένα τέτοιο αποτέλεσμα. Παρατηρούμε ότι στη δεύτερη θέση χρησιμοποιούνται ακριβώς δύο ψηφία, ένα στο ένα ζεύγος και ένα για το άλλο. Αποφασίζουμε λοιπόν κάθε τετράδα τέτοιων αριθμών να τη γράφουμε ως εξής:
Τα αντικείμενα δηλ. που θέλουμε να μετρήσουμε είναι σε ένα προς ένα αντιστοιχία με τις εξάδες
Το τελικό αποτέλεσμα είναι λοιπόν
Για να απαντήσουμε βρίσκουμε μια διαδικασία παραγωγής του τυπικού αποτελέσματος. Αφού λοιπόν πρέπει τρία από αυτά τα χαρτιά να είναι σπαθιά ξεκινάμε διαλέγοντας πρώτα απ' όλα αυτά. Τα τρία αυτά φύλλα επιλέγονται χωρίς κανένα περιορισμό από τα 13 συνολικά σπαθιά της τράπουλας. Άρα οι δυνατότητες γι' αυτή την επιλογή είναι .
Στη συνέχεια επιλέγουμε τα υπόλοιπα τρία φύλλα που πρέπει απλά να μην είναι σπαθιά, επιλέγονται δηλ. από τα φύλλα που δεν είναι σπαθιά, δίνοντάς μας δυνατότητες.
Επειδή η πρώτη επιλογή (των σπαθιών) είναι ανεξάρτητη από τη δεύτερη το τελικό αποτέλεσμα είναι
Για να τονίσουμε το πόσο σημαντικές είναι αυτές οι δύο ιδιότητες και πόσο προσεκτικοί πρέπει να είμαστε σε αντίστοιχα μετρήματα, ας παραλλάξουμε λίγο το ερώτημα του Παραδείγματος 3.5. Ας ρωτήσουμε το ίδιο με μόνη διαφορά ότι τώρα δεν απαιτούμε ακριβώς τρία φύλλα να είναι σπαθιά αλλά τουλάχιστον τρία.
Ας βρούμε μια διαδικασία κατασκευής (σύνθετη επιλογή). Αφού όπωσδήποτε θέλουμε τρία σπαθιά ας ξεκινήσουμε επιλέγοντάς τα. Έχουμε πάλι δυνατότητες γι' αυτή την επιλογή. Στο δεύτερο στάδιο μένει απλά να επιλέξουμε άλλα τρία φύλλα από τα εναπομέναντα , αφού τώρα δε μας πειράζει να έχουμε επιπλέον σπαθιά. Στο δεύτερο στάδιο λοιπόν έχουμε δυνατότητες. Εφ' όσον τα δύο στάδια επιλογής είναι ημι-ανεξάρτητα (προηγουμένως ήταν ανεξάρτητα) μπορούμε και πάλι να πολλαπλασιάσουμε και παίρνουμε τελικό αποτέλεσμα
ΛΑΘΟΣ!
Και ο λόγος είναι ότι μπορούμε να έχουμε το ίδιο αποτέλεσμα ακόμη κι αν η σύνθετη επιλογή μας αλλάξει. Για παράδειγμα, η κατασκευή μας μπορεί στο πρώτο στάδιο να μας δώσει 1 , 2 , 3 και στο δεύτερο 4 , 1 και 2 . Μπορεί επίσης να μας δώσει στο πρώτο στάδιο 1 , 2 , 4 και στο δεύτερο να μας δώσει 3 , 1 και 2 . Η τελική εξάδα είναι στις δύο αυτές περιπτώσεις η ίδια. Άρα ο αριθμός που υπολογίσαμε προηγουμένως είναι αυστηρά (και μάλλον κατά πολύ) μεγαλύτερος της πραγματικότητας.
Πώς μπορούμε να διορθώσουμε τη μέθοδό μας; Μια απλή απάντηση είναι ότι μπορούμε να διαχωρίσουμε τις δυνατές εξάδες σε τέσσερεις κατηγορίες: αυτές που έχουν ακριβώς 3, ακριβώς 4, ακριβώς 5 ή ακριβώς 6 σπαθιά. Μπορούμε εύκολα να μετρήσουμε τις εξάδες κάθε κατηγορίας, ουσιαστικά με τη μέθοδο του Παραδείγματος 3.5, και στο τέλος να προσθέσουμε αυτά τα τέσσερα νούμερα. Έτσι το αποτέλεσμα είναι
Ας σκεφτούμε λίγο πώς υπολογίζει κανείς το ανάπτυγμα ενός γινομένου, για απλότητα του που έχει δύο μόνο παράγοντες και όχι 10 όπως αυτό που ζητάμε. Το βρίσκουμε παίρνοντας κάθε προσθετέο του πρώτου αθροίσματος πολλαπλασιασμένο με κάθε προσθετέο του δεύτερου, και αθροίζουμε τα αποτελέσματα. Αν λοιπόν ρωτήσουμε ποιός είναι ο συντελεστής του στο ανάπτυγμα, είναι σα να ρωτάμε με πόσους τρόπους μπορεί να εμφανιστεί το γινόμενο κάνοντας το ανάπτυγμα όπως παραπάνω.
Λόγω αντιμεταθετικότητας του πολλαπλασιασμού αυτό μπορεί να εμφανιστεί είτε ως είτε ως . Το εμφανίζεται ακριβώς μία φορά, όταν συνδυάζουμε στο ανάπτυγμα το από την πρώτη παρένθεση με το από τη δεύτερη. Δεν υπάρχει άλλος τρόπος. Ομοίως μία φορά εμφανίζεται και το όταν συνδυάζεται το από την πρώτη παρένθεση με το από τη δεύτερη. Άρα ο συντελεστής του στο ανάπτυγμα είναι . Ομοίως τα και μπορούν το καθένα να προκύψουν με ένα μόνο τρόπο. Για το , π.χ., πρέπει να επιλεγεί το και από την πρώτη και από τη δεύτερη παρένθεση, ομοίως και για το . Επιβεβαιώνεται έτσι ο γνωστός μας τύπος .
Αν ρωτήσουμε για το συντελεστή του στο ανάπτυγμα του είναι σα να ρωτάμε με πόσους τρόπους μπορούμε να συνδυάσουμε ένα με δύο από τις τρείς παρενθέσεις που υπάρχουν στο γινόμενο. Αυτό μπορεί να γίνει με ακριβώς τρείς τρόπους μια και αρκεί να πούμε από ποια παρένθεση επιλέγουμε να πάρουμε το . Αυτό προσδιορίζει ότι από τις άλλες δύο παίρνουμε από ένα .
Επανερχόμαστε τώρα στο αρχικό μας ερώτημα και ρωτάμε για το συντελεστή του στο ανάπτυγμα του . Στο ανάπτυγμα αυτό οι προσθετέοι προκύπτουν με επιλογή, ο καθένας, ενός ή ενός από κάθε μία από τις 10 παρενθέσεις. Το λοιπόν μπορεί να προκύψει με τόσους τρόπους όσοι είναι οι τρόποι να επιλέξουμε τις 4 παρενθέσεις, από τις οποίες θα πάρουμε τα . Άρα το αποτέλεσμα είναι
Υπόδειξη: Για το δεύτερο ερώτημα, επιλέξτε το προεδρείο επιλέγοντας πρώτα τον πρόεδρο, μετά τον αντιπρόεδρο και, τέλος, τα τρία μέλη μαζί.
Mihalis Kolountzakis 2015-11-28