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 als gleich betrachtet werden, 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?
Für die Skala, für Bereiche von 1–1000 für alle vier Variablen:

• Gesamtkombinationen: 1000⁴ = 1.000.000.000.000 (1 Billion)
• Naiver paarweiser Vergleich zur Prüfung der Eindeutigkeit: ~ (10¹² * 10¹²) / 2 = 5 × 10²³ Vergleiche
• Selbst bei 1 Mikrosekunde pro Prüfung würde dies 5 dauern × 10²³ μs = 5 × 10¹⁷ Sekunden ≈ 15,8 Millionen Jahre.

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