Как сгенерировать множество с покрытием максимального числа результатов?

Question

[valis]

Есть следующая задача
Имеем условие для формирования множества множеств (или таблицы):
- Количество строк (элементов множества)
- Для каждого столбца задан процент значения Null (например (10,20,50) -первый столбец 10% нулов, второй 20 и третий 50)

Необходимо сгенерить такое множество заданной длины чтобы оно оптимально покрывала все возможные комбинации нулов и не нулов

Comments

[longclaps]

Прикольно. А критерий оптимальности потерялся? Ничего, он нам нахер не усрался.

Answer 1

[xmoonlight]

1. Вычисляем общее количество комбинаций ("масок" нулов/не-нулов: от "все нулы" до "все не-нулы" на заданном множестве: количестве строк). Это будет 100% всего диапазона.
2. 10%, 20%, 50% - каждый 10-й, каждый 5-й, каждый 2-й, соответственно.
3. Начнём с самого частого (50%) и через 1 (каждый 2-й) составим список.
4. Возьмём следующий (20%) и применим к оставшейся половине (так же равномерно, учитывая половину - за 100%) и присоединим к списку.
5. Возьмём оставшийся процент (10%) и применим к оставшимся 30% - это будет каждый 3-й элемент и тоже присоединим к списку.

Полученный список - будет то, что требовалось.

Answer 2

[Rsa97]

А в чём проблема то?

$nullPercents = [10, 20, 50];
$totalRows = 11;
$result = [];
for ($i = 1; $i <= $totalRows; $i++) {
  $row = [];
  foreach ($nullPercents as $percent) {
    if ($i <= $totalRows*$percent/100) {
      $row[] = null;
    } else {
      $row[] = $i;
    }
  }
  $result[] = $row;
}

Comments

[Wataru]

Тут покрытие различных вариантов будет наихудшим - только n+1 вариантов в лучшем случае.

[Rsa97]

wataru, А в задаче никакого критерия оптимальности нет, значит и так сойдёт.

[Wataru]

Последнее предложение в вопросе:
Необходимо сгенерить такое множество заданной длины чтобы оно оптимально покрывала все возможные комбинации нулов и не нулов

[Rsa97]

wataru, А критерий оптимальности какой?

[Wataru]

В этом же предложении: "покрывала все возможные комбинации нулов и не нулов"

[Rsa97]

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