Optimize the permutation search loop (can't use itertools) which is very slow. Any suggestions?

Edit: I misunderstood the original problem, here the solution presented addresses the following problem:

Given 4 groups with 3 different cards with a different score for each card, we draw cards until we have selected 3 cards from the same group. What is the expected result (the sum of the points of the selected cards) at the end of the game.

I leave the solution as it is because it was so nice to work with after so many years of theory and less, but I just can't delete it :)

See my other answer for handling the original problem.

There are two possibilities to improve performance: speeding up your code (and before starting that, you need to profile to find out which part of the program needs to be optimized, otherwise time is wasted optimizing things that are not taken into account) or improving the algorithm. I suggest doing the second.

Ok, this problem seems to be more complex than the first site. Let's start with some observations.

All you need to know is the expected number of selected cards at the end of the game:

If Pi

is the probability that a card is i

chosen somewhere during the game, then we are looking for the expected value of the score E(Score)=P1*W1+P2*W2+...Pn*Wn

. However, if we look at the cards in a group, we can state that due to symmetry, the probabilities for the cards in that group are the same, for example. P1=P2=P3=:Pgrand

in your case. Thus, our expectation can be calculated:

E(Score)=3*Pgrand*(W1+W2+W3)/3+...+3*Pbonus*(W10+W11+W12)/3

      

        
        
        
      

    

Let's name averageWgrand:=(W1+W2+W3)/3

and keep in mind that E(#grand)=3*Pgrand

- the expected number of selected Grand Cards at the end of the game. In this case, our formula becomes:

E(Score)=E(#grand)*averageWgrand+...+E(#bonus)*averageWbonus

      

        
        
        
      

    

In your example, we can go even further: the number of cards in each group is, therefore, due to the symmetry we may require: E(#grand)=E(#minor)=E(#major)=E(#grand)=:(E#group)

. For simplicity, in what follows, we will consider only this particular case (but the presented solution can be extended to the general case). This leads to the following simplification:

E(Score)=4*E(#group)(averageWgrand+...+averageWbonus)/4

      

        
        
        
      

    

Let's name averageW:=(averageWgrand+...+averageWbonus)/4

and note that E(#cards)=4*E(#grand)

- the expected number of collected cards at the end of the game.

Thus E(Score)=E(#cards)*averageW

, therefore, our task is reduced to calculating the expected value of the number of cards at the end of the game:

 E(#cards)=P(1)*1+P(2)*2+...P(n)*n

      

        
        
        
      

    

where P(i)

denotes the probability that the game ends with accurate cards i

. Probabilities P(1)

, P(2)

and P(k)

, k>9

it's easy to see - they are 0

.

Calculating the probability of the game ending using the i

selected cards - P(i)

:

Let's play a slightly different game: we choose exactly the i

cards and win if and only if:

• There is exactly one group with three chosen cards. We call this group full_group
  
  .
• The last selected (i-th) card was from full_group
  
  .

It is easy to see that the probability of winning this game P(win)

is exactly the probability we are looking for P(i)

. Once again we can use symmetry because all groups are equal ( P(win, full=grand)

meaning the probability that we are what and what full_group=grand

):

 P(win)=P(win, grand)+P(win, minor)+P(win, major)+P(win, bonus)
       =4*P(win, grand)

      

        
        
        
      

    

P(win, grand)

- the probability that:

• after selecting the cards, the i-1
  
  number of selected grand cards is 2, that is, `# grand = 2 'and
• after choosing cards i-1
  
  , for each group the number of selected cards is less than 3 and
• we choose the grand card in the last round. Given the first two constraints, this (conditional) probability is 1/(n-i+1)
  
  (there are cards n-i+1
  
  on the left, and only one of them is "right").

From the urn problem we know the probability for

P(#grand=u, #minor=x, #major=y, #bonus=z) = binom(3,u)*binom(3,x)*binom(3,y)*binom(3,z)/binom(12, u+x+y+z)

      

        
        
        
      

    

with binom(n,k)=n!/k!/(n-k)!

. Thus, P(win, grand)

it can be calculated as:

P(win, grand) = 1/(n-i+1)*sum P(#grand=2, #minor=x, #major=y, #bonus=z)
               where x<=2, y<=2, z<=2 and 2+x+y+z=i-1

      

        
        
        
      

    

And now the code:

import math

def binom(n,k):
  return math.factorial(n)//math.factorial(k)//math.factorial(n-k)

#expected number of cards:

n=12 #there are 12 cards
probs=[0]*n
for minor in xrange(3):
  for major in xrange(3):
     for bonus in xrange(3):
         i = 3 + minor +major +bonus 
         P_urn = binom(3,2)*binom(3,minor)*binom(3,major)*binom(3,bonus)/float(binom(n, n-i+1))
         P_right_last_card = 1.0/(n-i+1)
         probs[i]+=4*P_urn*P_right_last_card #factor 4 from symmetry


print "Expected number of cards:", sum((prob*card_cnt for card_cnt, prob in enumerate(probs)))

      

        
        
        
      

    

As a result, I get 6.94285714286

as the expected number of cards at the end of the game. And very quickly - almost instantly. Not sure if this is correct ...

Output:

Obviously, if you like to handle the more general case (more groups, number maps in another group), you should extend the code (recursion, memoization binom

) and theory.

But the most important part: With this approach, you (almost) don't care what order the cards were chosen in, and therefore the number of conditions you have to check is reduced at (k-1)!

, where the k

maximum number of cards is at the end of the game. In your example k=9

and therefore the approach is faster with a factor 40000

(I am not even considering acceleration from exploited symmetry, because that might not be possible in general).