Duplikate in Funktionsbildmenge

[OpaK]

Ich bin hier auf etwas Seltsames gestossen:

for (let i = 0; i < 18; i++) {
  let j = (((i * 4) % 18) + Math.floor(i / 4)) % 18;
  console.log(i, j);
}

Alle Zahlen von 0 - 17 werden ausgegeben, aber die 13 fehlt - und die 0 ist doppelt. Die Abbildung sollte aber bijektiv sein (jeder Wert aus dem Urbild soll um ein Offset verschoben auch in der Bildmenge sein...)

Wie geht man diese Aufgabe an? Ist das womöglich nur eine Besonderheit in JS, aka rundungsbdingt?

 

[Oneixee5]

Es führt sowohl i = 0 als auch i = 17 zum Ergebnis j = 0. Der Wert 0 ist also doppelt - nicht injektiv. 0 bis 17 wird also nie erreicht und damit nicht bijektiv.

Im Klartext:
i = 17

1. (((17 * 4) % 18) + Math.floor(17 / 4)) % 18
2. ((68 % 18) + 4) % 18 (Lang: 68 = 3 * 18 + 14, Rest ist 14)
3. (14 + 4) % 18
4. 18 % 18
5. j = 0

 

[OpaK]

Und was müsste ich ändern? 13 erscheint glaube ich erst bei i = 20

 

[OpaK]

Habe umgestellt, aber jetzt fehlt die 1 und 0 ist Duplikat:

let n = 18;
let seen = {};
for (let i = 0; i < n; i++) {
  let j = Math.floor((((i * 4) % n) + i / 4.5) % n);
  console.log(i, j);
  if (seen[j]) {
    console.log(j + ' is duplicate.');
  }
  seen[j] = true;
}
for (let i = 0; i < n; i++) {
  if (!seen[i]) {
    console.log(i + ' is missing.');
  }
}

Was müsste denn geändert werden, damit keine Zahlen mehr fehlen oder mehrfach auftreten, die Berechnung (Zeile 4) minimal ist und es auch für beliebige n funktioniert (schaue Richtung modulare Arithmetik...)?

 

[Oneixee5]

Das kann ich nicht aus dem Kopf vorhersagen. Ich würde auch nur Schritt für Schritt analysieren.
Bei 18 Werten kann man sich einfach ein Map mit den erwarteten Umrechnungen machen und sich die Berechnung sparen. Das ist evtl etwas langsamer aber JS nimmt man nicht wegen der Performanz.

 

[OpaK]

Um JS ging es nur so vordergründig... Eher wollte ich zwei Dinge: a) Zunächst ausschließen, dass etwa etwas an einer Rundung liege, und b) eine andere Formel oder einen anderen mathematischen Ansatz für dieses Problem finden (aber kein if-else-...).

Es müsste doch möglich sein, die Länge zu überschreiten (18) und gleichzeitig den Versatz zu erhöhen, mit einer geschossen Formel.

Wozu das Ganze? Aus 18 Farben, die sich nur in kleinen Nuancen unterscheiden, muss ich oft nur 5 bis 10 Farben auswählen. Es sollen also nicht immer sofort die Nachbarfarben gewählt werden, erst wenn mehr als 10 Farben benötigt würden.

 

[Oneixee5]

Um eine bijektive Abbildung für die Farben zu erhalten, muss eine Schrittweite gewählt werden, die "teilerfremd" zu 18 ist.
Der Ansatz scheitert weil 4 und 18 den gemeinsamen Teiler 2 haben.
Dadurch wiederholen sich die Reste der Multiplikation vorzeitig, was zu der doppelten 0 und der fehlenden 13 führt.

Schrittweite von 5 oder 7:

for (let i = 0; i < 18; i++) {
  // 5 garantiert maximale Abstände und Bijektivität.
  let j = (i * 5) % 18;
  console.log(i, j);
}

Die KI hat mich noch auf den "Goldenen Schnitt" gebracht, das wäre flexibler wenn eine andere Anzahl von Farben verwendet werden soll.

 

[OpaK]

Danke. 🙏 Ich dachte erst, das sei für die KI zu schwer, aber inzwischen kann sie es... Also geht es mathematisch gesehen um Äquivalenzklassen und Restklassenringe.

Btw, mein toller Code sieht so aus:

    function getNextHslColorString(currentIndex, hslLightness) {
        let totalSteps = 18;
        currentIndex = (((currentIndex * 4) % totalSteps) + Math.floor(currentIndex / 4)) % totalSteps;
        let nextIndex = (currentIndex + 1) % totalSteps;
        let hue = Math.round((nextIndex * 360) / totalSteps);
        let hslSaturation = 50;
        return `hsl(${hue}, ${hslSaturation}%, ${hslLightness}%)`;
    }

 

[Oneixee5]

Ja Mathematiker bin ich nicht, es hat schon etwas gedauert bis ich auf die Teilerregel von Modulo gekommen bin.

Der JS-Code ist einigermaßen schlimm: Parameter ändern!!! Und let statt const ...

 

[OpaK]

Mag const nicht... Schreibst du in Java vor jede lokale Variable final? Für mich hats keinen Nutzen

 

[Oneixee5]

Mag const nicht... Schreibst du in Java vor jede lokale Variable final? Für mich hats keinen Nutzen

Ja, das macht die IDE automatisch wenn es möglich ist. Wenn dich deine IDE nicht nervt oder das nicht automatisch behebt, dann ist dein Linter zu lasch eingestellt.
Wir machen ohnehin fast nur noch TypeScript statt JavaScript..

 

