NP-полные или нет, номера работают так, что можно эффективно создавать сделки даже если все значения p всех четырех рук указаны как редкий результат.
Стратегия одного поколения заключается в следующем. Учитывая значения p для всех четырех рук, вычислите для каждого из 2^16 = 65 536 подмножеств высоких карт, сколько существует возможностей, учитывая, что Восток-Запад вместе удерживает это подмножество. Используя арифметику BigInteger, создайте случайное подмножество в соответствии с количеством возможностей, затем произвольно распределите старшие карты Востока и Запада между Востоком и Западом и распределите по стартовым картам Север-Юг между Севером и Югом наугад и разыщите остальную часть карты.
Учитывая подмножество EW с указанием высоких карт, Восток-Запад удержание, сумма, по каждому приемлемому подмножества E из EW конкретизирующих высоких карт, которые держат Восток, количество (26 - |EW|) choose (13 - |E|), то есть число способов разделить низкие карты между Востоком и Западом, учитывая, что известно, какие из них принадлежат Востоку-Западу. Сделайте тот же расчет для Север-Юг.
Для каждого выбора EW количество способов разделить низкие карты между Востоком и Западом и Север-Юг составляет (36 choose (26 - |EW|)). Вес выборки EW должен составлять это количество, умноженное на количество разрывов для восточно-западного периода, количество разрывов для Север-Юг.
Программа должна будет работать через порядка 3^16 = 43,046,721 возможностей, что много, но на самом деле это не так много для компьютера. Вот полностью прототип прототипа Python, который занимает около минуты. Я ожидаю, что с лучшей реализацией Java потребуется немного секунды.
#!/usr/bin/env python3
from collections import namedtuple
from itertools import combinations
from math import factorial
from random import randrange
Card = namedtuple('Card', ('rank', 'suit'))
ranks = {'A', 'K', 'Q', 'J', '10', '9', '8', '7', '6', '5', '4', '3', '2'}
suits = ['S', 'H', 'D', 'C']
cards = {Card(rank, suit) for rank in ranks for suit in suits}
def p_value(card):
return {'A': 4, 'K': 3, 'Q': 2, 'J': 1}.get(card.rank, 0)
high_cards = {card for card in cards if p_value(card)}
def binomial(n, k):
return factorial(n) // (factorial(k) * factorial(n - k))
def sample_count2(ns_high_cards, n_p, s_p):
assert n_p + s_p == sum(map(p_value, ns_high_cards))
sample = None
count = 0
for k in range(min(len(ns_high_cards), len(cards) // 4) + 1):
for n_high_cards in map(set, combinations(ns_high_cards, k)):
if sum(map(p_value, n_high_cards)) != n_p:
continue
s_high_cards = ns_high_cards - n_high_cards
assert sum(map(p_value, s_high_cards)) == s_p
added_count = binomial(len(cards) // 2 - len(ns_high_cards), len(cards) // 4 - len(n_high_cards))
if not added_count:
continue
count += added_count
if randrange(count) < added_count:
sample = (n_high_cards, s_high_cards)
return (sample, count)
def sample_count(n_p, e_p, s_p, w_p):
assert n_p + e_p + s_p + w_p == sum(map(p_value, high_cards))
sample = None
count = 0
for k in range(min(len(high_cards), len(cards) // 2) + 1):
for ns_high_cards in map(set, combinations(high_cards, k)):
if sum(map(p_value, ns_high_cards)) != n_p + s_p:
continue
ew_high_cards = high_cards - ns_high_cards
assert e_p + w_p == sum(map(p_value, ew_high_cards))
ns_sample, ns_count = sample_count2(ns_high_cards, n_p, s_p)
ew_sample, ew_count = sample_count2(ew_high_cards, e_p, w_p)
added_count = binomial(len(cards) - len(high_cards), len(cards) // 2 - len(ns_high_cards)) * ns_count * ew_count
if not added_count:
continue
count += added_count
if randrange(count) < added_count:
n_sample, s_sample = ns_sample
e_sample, w_sample = ew_sample
sample = (n_sample, e_sample, s_sample, w_sample)
return (sample, count)
print(sample_count(15, 10, 10, 5))
Хорошо спасибо, это достаточно быстрое и простое решение; это так сложно, как мне нужно сделать для коэффициента скорости. – nmore