Как я могу применить Fisher-Yates-Knuth к Shuffling с ограничениями?Или есть другой эффективный подход? - PullRequest
Новая
       8

Как я могу применить Fisher-Yates-Knuth к Shuffling с ограничениями?Или есть другой эффективный подход?

2 голосов
/ 19 октября 2011

Например, я хотел бы перетасовать 4 колоды карт и убедиться:

Любые последовательные 4 карты не будут приходить из одной колоды.

Конечно, я могу сделатьсначала перетасуйте, а затем отфильтруйте плохие перестановки, но если ограничения сильны (например, любые две последовательные карты не будут приходить из одной колоды), будет слишком много неудач.

Если я не возражаючто, если это немного беспристрастно, (конечно, чем меньше уклон, тем лучше), как мне поступить?

Редактировать: Уточнить

Да, я хочу как можно более равномерновыбрать из всех полных перемешиваний так, чтобы применялся этот дополнительный критерий.

1 Ответ

0 голосов
/ 19 октября 2011

Я бы обработал, как показано ниже:

Сначала вы можете перетасовать каждые 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 колоды на основе этих разделов.

Например, если у вас есть: 

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

вы берете 3 сначала из колоды 1, затем 2 из колоды 2, затем 2 из колоды 1, 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)

Надеюсь, это понятно и помогает

...