Generieren Sie effizient alle eindeutigen 4-Ganzzahl-Verhältnisse innerhalb eines Bereichs bis zur Skalierung ⇐ Python

[Anonymous]

Ich möchte alle eindeutigen 4-Ganzzahl-Kombinationen generieren, bei denen jeder Wert in einem kleinen Bereich liegt, zum Beispiel: 1–10, und zwei Kombinationen gelten als gleich, wenn eine eine skalierte Version der anderen ist.
Beispiel für Äquivalenz:

Code: Select all

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

Ich möchte vermeiden, naiv jede neue Kombination mit allen vorherigen zu vergleichen (was exponentiell wächst).
Gibt es Algorithmen, Datenstrukturen oder vorberechnete Tabellen zum effizienten Generieren all dieser eindeutigen relativen Kombinationen?
Bearbeiten (Mathematik für Skala):
Für Bereiche von 1–1000 für alle vier Variablen:
Gesamtkombinationen:

1000^4 = 1.000.000.000.000 (1 Billion)

Naiver paarweiser Vergleich zur Überprüfung der Eindeutigkeit:

~ (10^12 * 10^12) / 2 = 5 × 10^23 Vergleiche

Selbst bei 1 Mikrosekunde pro Überprüfung würde dies dauern:

5 × 10^23 μs = 5 × 10^17 Sekunden ≈ 15,8 Millionen Jahre

Naive Überprüfung ist selbst bei modernen Computern eindeutig völlig unpraktisch, was zeigt, warum ein cleverer Algorithmus oder eine clevere Datenstruktur notwendig ist.