[Oneixee5]

Danke. 🙏 Ich dachte erst, das sei für die KI zu schwer, aber inzwischen kann sie es... Also geht es mathematisch gesehen um Äquivalenzklassen und Restklassenringe.

Btw, mein toller Code sieht so aus:

    function getNextHslColorString(currentIndex, hslLightness) {
        let totalSteps = 18;
        currentIndex = (((currentIndex * 4) % totalSteps) + Math.floor(currentIndex / 4)) % totalSteps;
        let nextIndex = (currentIndex + 1) % totalSteps;
        let hue = Math.round((nextIndex * 360) / totalSteps);
        let hslSaturation = 50;
        return `hsl(${hue}, ${hslSaturation}%, ${hslLightness}%)`;
    }

Wenn ich mir das so anschaue, vermute ich einen Bug, resultierend aus 2 Problemen. Leider bin ich ziemlich schlecht, wenn es um Erklärungen geht, daher kannst du evtl. gar nicht verstehen was ich meine.

Der allererste Schritt 0 müsste bei 0° (HSL-Rot) liegen aber 0 kann, durch das + 1, im kleinsten Fall 1, nie erreicht werden.
let nextIndex = (currentIndex + 1) % totalSteps;

Wenn du die Funktion in einer Schleife aufrufst (0, 1, 2, 3...), springen die Farben nicht sauber verteilt durch den Farbkreis, sondern erzeugen teilweise identische oder wild verschobene Werte, weil die Verschiebung/Umwandlung auf den aktuellen statt auf den nächsten Schritt angewendet wird.

Totalschaden der Logik:
...
5. Durchlauf (Schritt 4) (currentIndex = 4):
5.1 Die Misch-Maschine macht aus der 4 eine 17.
5.2 Danach + 1 ==> (17 + 1) % 18 ==> nextIndex wird 0

 

[OpaK]

Danke, ich schaue mir die Funktion noch einmal an

Ich verstehe ehrlich gerade nicht, weshalb der nextIndex erst zwei Zeilen später erscheint. Vermutlich hatte ich mir das anders gedacht.

 

[OpaK]

Hab's endlich. 👏

Sehr kompliziert, aber es funktioniert nun wie gewünscht mit einem beliebigen Offset zwischen 1 und Sqrt(18 x 2).

Offset=1 wäre dabei die Identitätsfunktion. Vielleicht ginge das auch noch einfacher.

function shiftIndex(currentIndex, offset) {
  let totalSteps = 18;
  let offset1 = offset;
  let offset2 = Math.round(totalSteps / offset1);
  if (totalSteps % offset2 != 0) currentIndex++;
  let row = Math.floor(currentIndex / offset2);
  let mod = Math.floor(currentIndex - row * offset2);
  return (mod * offset1 + row) % totalSteps;
}

function getNextHslColorString(currentIndex, hslLightness) {
  let totalSteps = 18;
  currentIndex = shiftIndex(currentIndex, 4);
  let hue = Math.round((currentIndex / totalSteps) * 360.0);
  let hslSaturation = 50;
  return `hsl(${hue}, ${hslSaturation}%, ${hslLightness}%)`;
}

for (let offset = 1; offset <= Math.sqrt(18 * 2); offset++) {
  let o = {};
  for (let i = 0; i < 18; i++) {
    let j = shiftIndex(i, offset);
    // console.log(i, j);
    if (!o[j]) {
      o[j] = 1;
    } else {
      o[j]++;
    }
  }
  console.log(o);
  for (let i = 0; i < 18; i++) {
    if (!o[i]) {
      console.log(i);
    }
  }
}

 

[OpaK]

Oh , mathematisch gesehen geht diese Interleaving-Logik leider doch nur mit einer inneren Schleife, für alle beliebigen Werte...

Hier noch einmal neu zusammen mit einer probabilistischen Testfunktion:

function interleaveShiftIndex(totalSteps, offset, currentIndex) {
  let offset2 = Math.ceil(totalSteps / offset);

  let virtualIndex = 0;
  let validCount = 0;

  while (true) {
    let row = Math.floor(virtualIndex / offset2);
    let mod = virtualIndex % offset2;

    // Das ist die originale mathematische Generierung deines Rasters
    let target = mod * offset + row;

    // Wenn der Wert im echten Bereich liegt, ist er gültig
    if (target < totalSteps) {
      if (validCount === currentIndex) {
        return target;
      }
      validCount++;
    }

    virtualIndex++;
  }
}

(function test(rounds) {
  a: for (let i = 0; i < rounds; i++) {
    let totalSteps = 10 + Math.round(Math.random() * 20);
    let offset = 1 + Math.round(Math.random() * (totalSteps / 2 - 1));
    let counts = {};
    for (let j = 0; j < totalSteps; j++) {
      let sIndex = interleaveShiftIndex(totalSteps, offset, j);
      // console.log(j, sIndex);
      if (!counts[sIndex]) {
        counts[sIndex] = 1;
      } else {
        counts[sIndex]++;
      }
    }
    for (let key in counts) {
      if (counts[key] !== 1) {
        console.log('Error', totalSteps, offset, i, key, counts[key]);
        continue a;
      }
    }
    console.log('Ok', totalSteps, offset, i);
  }
})(100);

Die KI brauchte dafür mehrere Versuche, auch weil sie das Problem nicht sofort verstand.