комбинаторика — Найти все комбинации чисел между минимальным и максимальным в переполнении стека
Я пытаюсь выяснить наиболее оптимизированный код, который найдет список комбинаций между X и Y для данного списка, как показано ниже:
- A = 4
- B = 6
- C = 3
- D = 5
- Е = 4
- F = 1
И скажем, X = 7, а Y = 16
Таким образом, находит все комбинации, сумма которых больше или равна X и меньше или равна Y. Значения могут повторяться.
То есть:
- А.А.
- AAA
- AAAA
- ABA
- ABB
- азбука
- …
- EE
- EEE
- ЕЕЕЕ
- Е.А.
- EAA
…И так далее
Конечное условие: дубликаты не должны быть включены. Например, ABB такой же, как BBA, и BAB. Таким образом, последние два не должны быть включены.
Я пытаюсь найти наиболее оптимизированный код для этого, так как список ввода может содержать до 200 номеров …
Решение
Что нужно сделать:
- Зациклить все наши комбинации букв
- Упорядочить комбинацию в алфавитном порядке, чтобы мы могли найти дубликаты. например ABB такой же, как BAB — см. https://stackoverflow.com/a/9912497/897266
- Если это дубликат, отметьте его как таковой или исключите — см. https://stackoverflow.com/a/10096034/897266
- Рассчитайте значение каждой комбинации — см. https://stackoverflow.com/a/49181225/897266
- Сравните значение каждой комбинации, чтобы убедиться, что оно находится в пределах наших мин / макс. https://stackoverflow.com/a/4684064/897266
- Если это так, сохраните его, в противном случае пометьте его как нет или исключите
- После цикла выведите набор комбинаций, которые проходят тест и не являются дубликатами.
Я мог бы написать все это в php, но я надеюсь, что этого достаточно, чтобы дать вам шанс на это.
Другие решения
Других решений пока нет …