如何将Fisher-Yates-Knuth定理应用于有限制的洗牌?或者有没有其他有效的方法

本文关键字：或者 有没有 其他 方法 有效 Fisher-Yates-Knuth 定理 应用于 有限制 | 更新日期: 2023-09-27 18:11:47

例如，我想洗牌4副牌，并确保:

任何连续的4张牌不会来自同一套牌。

当然我可以先洗牌，然后过滤掉不好的排列，但如果限制很强(例如任何连续的2张牌都不会来自同一套牌)，就会有太多的失败。

如果我不介意它稍微没有偏见，(当然偏见越少越好)，我该怎么办?

编辑:澄清

是的，我希望尽可能统一地从所有完全洗牌中挑选，以便应用此附加标准。

如何将Fisher-Yates-Knuth定理应用于有限制的洗牌?或者有没有其他有效的方法

我将处理如下:

首先你可以洗牌每4副牌(使用FYK算法)

然后生成一个4个分区(*我在下面定义分区)的52张牌的4副牌与不超过3个元素在每一组分区的约束:

例如:

(1,3,0,3,2,0,1) would be a partition of 10 with this constraint
(1,1,1,1,1,1,1,1,1,1) would be a partition of 10 too with this constraint

然后根据这些分区混合4个deck

例如:

(3,2,1)
(2,2,2)

取第1层的3，第2层的2，第1层的2，第2层的2，第1层的1，第2层的2。(?)

所有分区都是无效的，所以您需要添加一个约束:

的例子:

(1,2,1,1,1,1,1,1) 
(3,3,3)

最终将有4个牌1的元素。

所以最后一个分区必须满足一个约束，我写了一个小python程序来生成这些分区

from random import randint,choice
def randomPartition(maxlength=float('inf'),N=52): 
    '''
    the max length is the last constraint in my expanation:
      you dont want l[maxlength:len(l)]) to be more than 3
 in this case we are going to randomly add +1 to all element in the list that are less than 3
    N is the number of element in the partition
     '''
    l=[] # it's your result partition
    while(sum(l)<N ):
        if (len(l)>maxlength and sum(l[maxlength:len(l)])>=3): #in the case something goes wrong 
            availableRange=[i for i in range(len(l)) if l[i]<3] #create the list of available elements to which you can add one
            while(sum(l)<N):
                temp=choice(availableRange) #randomly pick element in this list
                l[temp]+=1
                availableRange=[i for i in range(len(l)) if l[i]<3] #actualize the list
                if availableRange==[]: #if this list gets empty your program cannot find a solution
                    print "NO SOLUTION" 
                    break
            break
        else:
            temp=randint(0,min(N-sum(l),3)) # If everything goes well just add the next  element in the list until you get a sum of N=52
            l.append(temp)
    return l

现在您可以生成4个分区，并根据这些分区混合甲板:

def generate4Partitions():
    l1=randomPartition();
    l2=randomPartition();
    l3=randomPartition();
    m=max(len(l1),len(l2),len(l3))
    l4=randomPartition(m);
    return l1,l2,l3,l4

根据它们的定义，这4个分区将始终是允许的。

注意:

可能有更多不允许的情况，例如:

(3,0,0,3)
(0,3,3,0)

我想这段代码需要稍微修改一下，以考虑更多的约束。

但它应该很容易，只是删除不需要的零，像这样:

(3,0,3)
(0,3,3,0)

希望大家能理解，对大家有帮助

相关文章：