Установить алгоритм комбинаторики в Java

Question

У меня есть набор данных с такими атрибутами:

Marital_status = {M,S,W,D}
IsBlind = {Y,N}
IsDisabled = {Y,N}
IsVetaran = {Y,N}

и т.д.. Есть около 200 таких переменных.

Мне нужен алгоритм для генерации комбинаций атрибутов, по одному значению за раз.

Другими словами, моя первая комбинация будет:

Marital_status = M, IsBlind = Y, IsDisabled = Y, IsVeteran = Y

Следующий набор будет:

Marital_status = M, IsBlind = Y, IsDisabled = Y, IsVeteran = N

Я пытался использовать простой генератор комбинаций, рассматривая каждое значение для каждого атрибута как сам атрибут. Это не сработало, потому что взаимоисключающие варианты включены в комбинации, а количество возможных комбинаций было действительно огромным (133873417996074857185490633899939406700260683726864088366400, если быть точным)

Не могли бы вы предложить алгоритм (желательно кодированный на Java)?

Спасибо !!

Answer 1

Как отмечали другие (и вы сами), невозможно полностью это проверить.

Я предлагаю вам взять метод выборки и протестировать его. У вас сильный теоретический опыт, поэтому вы сможете найти свой путь в Интернете, чтобы найти и понять это.

---

Но позвольте мне привести небольшой пример. Пока я буду игнорировать возможные «кластеры» параметров (которые тесно связаны).

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

  Его не нужно создавать заранее, значения можно создавать с помощью цикла.

• К каждой выборке из одних данных необходимо добавить другие значения. Простым подходом было бы выбрать количество тестирований каждого отдельного образца (скажем, N = 100). Для каждой выборки из одних данных вы бы генерировали случайным образом N раз другие значения .

Если есть 1000 возможных значений, использующих все 200 параметров, и N = 100, это даст нам 100K тестов.

---

Вы могли бы развить эту основную идею многими способами:

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

Answer 2

Найди другой путь. Если у вас есть 200 переменных, и у каждой есть как минимум 2 варианта, у вас будет> = 2 ^ 200 комбинаций. Если вы генерируете одну комбинацию каждую наносекунду, потребуется около 10 ^ 43 лет, чтобы перечислить 2 200 вариантов.

Answer 3

Как указал Кейт , количество комбинаций будет невероятно большим, если не будет исключенных комбинаций, что сделает вашу потребность неуязвимой. Однако, поскольку вы уже сказали, что у вас есть взаимоисключающие варианты, пространство для решения будет меньше.

Насколько меньше? Зависит от того, сколько вариантов являются взаимоисключающими. Я рекомендую немного поработать над этим, прежде чем идти слишком усердно.

Предполагая, что достаточное количество вариантов выбора является эксклюзивным, вам все равно придется по сути его перебирать, но вы вряд ли найдете существующий, полезный алгоритм.

Что приводит меня к вопросу: какова ваша причина для этого - исчерпывающее тестирование? Звучит хорошо, но вы можете обнаружить, что это невозможно. Я сам столкнулся с этой проблемой, и, в конце концов, вас вполне может заставить некоторая комбинация тщательно отобранных «крайних» случаев плюс некоторые квази-случайно выбранные другие случаи.

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

Итак, данный пациент не слеп и не слеп. Отлично. Но это не то, что я (и я подозреваю, что все остальные здесь) поняли, когда вы упомянули обоюдное исключение.

Тем, о которых я говорю, например, если слепой, не может быть инвалидом или что-то в этом роде.

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