Алгоритм может быть слишком сильным словом, поскольку для меня это подразумевает формализм и публикацию, но есть метод выбора подмножеств с точными пропорциями (при условии, что ваши проценты дают целые числа предметов из выборочной вселенной ), и это намного проще, чем другие предложенные решения. Я построил один и протестировал его.
Между прочим, мне жаль, что я здесь медленно отвечаю, но сейчас мое время ограничено. Я довольно быстро написал жестко запрограммированное решение, и с тех пор я превращаю его в достойную реализацию общего назначения. Поскольку я был занят, это все еще не завершено, но я не хотел больше откладывать ответ.
Метод:
По сути, вы будете рассматривать каждую строку отдельно и решать, будет ли она выбираться, исходя из того, дают ли ваши критерии место для выбора каждого из значений ее столбца.
Чтобы сделать это, вы будете рассматривать каждое из ваших правил столбца (например, 40% мужчин, 60% женщин) как отдельную цель (например, при желаемом размере подмножества 100, вы ищете 40 мужчины, 60 женщин). Сделайте счетчик для каждого.
Затем вы выполняете цикл, пока не создадите свое подмножество или не проверили все строки в образце юниверса, не найдя соответствия (см. Ниже, что происходит затем). Это цикл в псевдокоде:
- Randomly select a row.
- Mark the row examined.
- For each column constraint:
* Get the value for the relevant column from the row
* Test for selectability:
If there's a value target for the value,
and if we haven't already selected our target number of incidences of this value,
then the row is selectable with respect to this column
* Else: the row fails.
- If the row didn't fail, select it: add it to the subset
В этом суть. Он предоставит подмножество, соответствующее вашим правилам, или не сможет это сделать ... что подводит меня к тому, что происходит, когда мы не можем найти
матч.
невыполнимость:
Как уже отмечали другие, не всегда возможно удовлетворить любой произвольный набор правил для любой произвольной выборочной вселенной. Даже если предположить, что правила действительны (проценты для каждого значения составляют 100), размер подмножества меньше, чем размер юниверса, и в юниверсе содержится достаточно индивидуумов с каждым выбранным значением, чтобы поразить цели, но все равно возможно потерпеть неудачу, если значения на самом деле не распределяются независимо.
Рассмотрим случай, когда все мужчины в выборочной вселенной являются австралийцами: в этом случае вы можете выбрать только столько мужчин, сколько сможете выбрать австралийцев, и наоборот. Таким образом, набор ограничений (размер подмножества: 100; мужчины: 40%; австралийцы 10%) не может быть удовлетворен вообще из такой вселенной, даже если все выбранные нами австралийцы являются мужчинами.
Если мы изменим ограничения (размер подмножества: 100; мужчины: 40%; австралийцы 40%), теперь мы можем создать соответствующее подмножество, но все выбранные нами австралийцы должны быть мужчинами. И если мы снова изменим ограничения (размер подмножества: 100; мужчины: 20%; австралийки 40%), теперь мы можем сделать соответствующее подмножество, но только если мы не выберем слишком много австралийских женщин (не более половины в это дело).
В этом последнем случае порядок выбора будет иметь значение. В зависимости от нашего случайного семени, иногда мы можем добиться успеха, а иногда и потерпеть неудачу
По этой причине алгоритм (и моя реализация) должны быть готовы повторить попытку. Я думаю об этом как о тесте на терпение: вопрос в том, сколько раз мы готовы позволить ему потерпеть неудачу, прежде чем мы решим, что ограничения не совместимы с выборочной совокупностью.
* 1035 Пригодность *
Этот метод хорошо подходит для описанной задачи ОП: выбор случайного подмножества, соответствующего заданным критериям. Это не подходит для ответа на немного другой вопрос: «Возможно ли сформировать подмножество с заданными критериями».
Мое объяснение этому простое: ситуации, в которых алгоритму не удается найти подмножество, - это ситуации, в которых данные содержат неизвестные связи или когда критерии допускают очень ограниченное количество подмножеств из выборочного юниверса. В этих случаях использование любого подмножества было бы сомнительным для статистического анализа, по крайней мере, без дальнейших размышлений.
Но для ответа на вопрос, возможно ли сформировать подмножество, этот метод недетерминирован и неэффективен. Было бы лучше использовать один из более сложных алгоритмов перемешивания и сортировки, предложенных другими.
Pre-Validation:
Непосредственной мыслью об обнаружении того, что не все подмножества могут быть удовлетворены, является выполнение некоторой начальной проверки и, возможно, анализ данных, чтобы определить, являются ли они подотчетными или только условно подотчетными.
Моя позиция заключается в том, что кроме первоначальной проверки того, что каждое из правил столбца является действительным (т. Е. Процентное соотношение столбца равно 100 или достаточно близко) и что размер подмножества меньше размера юниверса, другой предварительной проверки нет что стоит сделать Можно привести аргумент, что вы можете захотеть проверить, что в юниверсе достаточно индивидуумов с каждым выбранным значением (например, в действительности в юниверсе 40 мужчин и 60 женщин), но я этого не реализовал.
Кроме этого, любой анализ для выявления связей в популяции сам по себе отнимает много времени, так что вам может быть лучше обслужен, просто выполняя задачу с большим количеством повторных попыток. Может быть, это просто отсутствие статистики.
Не совсем проблема с подмножеством сумм
Было высказано предположение, что эта проблема похожа на задачу subset sum . Я утверждаю, что это тонко и в то же время существенно отличается. Я рассуждаю так: для проблемы суммы подмножеств необходимо сформировать и протестировать подмножество, чтобы ответить на вопрос о том, соответствует ли оно правилам: невозможно (за исключением определенных граничных условий) проверить отдельный элемент перед добавлением это к подмножеству.
По вопросу ОП, однако, это возможно. Как я объясню, мы можем случайным образом выбирать строки и тестировать их по отдельности, потому что вес каждого из них равен единице.