Ζάρια

[k33theod]

Γειά και πάλι

 

Ένα άλλο πρόβλημα με πιθανότητες πάλι με ζάρια που το παλεύω 2 μέρες

 

Έχουμε ένα αριθμό ζαριών που έχουν ένα αριθμό πλευρών και θέλουμε να βρούμε την πιθανότητα να φέρουν ένα συκεκριμένο άθροισμα

 

παράδειγμα probability(1,6,1) =1/6 δηλαδή 1 ζάρι με έξι έδρες και θέλω άθροισμα 1

                    probability(2,10,3) =2/100   2 ζάρια με 10 έδρες και άθροισμα 3 κλπ

 

Εκτός από brute force βρήκα και έναν άλλο τρόπο που περιγράφεται εδώ  https://wizardofodds.com/gambling/dice/2/  

στη υλοποίηση του όμως στα μεγάλα νούμερα είναι εξαιρετικά αργό (To έκανα με αναδρομική συνάρτηση)

για το probability(10,10,50) 5,5 λεπτά

 

Ξέρει κανείς κανένα ποιό εύκολο/γρήγορο τρόπο

 

βλέποντας τα νούμερα έχω την εντύπωση πως υπάρχει κάποια άλλη πιο (απλή) μαθηματική σχέση 

 

[Lanike71]

Στο φτερό απαντώ :

 

Το λινκ που διάβασα λέει ότι κάθε επόμενο ζάρι και πιθανότητες, μπορούν να υπολογιστούν από τα προηγούμενα. Θυμίζει πρόβλημα Fibo και δυναμικό προγραμματισμό (χωρίς να είμαι σίγουρος).

[k33theod]

Στο φτερό απαντώ :

 

Το λινκ που διάβασα λέει ότι κάθε επόμενο ζάρι και πιθανότητες, μπορούν να υπολογιστούν από τα προηγούμενα. Θυμίζει πρόβλημα Fibo και δυναμικό προγραμματισμό (χωρίς να είμαι σίγουρος).

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

Σκέφτομαι ότι ίσως υπάρχει και άλλος τρόπος 

[paparovic]

Χρειάζεσαι το πλήθος των αθροισμάτων που δίνουν το επιθυμητό άθροισμα. Για παράδειγμα, στο (2, β, 6), υπάρχουν τα: 1+5, 2+4, 3+3 -> 3 συνδυασμοί. Στο (3,β,6), έχεις το 1+1+4, 1+2+3, 2+2+2. Στο (4,β,6) έχεις 1+1+1+3, 1+1+2+2. Στο (5, β, 6) έχεις 1+1+1+1+2. 

 

Ο συμβολισμός για τα παραπάνω είναι P(n,k). Δλδ. P(6,2) = 3, P(6,3) = 2 κτλ.

 

Ισχύει P(n,k) = P(n-1,k-1) + P(n-k,k). Έχεις λοιπόν μια αναδρομική συνάρτηση.

 

Π.χ. P(6,3) = P(5,2) + P(3,3) = P(4,1) + P(3,2) + P(3,3) = P(4,1) + P(2,1) + P(1,2) + P(3,3) = 1 + 1 + 0 + 1 = 3

 

Αν (α, β, γ) η αρχική σου τριάδα, το αποτέλεσμα είναι  P(γ, α) * α! / b^a

 

Άρα, το πρόβλημα είναι μια efficient υλοποίηση της αναδρομικής σχέσης αυτής. Σε καμία περίπτωση όμως δεν θα πάρει 5,5 λεπτά για το (10,10,50)

[k33theod]

Ο κώδικας που έχω γράψει σε python είναι αυτός

def probability(a, b, c):
  denominator=b**a # Ο παρονομαστής είναι στανταρ
  nom=nominator (a,b,c) #ο αριθμητής
  return round(nom/denominator,4)

#Τον αριθμητή τον υπολογίζω με βάση τη θεωρία https://wizardofodds.com/gambling/dice/2/
#που για την δική μου περίπτωση μεταφράζω σε
#nominator (a,b,c)= nominator(a-1,b,c-1)+nominator(a-1,b,c-2)+...+nominator(a-1,b,c-
#και το κάνω κώδικα 

def nominator (a,b,c):
  if c<a:
    return 0
  if a==1:
    return 1
  else:
    suma=0
    i=1
    while i<=b:
      suma+=(nominator(a-1,b,c-i))
      i+=1
    return suma

Στα μικρά νούμερα πάει καλά γρήγορα σχετικά

def count_time():
	start=time.time()
	nominator(10,10,50)
	endt=time.time()
	return endt-start
>>> count_time()
#και ακόμα περιμένω μόλις δώσει τιμή θα την γράψω

868.9112505912781
14 λεπτά !!!!

