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

[Anonymous]

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

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

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

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

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

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

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