Bijektive Abbildung (Selbstabbildung) mithilfe des %-Operators in JS/ES

Anon-81275

Moin, ich hätte eine Frage.

Wie müsste der folgende Term für j umgestellt werden, damit eine bijektive Abbildung, jeweils mit einem Versatz um 4, entsteht? Bislang fehlt die 13, aber die 0 kommt zweimal vor. Ginge das nur mit einer for-Schleife?

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

SeppJ

(i+4) % 18?

Anon-81275

@SeppJ sagte in Bijektive Abbildung mithilfe des %-Operators in JS/ES:

(i+4) % 18?

Theoretisch ja. Aber ich hatte an ein Raster gedacht (jeweils 4 weiter):

0 4 8 12 16
1 5 9 13 17
2 6 10 14
3 7 11 15

Jetzt sieht man vielleicht das Problem: Es gibt "Leerplätze".

Für beliebige n (momentan 18) und m (momentan 4) komme ich da auf keinen grünen Zweig.

Und die KI möchte eine zusätzliche Schleife einführen.

SeppJ

Jetzt verstehe ich erst, was du möchtest. Da braucht man keine zweite Schleife, sondern Mathematik der 3. Klasse. Tolle KI

Ich weiß nicht, wie man in Javascript eine Integerdivision schreibt. Also eine Division, wo man nur den ganzzahligen Teil einer Integerdivision bekommt, das Gegenstück von modulo (%). Das musst du selber herausfinden, gibt es ganz sicher. Mal angenommen // wäre diese Integerdivision (Merke // ist es ganz bestimmt nicht, das weiß selbst ich, dass das ein Kommentar in JS ist), dann wäre die Formel für beliebige n und m (und i von 0 bis m):

(i * n) % m + (i * n) // m

Beispiel für dein n=4 und m=18:

Okay, ein Drittklässler käme da wahrscheinlich nicht alleine drauf, aber er könnte es immerhin alles ausrechnen

PS: Ich schätze dein Math.floor(i / 4) ist effektiv schon die Integerdivision von i und 4. Gibt es da nichts besseres? Aber zu Not tut es das auch, hier dann natürlich Math.floor((i * n) / m)

Anon-81275

Dein Ansatz ist gut... funktioniert aber nicht für beliebige "n" und "m":

function interleaveShiftIndex(totalSteps, offset, currentIndex) {
  return (
    ((currentIndex * offset) % totalSteps) +
    Math.floor((currentIndex * offset) / totalSteps)
  );
}

(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);

... und 3. Klasse ist bei mir schon länger her.

Anon-81275

@SeppJ sagte in Bijektive Abbildung mithilfe des %-Operators in JS/ES:

13 18

18 darf auch nicht vorkommen, denn der Definitionsbereich ist zugleich auch der Wertebereich.

Edit: Selbstabbildung, Endomorphismus bzw. Permutation.

SeppJ

Ich und mein großes Maul

Das ist ja ekelhaft im allgemeinen Fall, aber das musste ich heute Abend noch durchtüfteln, nachdem ich mich über die schlechten Mathekenntnisse der KI lustig gemacht habe.Jetzt sollte hoffentlich alles passen, egal welche m und n.

Leider habe ich einen allerletzten Ausdruck, wo ich eine Fallunterscheidung habe, da ich eine Stufenfunktion brauche, die 0 für x < 0 und 1 für x >= 0 ist. Das kann man nicht mehr mit primitiven Operationen wie Plus, Minus, Mal, Geteilt schreiben, da muss man irgendwie verzweigen. Du kannst das entweder so machen wie ich, mit einem expliziten if, oder das irgendwie verstecken hinter irgendwelchen sign oder abs Funktionen (Was immer Javascript da so hat), die dann intern aber auch nix anderes machen.

Der finale Ausdruck ist lang. Es gäbe auch eine Erklärung, die wäre nochmals viel länger, aber ich denke mit ausreichendem Draufgucken kann man verstehen, was da vor sich geht. Das schafft dann aber kein Drittklässler mehr, vermutlich auch die meisten Abiturienten nicht.

Da ich das in Python ausgekügelt habe, und keine Lust habe, das jetzt auch noch in LaTeX zu setzen kopiere ich einfach mein Testprogramm hier. Das sollte trivial nach Javascript übersetzbar sein, und Python ist so einfach, da muss ich wohl nicht erklären, was die Syntax bedeutet:

import math


def H(x):
    # Stufenfunktion, wie auch immer du die in Javascript mit den erlaubten Mitteln machen würdest
    return 1 if x >= 0 else 0


def func(i, n, m):
    L = math.floor(m / n)
    s = m - n * L
    T = s * (L + 1)
    J = H(i - T)  # Hier müssen wir feststellen, ob i-T >= 0 ist (d.h. ob i >= T)
    return n * ((i - T * J) % (L + 1 - J)) + (1 - J) * math.floor(i / (L + 1)) + J * (s + math.floor((i - T) / L))


n = 4
m = 18

for i in range(m):
    print(i, func(i, n, m))

Die Geschichte mit dem J ist, dass ich es als persönliche Herausforderung gesehen habe, kein if zu nutzen. Das ganze wäre viel einfacher, wenn man mit if i < T einfach zwei verschiedenen Formeln nutzen würde.

Die Grundidee ist, dass wir uns ausrechnen, wie viele lange Zyklen wir haben. Das ist das s . Und vor allem, wo der Übergang (T) von den langen zu den kurzen ist. Bei n = 4 und m = 18 haben wir 2 lange Zyklen mit mit 5 Werten, dann 2 kurze mit 4 Werten. Der Übergang ist daher bei i = 2 * 5 = 10.

Wenn i >= T ist, sind wir in einer kurzen Zeile. Mit diesem Wissen können wir dann den korrekten Wert innerhalb der Zeile konstruieren. Bei i < T haben wir Zyklen von Länge L + 1, ab i >= T ist die Länge L. Das ist alles in dem langen Ausdruck am Ende verpackt.

Die Ordnung der Zyklen ist natürlich willkürlich, man hätte genausogut auch anders ordnen können, aber ich mochte dass die Sequenz bei 0 mit 0 beginnt, und das schien mir die natürliche Ordnung von da an.