Τα αποτελέσματα που παίρνω είναι σωστά η αναδρομή είναι το θέμα καλώ τη συνάρτηση 10 φορές που η κάθε μια την καλεί 10 φορές που την καλεί 10 φορές και έχουμε να περιμένουμε 10**10 εκτελέσεις δηλαδή 10000000000

[paparovic]

Φώναξε τον defacer στο νήμα να σου κοπανήσει μερικές ανάποδες που πήγες κι έβαλες αυτό το  while i<=b: σε αναδρομική συνάρτηση. 

[k33theod]

Φώναξε τον defacer στο νήμα να σου κοπανήσει μερικές ανάποδες που πήγες κι έβαλες αυτό το  while i<=b: σε αναδρομική συνάρτηση. 

Αυτό πρέπει να το βάλω γιατί κάθε φορά πρέπει να την καλώ b φορές 

nominator (a,b,c)= nominator(a-1,b,c-1)+nominator(a-1,b,c-2)+...+nominator(a-1,b,c-

και η κάθε μια από αυτές σκέψου ότι το κάνει ξανά 

Απλά τελικά νομίζω ότι η αναδρομή δεν είναι η λύση και ότι εκτός από τον αλγόριθμο του https://wizardofodds.com/gambling/dice/2/

υπάρχει άλλος πιο γρήγορος

 

Όχι η brute force τα 8gb ram μου τα τρώει σε 5 sec

[Lanike71]

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

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

Δες πώς λύνεται το πρόβλημα Φιμπονάτσι.

[albNik]

Εχεις π.χ. 100 ζαρια και θες αθροισμα 500.

Αν φερεις 1 θες 99 ζαρια με αθροισμα 499

Αν φερεις 2 θες 99 ζαρια με αθροισμα 498

 

Κρατας καπου τα ήδη υπολογισμένα αποτελέσματα σε ενα πινακα 100X500 (αυτο λεγεται memoization)

 

ways(100, 500)=ways(99, 499)+ways(99, 498)+ways(99, 497)+...

 

Η πιθανότητα είναι ο λόγος ways(100, 500)/(γινομενο πλευρών καθε ζαριου) π.χ 6^100 

[k33theod]

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

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

Δες πώς λύνεται το πρόβλημα Φιμπονάτσι.

Κατάλαβα περίπου τι λες, ίδιο αλγόριθμο αλλά όχι συναρτήσεις και κράτημα των τιμών σε κάποιες μεταβλητές η πίνακα

 

Θα το προσπαθήσω άλλωστε δεν έχω άλλες ιδέες

Εχεις π.χ. 100 ζαρια και θες αθροισμα 500.

Αν φερεις 1 θες 99 ζαρια με αθροισμα 499

Αν φερεις 2 θες 99 ζαρια με αθροισμα 498

 

Κρατας καπου τα ήδη υπολογισμένα αποτελέσματα σε ενα πινακα 100X500 (αυτο λεγεται memoization)

 

ways(100, 500)=ways(99, 499)+ways(99, 498)+ways(99, 497)+...

 

Η πιθανότητα είναι ο λόγος ways(100, 500)/(γινομενο πλευρών καθε ζαριου) π.χ 6^100 

δεν το καταλάβα 

λείπει και η παράμετρος των τιμών ανά ζάρι η οποία παίζει σημαντικό ρόλο 

[albNik]

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

{1,2,2 ,2 ,7} {1,1,5}, {4,6,7,8,9}, {2,2,2,2} {1,2,3,4,5}  

δλδ 5x3x5x4x5 περιπτώσεις

ways(5 20)=ways(4 19)+ 3*ways(4 18) +ways(4 13)

Βασικα ειναι ο συντελεστης του x^20 του

(x+3x²+x⁷)(2x+x⁵​)(x⁴+x⁶+x⁷⁺x⁸+x⁹)... 

 

Αν ολα τα ζαρια ειναι ιδια με Ν πλευρες (αριθμους1 εως Ν) απλοποιείται ο παραπάνω τυπος (μπορει να υπολογιστει με μολύβι και χαρτι) 

.

[k33theod]

Τελικά το έκανα με τον τρόπο που μου είπε ο Lanike71

>>> def count_time():
	start=time.time()
	a=probability(10,10,50)
	endt=time.time()
	return endt-start,a

>>> count_time()
(0.0, 0.0375)
>>>  

Χρόνος για το ίδιο αποτέλεσμα που το άλλο έκανε 1000 δεύτερα 0.0

και για το 100,100,3000 1,5 sec

Δεν το πιστεύω

[pmav99]

@k33theod

Για να μην το κάνεις χειροκίνητα, δες για memoization

https://wiki.python.org/moin/PythonDecoratorLibrary#Memoize

https://docs.python.org/3/library/functools.html#functools.lru_cache

 

edit

όσον αφορά το performance:

 

1. τα function calls στην python είναι ακριβά και τα exceptions πανάκριβα.

2. H python δεν κάνει tail recursion optimization για αυτό και η αναδρομή θα είναι πάντα αργή: http://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion