ChatGPT подсказал название задачи по формулировке

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

Пусть имеется множество из N элементов. В ходе одного испытания случайным образом выбирается какой-либо элемент. Сколько в среднем нужно испытаний, чтобы каждый элемент множества был выбран хотя бы один раз?

ChatGPT в целом правильно воспроизводил идею решения, но с названием не заладилось. За несколько попыток правильного названия он так и не выдал, в каждой попытке какая-то ерунда:

Это классическая задача, известная как проблема дней рождения или задача выбора.

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

Эта задача относится к классу задач под названием «задача об абсолютной перестановке» или «задача о деньгах дней рождения».

Этот вопрос относится к теории вероятностей и известен как проблема «парадокса дней рождений» или «проблема встречи». В вашем случае, это известно как проблема «выборки с возвратом» (sampling with replacement).

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

Когда я добавил к своему запросу «ответ дай по-английски», получил правильное название:

This problem is a classic example of the coupon collector's problem.

Оказывается, эта интересная задача встречается в английской литературе под таким названием, что можно перевести как «задача коллекционера», а в русской литературе практически неизвестна. Я думал, что для ChatGPT не проблема дать ответ с учетом перевода. Но, видимо, при генерации ответа связь между словами одного языка сильнее, чем связи между терминами с учетом перевода.

О самой задаче коллекционера написал подробнее в «черновиках физика».

Как правильно представлять и обрабатывать состояние фильтров в коде

Фильтры в интерфейсах интернет-магазинов имеют одну особенность. Фильтр, в котором выбрано всё, и фильтр, в котором не выбрано ничего, дают один и тот же результат — надо показать все товары:

Если рассуждать с точки зрения формальной логики, пустому фильтру нужно было бы сопоставить пустой результат. Но на практике в этом нет смысла. Об этом как раз сегодняшний совет Бюро.

Я хочу рассказать, как правильно обрабатывать в коде эту особенность фильтров. Вообще естественно сопоставить выбранным элементам фильтра элементы массива. В этом случае пустому фильтру будет соответствовать пустой массив. Если мы напишем код из этого предположения, то по всей цепочке передачи состояния фильтра нужно отдельной логикой обрабатывать пустой массив, а это будет громоздко и некрасиво.

Чтобы показать, в чем недостатки кодирования пустого фильтра пустым массивом, рассмотрим типовую операцию — пересечение фильтров. Она требуется, когда мы проверяем права доступа пользователя к выбранным в фильтре элементам. Для иллюстрации представим, что в примере выше есть скрытые сезоны, а в них — скрытые товары. Допустим, мы не хотим продавать летом зимние товары, потому что их нет на складе, и скрываем до следующей зимы. Логика в коде может быть примерно такой:

$filterValues  = $request->get('seasons');
$allowedValues = getActiveSeasons();
if ($filterValues === []) {
    // В фильтре ничего не выбрано - используем все доступные значения
    $intersectValues = $allowedValues;
} else {
    $intersectValues = array_intersect($allowedValues, $filterValues);
}

// Получаем список товаров из БД
$result = getProductsByConditions(['seasons' => $intersectValues]);

Мы видим недостаток: $allowedValues и $filterValues обрабатываются несимметрично в этом коде. Пустой массив в $filterValues не приводит к ограничениям списка товаров. А пустой массив в $allowedValues должен приводить к пустому результату. Было бы неправильно отображать товары из всех категорий, после того как я скрыл последнюю доступную категорию.

Представьте теперь, что нам поступило новое требование: администратор должен видеть скрытые товары. Тогда код еще больше усложнится и станет примерно таким:

$filterValues  = $request->get('seasons');
$allowedValues = getActiveSeasons();
$conditions    = [];
if (grantedHiddenProducts($currentUser)) {
    if (!$filterValues === []) {
        // Админу фильтруем, только если он сам заполнил фильтр
        $conditions = ['seasons' => $filterValues];
    }
} elseif ($filterValues === []) {
    // В фильтре ничего не выбрано - используем все доступные значения
    $conditions = ['seasons' => $allowedValues];
} else {
    $intersectValues = array_intersect($allowedValues, $filterValues);
    $conditions = ['seasons' => $intersectValues];
}

// Получаем список товаров из БД
$result = getProductsByConditions($conditions);

Я предлагаю интерпретировать значения массивов-ограничений по-другому. За пустым массивом сохраним его формальный смысл пустого множества (пустой массив — пустой результат). А отсутствие ограничений будем кодировать значением null. В этом случае множество элементов массива всегда соответствует множеству разрешенных элементов, а null соответствует универсальному множеству — дополнению к пустому множеству.

Если следовать соглашению о кодировке отсутствия ограничений через null, пустой интерфейсный фильтр конвертируется в null в самом начале потока данных. В конце потока при формировании запроса к БД значение null в фильтре игнорируется и в SQL-запрос не попадает. В то же время на пустой массив можно сразу возвращать пустой результат без выполнения реального запроса к БД (array_intersect() как раз может вернуть пустой массив, если кто-то подбирает id элементов из фильтра через адресную строку). В остальных случаях элементы фильтра передаются напрямую в условие IN в запросе:

$filterValues = $request->get('seasons');
if ($filterValues === []) {
    // По бизнес-логике если фильтр не выбран, показываем все доступные товары
    $filterValues = null;
}

// Скрытые товары показываем только админам
$allowedValues = grantedHiddenProducts($currentUser) ? null : getActiveSeasons();

// Комбинируем ограничения
$intersectValues = array_intersect_sets($allowedValues, $filterValues);

// Получаем список товаров из БД
$result = getProductsByConditions(['seasons' => $intersectValues]);

// ...

function array_intersect_sets(?array $a, ?array $b): ?array {
    if ($a === null) {
        return $b;
    }
    
    if ($b === null) {
        return $a;
    }
    
    return array_intersect($a, $b);
}

function getProductsByConditions(array $conditions): array {
    // ...
    if ($conditions['seasons'] !== null) {
        if ($conditions['seasons'] === []) {
            return [];
        }
        
        $queryBuilder->andWhere('p.seasons IN (?)', $conditions['seasons']);
    }
    // ...
}

В этом варианте в каждом фрагменте кода прозрачная и ясная логика. Функция array_intersect_sets() является симметричной по отношению к перестановке аргументов. Она переиспользуется везде, где нужно применять несколько ограничений одновременно. Из кода пропала проблемная длинная цепочка условных операторов. Раньше при изменении логики фильтрации программист должен был осознать эту цепочку целиком и быть очень внимательным, чтобы не упустить какую-нибудь хитрую комбинацию условий.

← сюда туда →