Эффективно генерируйте все уникальные 4-целые отношения в диапазоне вплоть до масштабирования. ⇐ Python

[Anonymous]

Я хочу сгенерировать все уникальные комбинации из 4 целых чисел, где каждое значение находится в небольшом диапазоне, например 1–10, и две комбинации считаются одинаковыми, если одна из них является масштабированной версией другой.
Пример эквивалентности:

Код: Выделить всё

(1,2,3,4) ≈ (2,4,6,8)

Я хочу избежать наивной проверки каждой новой комбинации со всеми предыдущими (которые растут в геометрической прогрессии).
Существуют ли какие-либо алгоритмы, структуры данных или предварительно вычисленные таблицы для эффективного создания всех таких уникальных относительных комбинаций?
Для масштаба, для диапазонов 1–1000 для всех четырех переменных:

• Всего комбинаций: 1000^4 = 1 000 000 000 000 (1 триллион)
• Наивное парное сравнение для проверки уникальности: ~ (10^12 * 10^12) / 2 = 5 × 10^23 сравнений
• Даже при 1 микросекунде на проверку это займет 5 × 10^23 мкс = 5 × 10^17 секунд ≈ 15,8 миллиона лет.

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

Подробнее здесь: https://stackoverflow.com/questions/798 ... to-scaling