优化非常慢的排列搜索循环（不能使用 itertools）。有什么建议么？
Optimize permutations search loop (can't use itertools) that is extremely slow. Any suggestions?
这是一个游戏，您有 12 张牌，您可以选择您，直到您从同一组中选出 3 张。我试图找到选择每个组的概率。我创建的脚本有效，但速度非常慢。我的同事在 R 中创建了一个没有函数的类似脚本，他的脚本花费的时间是我的 1/100。我只是想弄清楚为什么。任何想法将不胜感激。
from collections import Counter
import pandas as pd
from datetime import datetime
weight = pd.read_excel('V01Weights.xlsx')
权重如下所示：
Symb Weight
Grand 170000
Grand 170000
Grand 105
Major 170000
Major 170000
Major 215
Minor 150000
Minor 150000
Minor 12000
Bonus 105000
Bonus 105000
Bonus 105000
Max Picks代表不同的总数"cards"。 Total Picks 表示用户选择的最大数量。这是因为在 8 次选择之后，你保证每种类型都有 2 个，所以在第 9 个选择时，你保证有 3 个匹配。
TotalPicks = 9
MaxPicks = 12
这应该被命名为 PickedProbabilities。
Picks = {0:0,1:0,2:0,3:0}
这是我的 timeit 的简单版本 class 因为我不喜欢 timeit class
def Time_It(function):
start =datetime.now()
x = function()
finish = datetime.now()
TotalTime = finish - start
Minutes = int(TotalTime.seconds/60)
Seconds = TotalTime.seconds % 60
print('It took ' + str(Minutes) + ' minutes and ' + str(Seconds) + ' seconds')
return(x)
给定 x（我按顺序选择）我找到了概率。这些选择是在没有更换的情况下完成的
def Get_Prob(x,weight):
prob = 1
weights = weight.iloc[:,1]
for index in x:
num = weights[index]
denom = sum(weights)
prob *= num/denom
weights.drop(index, inplace = True)
# print(weights)
return(prob)
这用于确定我的循环中是否存在重复项，因为这是不允许的
def Is_Allowed(x):
return(len(x) == len(set(x)))
这决定了目前所有出现的牌是否都赢了。
def Is_Win(x):
global Picks
WinTypes = [[0,1,2],[3,4,5],[6,7,8],[9,10,11]]
IsWin = False
for index,item in enumerate(WinTypes):
# print(index)
if set(item).issubset(set(x)):
IsWin = True
Picks[index] += Get_Prob(x,weight)
# print(Picks[index])
print(sum(Picks.values()))
break
return(IsWin)
这是我循环遍历所有卡片的主要功能。我试图使用递归来做到这一点，但我最终放弃了。我不能使用 itertools 创建所有的排列，因为例如 [0,1,2,3,4] 将由 itertools 创建，但这是不可能的，因为一旦你获得 3 个匹配，游戏就结束了。
def Cycle():
for a in range(MaxPicks):
x = [a]
for b in range(MaxPicks):
x = [a,b]
if Is_Allowed(x):
for c in range(MaxPicks):
x = [a,b,c]
if Is_Allowed(x):
if Is_Win(x):
# print(x)
continue
for d in range(MaxPicks):
x = [a,b,c,d]
if Is_Allowed(x):
if Is_Win(x):
# print(x)
continue
for e in range(MaxPicks):
x = [a,b,c,d,e]
if Is_Allowed(x):
if Is_Win(x):
continue
for f in range(MaxPicks):
x = [a,b,c,d,e,f]
if Is_Allowed(x):
if Is_Win(x):
continue
for g in range(MaxPicks):
x = [a,b,c,d,e,f,g]
if Is_Allowed(x):
if Is_Win(x):
continue
for h in range(MaxPicks):
x = [a,b,c,d,e,f,g,h]
if Is_Allowed(x):
if Is_Win(x):
continue
for i in range(MaxPicks):
if Is_Allowed(x):
if Is_Win(x):
continue
调用主函数
x = Time_It(Cycle)
print(x)
将概率写入文本文件
with open('result.txt','w') as file:
# file.write(pickle.dumps(x))
for item in x:
file.write(str(item) + ',' + str(x[item]) + '\n')
My coworker created a similar script in R without the functions and his script takes 1/100th the time that mine takes.
两个简单的优化：
1) 像 Is_Allowed() 这样的内联函数调用，因为 Python 有很多函数调用开销（例如创建新的堆栈框架和参数元组）。
2) 运行 using pypy 中的代码非常擅长优化像这样的函数。
编辑：我误解了原来的问题，这里提出的解决方案是针对以下问题：
Given 4 groups with 3 different cards with a different score for every card, we pick up cards as long as we don't have picked 3 cards from the same group. What is the expected score(sum of scores of picked cards) in the end of the game.
我保留解决方案原样，因为在这么多年没有概率论的情况下解决这个问题真是太高兴了，我就是不能删除它:)
原问题的处理见我的其他回答
有两种提高性能的可能性：使代码更快（在开始之前，应该进行概要分析以了解应该优化程序的哪一部分，否则时间会花在优化那些不需要的东西上t 计数）或改进算法。我建议做第二个。
好的，这个问题似乎比第一个站点更复杂。让我们从一些观察开始。
你只需要知道游戏结束时预计抽到的牌数：
如果Pi是牌i在游戏中某处被抽到的概率，那么我们就是在寻找得分的期望值E(Score)=P1*W1+P2*W2+...Pn*Wn。然而，如果我们看一组卡片，我们可以说由于对称性，这组卡片的概率是相同的，例如P1=P2=P3=:Pgrand 你的情况。因此我们的期望值可以计算为：
E(Score)=3*Pgrand*(W1+W2+W3)/3+...+3*Pbonus*(W10+W11+W12)/3
我们调用 averageWgrand:=(W1+W2+W3)/3 并注意 E(#grand)=3*Pgrand - 游戏结束时所选择的大牌的预期数量。这样我们的公式就变成了：
E(Score)=E(#grand)*averageWgrand+...+E(#bonus)*averageWbonus
在您的示例中，我们可以走得更远：每组中的卡片数量相等，因此由于对称性，我们可以声明：E(#grand)=E(#minor)=E(#major)=E(#grand)=:(E#group)。为了简单起见，下面我们只考虑这种特殊情况（但概述的解决方案也可以扩展到一般情况）。这导致以下简化：
E(Score)=4*E(#group)(averageWgrand+...+averageWbonus)/4
我们调用 averageW:=(averageWgrand+...+averageWbonus)/4 并注意 E(#cards)=4*E(#grand) 是游戏结束时预期的拾牌数。
这样，E(Score)=E(#cards)*averageW，所以我们的任务就简化为计算游戏结束时牌数的期望值：
E(#cards)=P(1)*1+P(2)*2+...P(n)*n
其中 P(i) 表示游戏以恰好 i 张牌结束的概率。概率 P(1)、P(2) 和 P(k)、k>9 很容易看出 - 它们是 0。
计算用i张牌结束游戏的概率-P(i):
让我们来玩一个稍微不同的游戏：我们恰好挑选 i 张牌并且当且仅当：
- 正好有一组选了3张牌。我们称这个组为
full_group.
- 最后选择的第 (i) 张牌来自
full_group。
很容易看出，赢得这场比赛的概率P(win)正是我们要找的概率-P(i)。我们可以再次使用对称性，因为所有组都是相等的（P(win, full=grand) 表示我们和 full_group=grand 是什么的概率）：
P(win)=P(win, grand)+P(win, minor)+P(win, major)+P(win, bonus)
=4*P(win, grand)
P(win, grand) 是以下概率：
- 在选择
i-1 牌后，选择的大牌数量为 2，即 `#grand=2' 和
- 抽取
i-1张牌后，每组抽取的牌数少于3张且
- 我们在最后一轮选了一张大牌。鉴于前两个约束条件成立，这个（条件）概率是
1/(n-i+1)（还剩下 n-i+1 张牌，其中只有一张是 "right"）。
从骨灰盒问题我们知道
的概率
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)
和 binom(n,k)=n!/k!/(n-k)!。因此 P(win, grand) 可以计算为：
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
现在代码：
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)))
结果我得到 6.94285714286 作为游戏结束时的预期牌数。而且非常快——几乎是瞬间。不确定是否正确...
结论：
显然，如果你想处理更一般的情况（更多的组，组中的数字卡不同）你必须扩展代码（递归，binom 的记忆）和理论。
但最关键的部分：使用这种方法，您（几乎）不关心卡片的挑选顺序 - 因此您必须检查的状态数量减少了 (k-1)!其中 k 是游戏结束时可能出现的最大牌数。在您的示例 k=9 中，因此该方法更快 40000 （我什至不考虑利用对称性的加速，因为在一般情况下这可能是不可能的）。
好的，这次我希望我能解决你的问题:)
为了加速您的程序 算法:
需要两个见解（我想您已经有了，只是为了完整起见）
- 序列
(card_1, card_2) 和 (card_2, card_1) 的概率不相等，所以我们不能使用骨灰盒问题的结果，看来我们需要尝试所有排列。
- 然而，鉴于我们到目前为止挑选的一组牌，我们实际上并不需要他们挑选顺序的信息 - 对于未来的游戏过程来说都是一样的。所以使用动态规划并计算游戏过程中要遍历的每个子集的概率就足够了（因此我们需要检查
2^N 而不是 N! 状态）。
对于一组已选取的牌 set 在下一回合中选取牌 i 的概率是：
norm:=sum Wi for i in set
P(i|set)=Wi/norm if i not in set else 0.0
计算P(set)的递归-在游戏中出现一组被选中的牌的概率是：
set_without_i:=set/{i}
P(set)=sum P(set_without_i)*P(i|set_without_i) for i in set
然而，这应该只对游戏尚未结束的 set_without_i 进行，即没有组有 3 张牌被选中。
这可以通过递归+记忆的方式来完成，或者像我的版本一样，通过使用自下而上的动态规划来完成。它还使用整数的二进制表示来表示集合和（最重要的部分！）returns 结果几乎立即 [('Grand', 0.0014104762718021384), ('Major', 0.0028878988709489244), ('Minor', 0.15321793072867956), ('Bonus', 0.84248369412856905)]:
#calculates probability to end the game with 3 cards of a type
N=12
#set representation int->list
def decode_set(encoded):
decoded=[False]*N
for i in xrange(N):
if encoded&(1<<i):
decoded[i]=True
return decoded
weights = [170000, 170000, 105, 170000, 170000, 215, 150000, 150000, 12000, 105000, 105000, 105000]
def get_probs(decoded_set):
denom=float(sum((w for w,is_taken in zip(weights, decoded_set) if not is_taken)))
return [w/denom if not is_taken else 0.0 for w,is_taken in zip(weights, decoded_set)]
def end_group(encoded_set):
for i in xrange(4):
whole_group = 7<<(3*i) #7=..000111, 56=00111000 and so on
if (encoded_set & whole_group)==whole_group:
return i
return None
#MAIN: dynamic program:
MAX=(1<<N)#max possible set is 1<<N-1
probs=[0.0]*MAX
#we always start with the empty set:
probs[0]=1.0
#building bottom-up
for current_set in xrange(MAX):
if end_group(current_set) is None: #game not ended yet!
decoded_set=decode_set(current_set)
trans_probs=get_probs(decoded_set)
for i, is_set in enumerate(decoded_set):
if not is_set:
new_set=current_set | (1<<i)
probs[new_set]+=probs[current_set]*trans_probs[i]
#filtering wins:
group_probs=[0.0]*4
for current_set in xrange(MAX):
group_won=end_group(current_set)
if group_won is not None:
group_probs[group_won]+=probs[current_set]
print zip(["Grand", "Major", "Minor", "Bonus"], group_probs)
代码中使用的"tricks"的一些解释：
一个非常标准的技巧是使用整数的二进制表示来编码一个集合。假设我们有对象 [a,b,c]，所以我们可以将集合 {b,c} 表示为 110，这意味着 a（列表中的第一个对应于 0-最低位）- 不在集合中，b(1) 在集合中，c(1) 在集合中。但是，110 读取为整数时它是 6。
current_set - for 循环模拟了游戏，在玩的时候最好理解。让我们玩两张牌 [a,b]，权重 [2,1].
我们用一个空集开始游戏，0 作为整数，所以概率向量（给定集，它的二进制表示和映射到概率的整数）：
probs=[{}=00=0->1.0, 01={a}=1->0.0, {b}=10=2->0.0, {a,b}=11=3->0.0]
我们处理current_set=0，有两种可能66%拿卡a和33%拿卡b，所以处理后的概率变成：
probs=[{}=00=0->1.0, 01={a}=1->0.66, {b}=10=2->0.33, {a,b}=11=3->0.0]
现在我们处理 current_set=1={a} 唯一的可能性是取 b 所以我们将以集合 {a,b} 结束。所以我们需要通过我们的公式更新它的 (3={a,b}) 概率，我们得到：
probs=[{}=00=0->1.0, 01={a}=1->0.66, {b}=10=2->0.33, {a,b}=11=3->0.66]
下一步我们处理2，给定集合{b}唯一的可能就是选牌a，所以集合{a,b}的概率需要再次更新
probs=[{}=00=0->1.0, 01={a}=1->0.66, {b}=10=2->0.33, {a,b}=11=3->1.0]
我们可以通过两条不同的路径到达 {a,b} - 这可以在我们的算法中看到。在我们游戏中的某个时刻通过集合 {a,b} 的概率显然是 1.0。
另一件重要的事情：在我们处理这个集合之前，所有通向 {a,b} 的路径都已经处理好了（这将是下一步）。
这是一个游戏，您有 12 张牌，您可以选择您，直到您从同一组中选出 3 张。我试图找到选择每个组的概率。我创建的脚本有效，但速度非常慢。我的同事在 R 中创建了一个没有函数的类似脚本，他的脚本花费的时间是我的 1/100。我只是想弄清楚为什么。任何想法将不胜感激。
from collections import Counter
import pandas as pd
from datetime import datetime
weight = pd.read_excel('V01Weights.xlsx')
权重如下所示：
Symb Weight
Grand 170000
Grand 170000
Grand 105
Major 170000
Major 170000
Major 215
Minor 150000
Minor 150000
Minor 12000
Bonus 105000
Bonus 105000
Bonus 105000
Max Picks代表不同的总数"cards"。 Total Picks 表示用户选择的最大数量。这是因为在 8 次选择之后，你保证每种类型都有 2 个，所以在第 9 个选择时，你保证有 3 个匹配。
TotalPicks = 9
MaxPicks = 12
这应该被命名为 PickedProbabilities。
Picks = {0:0,1:0,2:0,3:0}
这是我的 timeit 的简单版本 class 因为我不喜欢 timeit class
def Time_It(function):
start =datetime.now()
x = function()
finish = datetime.now()
TotalTime = finish - start
Minutes = int(TotalTime.seconds/60)
Seconds = TotalTime.seconds % 60
print('It took ' + str(Minutes) + ' minutes and ' + str(Seconds) + ' seconds')
return(x)
给定 x（我按顺序选择）我找到了概率。这些选择是在没有更换的情况下完成的
def Get_Prob(x,weight):
prob = 1
weights = weight.iloc[:,1]
for index in x:
num = weights[index]
denom = sum(weights)
prob *= num/denom
weights.drop(index, inplace = True)
# print(weights)
return(prob)
这用于确定我的循环中是否存在重复项，因为这是不允许的
def Is_Allowed(x):
return(len(x) == len(set(x)))
这决定了目前所有出现的牌是否都赢了。
def Is_Win(x):
global Picks
WinTypes = [[0,1,2],[3,4,5],[6,7,8],[9,10,11]]
IsWin = False
for index,item in enumerate(WinTypes):
# print(index)
if set(item).issubset(set(x)):
IsWin = True
Picks[index] += Get_Prob(x,weight)
# print(Picks[index])
print(sum(Picks.values()))
break
return(IsWin)
这是我循环遍历所有卡片的主要功能。我试图使用递归来做到这一点，但我最终放弃了。我不能使用 itertools 创建所有的排列，因为例如 [0,1,2,3,4] 将由 itertools 创建，但这是不可能的，因为一旦你获得 3 个匹配，游戏就结束了。
def Cycle():
for a in range(MaxPicks):
x = [a]
for b in range(MaxPicks):
x = [a,b]
if Is_Allowed(x):
for c in range(MaxPicks):
x = [a,b,c]
if Is_Allowed(x):
if Is_Win(x):
# print(x)
continue
for d in range(MaxPicks):
x = [a,b,c,d]
if Is_Allowed(x):
if Is_Win(x):
# print(x)
continue
for e in range(MaxPicks):
x = [a,b,c,d,e]
if Is_Allowed(x):
if Is_Win(x):
continue
for f in range(MaxPicks):
x = [a,b,c,d,e,f]
if Is_Allowed(x):
if Is_Win(x):
continue
for g in range(MaxPicks):
x = [a,b,c,d,e,f,g]
if Is_Allowed(x):
if Is_Win(x):
continue
for h in range(MaxPicks):
x = [a,b,c,d,e,f,g,h]
if Is_Allowed(x):
if Is_Win(x):
continue
for i in range(MaxPicks):
if Is_Allowed(x):
if Is_Win(x):
continue
调用主函数
x = Time_It(Cycle)
print(x)
将概率写入文本文件
with open('result.txt','w') as file:
# file.write(pickle.dumps(x))
for item in x:
file.write(str(item) + ',' + str(x[item]) + '\n')
My coworker created a similar script in R without the functions and his script takes 1/100th the time that mine takes.
两个简单的优化：
1) 像 Is_Allowed() 这样的内联函数调用，因为 Python 有很多函数调用开销（例如创建新的堆栈框架和参数元组）。
2) 运行 using pypy 中的代码非常擅长优化像这样的函数。
编辑：我误解了原来的问题，这里提出的解决方案是针对以下问题：
Given 4 groups with 3 different cards with a different score for every card, we pick up cards as long as we don't have picked 3 cards from the same group. What is the expected score(sum of scores of picked cards) in the end of the game.
我保留解决方案原样，因为在这么多年没有概率论的情况下解决这个问题真是太高兴了，我就是不能删除它:)
原问题的处理见我的其他回答
有两种提高性能的可能性：使代码更快（在开始之前，应该进行概要分析以了解应该优化程序的哪一部分，否则时间会花在优化那些不需要的东西上t 计数）或改进算法。我建议做第二个。
好的，这个问题似乎比第一个站点更复杂。让我们从一些观察开始。
你只需要知道游戏结束时预计抽到的牌数：
如果Pi是牌i在游戏中某处被抽到的概率，那么我们就是在寻找得分的期望值E(Score)=P1*W1+P2*W2+...Pn*Wn。然而，如果我们看一组卡片，我们可以说由于对称性，这组卡片的概率是相同的，例如P1=P2=P3=:Pgrand 你的情况。因此我们的期望值可以计算为：
E(Score)=3*Pgrand*(W1+W2+W3)/3+...+3*Pbonus*(W10+W11+W12)/3
我们调用 averageWgrand:=(W1+W2+W3)/3 并注意 E(#grand)=3*Pgrand - 游戏结束时所选择的大牌的预期数量。这样我们的公式就变成了：
E(Score)=E(#grand)*averageWgrand+...+E(#bonus)*averageWbonus
在您的示例中，我们可以走得更远：每组中的卡片数量相等，因此由于对称性，我们可以声明：E(#grand)=E(#minor)=E(#major)=E(#grand)=:(E#group)。为了简单起见，下面我们只考虑这种特殊情况（但概述的解决方案也可以扩展到一般情况）。这导致以下简化：
E(Score)=4*E(#group)(averageWgrand+...+averageWbonus)/4
我们调用 averageW:=(averageWgrand+...+averageWbonus)/4 并注意 E(#cards)=4*E(#grand) 是游戏结束时预期的拾牌数。
这样，E(Score)=E(#cards)*averageW，所以我们的任务就简化为计算游戏结束时牌数的期望值：
E(#cards)=P(1)*1+P(2)*2+...P(n)*n
其中 P(i) 表示游戏以恰好 i 张牌结束的概率。概率 P(1)、P(2) 和 P(k)、k>9 很容易看出 - 它们是 0。
计算用i张牌结束游戏的概率-P(i):
让我们来玩一个稍微不同的游戏：我们恰好挑选 i 张牌并且当且仅当：
- 正好有一组选了3张牌。我们称这个组为
full_group. - 最后选择的第 (i) 张牌来自
full_group。
很容易看出，赢得这场比赛的概率P(win)正是我们要找的概率-P(i)。我们可以再次使用对称性，因为所有组都是相等的（P(win, full=grand) 表示我们和 full_group=grand 是什么的概率）：
P(win)=P(win, grand)+P(win, minor)+P(win, major)+P(win, bonus)
=4*P(win, grand)
P(win, grand) 是以下概率：
- 在选择
i-1牌后，选择的大牌数量为 2，即 `#grand=2' 和 - 抽取
i-1张牌后，每组抽取的牌数少于3张且 - 我们在最后一轮选了一张大牌。鉴于前两个约束条件成立，这个（条件）概率是
1/(n-i+1)（还剩下n-i+1张牌，其中只有一张是 "right"）。
从骨灰盒问题我们知道
的概率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)
和 binom(n,k)=n!/k!/(n-k)!。因此 P(win, grand) 可以计算为：
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
现在代码：
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)))
结果我得到 6.94285714286 作为游戏结束时的预期牌数。而且非常快——几乎是瞬间。不确定是否正确...
结论：
显然，如果你想处理更一般的情况（更多的组，组中的数字卡不同）你必须扩展代码（递归，binom 的记忆）和理论。
但最关键的部分：使用这种方法，您（几乎）不关心卡片的挑选顺序 - 因此您必须检查的状态数量减少了 (k-1)!其中 k 是游戏结束时可能出现的最大牌数。在您的示例 k=9 中，因此该方法更快 40000 （我什至不考虑利用对称性的加速，因为在一般情况下这可能是不可能的）。
好的，这次我希望我能解决你的问题:)
为了加速您的程序 算法:
需要两个见解（我想您已经有了，只是为了完整起见）- 序列
(card_1, card_2)和(card_2, card_1)的概率不相等，所以我们不能使用骨灰盒问题的结果，看来我们需要尝试所有排列。 - 然而，鉴于我们到目前为止挑选的一组牌，我们实际上并不需要他们挑选顺序的信息 - 对于未来的游戏过程来说都是一样的。所以使用动态规划并计算游戏过程中要遍历的每个子集的概率就足够了（因此我们需要检查
2^N而不是N!状态）。
对于一组已选取的牌 set 在下一回合中选取牌 i 的概率是：
norm:=sum Wi for i in set
P(i|set)=Wi/norm if i not in set else 0.0
计算P(set)的递归-在游戏中出现一组被选中的牌的概率是：
set_without_i:=set/{i}
P(set)=sum P(set_without_i)*P(i|set_without_i) for i in set
然而，这应该只对游戏尚未结束的 set_without_i 进行，即没有组有 3 张牌被选中。
这可以通过递归+记忆的方式来完成，或者像我的版本一样，通过使用自下而上的动态规划来完成。它还使用整数的二进制表示来表示集合和（最重要的部分！）returns 结果几乎立即 [('Grand', 0.0014104762718021384), ('Major', 0.0028878988709489244), ('Minor', 0.15321793072867956), ('Bonus', 0.84248369412856905)]:
#calculates probability to end the game with 3 cards of a type
N=12
#set representation int->list
def decode_set(encoded):
decoded=[False]*N
for i in xrange(N):
if encoded&(1<<i):
decoded[i]=True
return decoded
weights = [170000, 170000, 105, 170000, 170000, 215, 150000, 150000, 12000, 105000, 105000, 105000]
def get_probs(decoded_set):
denom=float(sum((w for w,is_taken in zip(weights, decoded_set) if not is_taken)))
return [w/denom if not is_taken else 0.0 for w,is_taken in zip(weights, decoded_set)]
def end_group(encoded_set):
for i in xrange(4):
whole_group = 7<<(3*i) #7=..000111, 56=00111000 and so on
if (encoded_set & whole_group)==whole_group:
return i
return None
#MAIN: dynamic program:
MAX=(1<<N)#max possible set is 1<<N-1
probs=[0.0]*MAX
#we always start with the empty set:
probs[0]=1.0
#building bottom-up
for current_set in xrange(MAX):
if end_group(current_set) is None: #game not ended yet!
decoded_set=decode_set(current_set)
trans_probs=get_probs(decoded_set)
for i, is_set in enumerate(decoded_set):
if not is_set:
new_set=current_set | (1<<i)
probs[new_set]+=probs[current_set]*trans_probs[i]
#filtering wins:
group_probs=[0.0]*4
for current_set in xrange(MAX):
group_won=end_group(current_set)
if group_won is not None:
group_probs[group_won]+=probs[current_set]
print zip(["Grand", "Major", "Minor", "Bonus"], group_probs)
代码中使用的"tricks"的一些解释：
一个非常标准的技巧是使用整数的二进制表示来编码一个集合。假设我们有对象 [a,b,c]，所以我们可以将集合 {b,c} 表示为 110，这意味着 a（列表中的第一个对应于 0-最低位）- 不在集合中，b(1) 在集合中，c(1) 在集合中。但是，110 读取为整数时它是 6。
current_set - for 循环模拟了游戏，在玩的时候最好理解。让我们玩两张牌 [a,b]，权重 [2,1].
我们用一个空集开始游戏，0 作为整数，所以概率向量（给定集，它的二进制表示和映射到概率的整数）：
probs=[{}=00=0->1.0, 01={a}=1->0.0, {b}=10=2->0.0, {a,b}=11=3->0.0]
我们处理current_set=0，有两种可能66%拿卡a和33%拿卡b，所以处理后的概率变成：
probs=[{}=00=0->1.0, 01={a}=1->0.66, {b}=10=2->0.33, {a,b}=11=3->0.0]
现在我们处理 current_set=1={a} 唯一的可能性是取 b 所以我们将以集合 {a,b} 结束。所以我们需要通过我们的公式更新它的 (3={a,b}) 概率，我们得到：
probs=[{}=00=0->1.0, 01={a}=1->0.66, {b}=10=2->0.33, {a,b}=11=3->0.66]
下一步我们处理2，给定集合{b}唯一的可能就是选牌a，所以集合{a,b}的概率需要再次更新
probs=[{}=00=0->1.0, 01={a}=1->0.66, {b}=10=2->0.33, {a,b}=11=3->1.0]
我们可以通过两条不同的路径到达 {a,b} - 这可以在我们的算法中看到。在我们游戏中的某个时刻通过集合 {a,b} 的概率显然是 1.0。
另一件重要的事情：在我们处理这个集合之前，所有通向 {a,b} 的路径都已经处理好了（这将是下一步）。