这是一个游戏,您有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

“最大选择数”代表不同“卡”的总数.总选择数代表用户选择的最大数量.这是因为经过8个选择,您将确保每种类型都有2个,因此在第9个选择中,您将保证具有3个匹配项.

TotalPicks = 9
MaxPicks = 12

该名称应为PickedProbabilities.

Picks = {0:0,1:0,2:0,3:0}

这是timeit类的简单版本,因为我不喜欢timeit类

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')

解决方法:

好的,这次我希望我能解决您的问题：)

为了从算法上加快程序速度,需要两个洞察力(我想您是出于完整性的考虑而拥有它们)：

>序列(card_1,card_2)和(card_2,card_1)的概率不相等,因此我们无法使用urn问题的结果,看来我们需要尝试所有排列.
>但是,考虑到到目前为止我们选择的一组纸牌,我们实际上并不需要这些信息以什么顺序选择它们-在以后的游戏中都是一样的.因此,使用动态编程并计算游戏期间要遍历的每个子集的概率就足够了(因此,我们需要检查2 ^ N而不是N！个状态).

对于一组拾取的卡,设置下一轮拾取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张牌.

这可以通过递归记忆或通过使用自下而上的动态编程来实现.它还使用整数的二进制表示形式表示集合,并且(最重要的部分！)几乎立即返回结果[(‘Grand’,0.0014104762718021384),(‘Major’,0.0028878988709489244),(‘Minor’,0.15321793072867956),(‘奖金”,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)

对代码中使用的“技巧”的一些解释：

一个非常标准的技巧是使用整数的二进制表示形式对集合进行编码.假设我们有对象[a,b,c],因此我们可以将集合{b,c}表示为110,这意味着a(列表中的第一个对应于0-最低数字)-不在集合中,集合中的b(1),集合中的c(1).但是,将110读为整数则是6.

current_set-for循环可模拟游戏,并在玩游戏时能更好地理解.让我们玩两张权重为[2,1]的卡片[a,b].

我们从一个空集开始游戏,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％拿卡card,因此概率在处理后变为：

 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}的路径(这将是下一步).