Finden Sie eine Funktion mit Zyklen jeder Länge

11

Eine Funktion wird gesagt , ein haben Zyklus der Länge n , wenn es eine gibt x in seiner Domäne , so dass f n (x) = x und f m (x) ≠ x für 0 <m <n , wobei der Exponent n Bezeichnet n - Falte Anwendung von f . Beachten Sie, dass ein Zyklus der Länge 1 ein fester Punkt f (x) = x ist .

Ihre Aufgabe ist es, eine bijektive Funktion von den ganzen Zahlen zu sich selbst zu implementieren , die genau einen Zyklus jeder positiven Länge n hat . Eine bijektive Funktion ist eine Eins-zu-Eins-Entsprechung, dh jede Ganzzahl, die genau einmal zugeordnet ist. Genau einen Zyklus der Länge n zu haben bedeutet, dass es genau n verschiedene Zahlen x gibt, für die f n (x) = x und f m (x) ≠ x für 0 <m <n ist .

Hier ist ein Beispiel, wie eine solche Funktion um x = 0 aussehen könnte :

x     ... -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7 ...
f(x)  ...  2  4  6 -3 -1  1 -4  0 -2  5  7 -7 -6  3 -5 ...

Dieser Auszug enthält Zyklen der Länge 1 bis 5 :

n   cycle
1    0
2   -2  1
3   -4 -3 -1
4   -5  6  3  7
5   -7  2  5 -6  4
...

Beachten Sie, dass ich oben "Funktion" nur im mathematischen Sinne verwende. Sie können entweder eine Funktion oder ein vollständiges Programm in der Sprache Ihrer Wahl schreiben, sofern eine einzelne (vorzeichenbehaftete) Ganzzahl als Eingabe verwendet und eine einzelne (vorzeichenbehaftete) Ganzzahl zurückgegeben wird. Wie üblich können Sie Eingaben über STDIN, Befehlszeilenargument, Funktionsargument usw. und Ausgaben über STDOUT, Funktionsrückgabewert oder Funktionsargument (out) usw. vornehmen.

Natürlich unterstützen viele Sprachen (leicht) keine Ganzzahlen mit beliebiger Genauigkeit. Es ist in Ordnung, wenn Ihre Implementierung nur für den Bereich des nativen Integer-Typs Ihrer Sprache funktioniert, sofern dieser mindestens den Bereich [-127, 127] abdeckt und für beliebige Ganzzahlen funktioniert, wenn der Integer-Typ der Sprache durch einen beliebigen Integer-Typ ersetzt wird. Präzisions-Ganzzahlen.

Es gelten die Standardregeln für .

Martin Ender
quelle
2
Eng verwandt. Obwohl die Unterschiede gering erscheinen, implizieren sie, dass keiner der alten Ansätze ohne wesentliche Modifikation funktioniert, und insbesondere denke ich nicht, dass der Siegeransatz aus dieser Herausforderung überhaupt angepasst werden kann.
Martin Ender
"hat genau einen Zyklus jeder Länge", "hat viele Zyklen jeder Länge": Ist dies der einzige Unterschied, der sich von anderen unterscheidet?
Abr001am
@ Agawa001 Das ist ein Unterschied, der andere ist, dass es bei der anderen Herausforderung um Funktionen für die positiven ganzen Zahlen geht, während diese Herausforderung nach einer Funktion für alle ganzen Zahlen fragt.
Martin Ender
1
Ich denke, Ihre Definition des Zyklus muss beinhalten, dass n minimal ist. Andernfalls zählt Ihr Zyklus der Länge 2 auch als Ihr Zyklus der Länge 4 und 6 und so weiter.
xnor
@xnor Whoops, guter Punkt.
Martin Ender

Antworten:

2

Pyth, 27 18 Bytes

_h?gQ0^2Q*.5@,Q-xh

Erläuterung (Pyth wird Qmit der Eingabe-Ganzzahl initialisiert ):

_                       negative of (
                          (
  ?gQ0                      if Q >= 0:
      ^2Q                     2**Q
                            else:
         *.5                  half of
            @        Q          element Q (modulo list length) in
             ,                    the two element list [
              Q                     Q,
                 hQ                 ((Q plus 1)
                x  Q                 XOR Q)
               -    Q               minus Q
                                  ]
 h                        ) plus 1
                        )

Dies hat Zyklen

(–1)
(0, –2)
(1, –3, –4)
(2, –5, –7, –6)
(3, –9, –13, –11, –8)
(4, - 17, -25, -21, -15, -10)
(5, -33, -49, -41, -29, -19, -12)
(6, -65, -97, -81, -57, -37, -23, -14)
(7, -129, -193, -161, -113, -73, -45, -27, -16)
(8, -257, -385, -321, -225 , –145, –89, –53, –31, –18)
(9, –513, –769, –641, –449, –289, –177, –105, –61, –35, –20)

Der Zyklus der Länge n ist gegeben durch

( n - 2,
−2 ^ ( n - 2) ⋅1 - 1,
−2 ^ ( n - 3) ⋅3 - 1,
−2 ^ ( n - 4) ⋅5 - 1,
…,
−2 ^ 2 ⋅ (2 · n - 7) - 1,
−2 ^ 1⋅ (2 · n - 5) - 1,
−2 ^ 0⋅ (2 · n - 3) - 1).

Jede ganze Zahl k ≥ −1 erscheint als erstes Element des ( k + 2) -Zyklus. Für jede ganze Zahl k <−1 können wir 1 - k = 2 ^ i ⋅ (2⋅ j + 1) für einige i , j ≥ 0 eindeutig schreiben ; dann erscheint k als das ( j + 2) -te Element des ( i + j + 2) -Zyklus.

Anders Kaseorg
quelle
5

MATL , 47 Bytes

E|G0<-QXJ:tQ*2/0hStJ<f0))Q2MQ)&:J6M-)2/ttk>Eq*k

Probieren Sie es online aus!

Allgemeine Erklärung

Die folgende Funktion 2 entspricht der Antwort von @ Sp3000 auf die entsprechende Herausforderung. Vielen Dank an @ Agawa001 für das Bemerken.

Die Funktion ist die Zusammensetzung von drei:

  1. Bijektion von Z (die ganzen Zahlen) nach N (die natürlichen).
  2. Bijektion von N nach N mit der gewünschten Charakteristik (ein Zyklus jeder Länge).
  3. Umkehrung der Funktion 1.

Die Funktionen 1 und 3 werden verwendet, weil es (glaube ich) einfacher ist, das gewünschte Verhalten in N als in Z zu erreichen .

Funktion 2 lautet wie folgt: Die obere Zeile ist die Domäne, die untere Zeile ist die Codomäne. Kommas werden aus Gründen der Übersichtlichkeit verwendet:

1,  2  3,  4  5  6,  7  8  9  10  ...
1,  3  2,  6  4  5, 10  7  8   9  ...

Der erste Block (von oben 1nach unten 1) ist ein Zyklus der Länge 1. Der zweite (von 2 3bis 3 2) ist ein Zyklus der Länge 2 usw. In jedem Block ist der untere Teil (Bild der Funktion) der obere Teil kreisförmig verschoben einen Schritt nach rechts.

Funktion 1 ist wie folgt:

 -5  -4  -3  -2  -1   0  +1  +2  +3  +4  ...
+10  +8  +6  +4  +2  +1  +3  +5  +7  +9  ...

Funktion 3 ist dieselbe wie 1, wobei die beiden Zeilen vertauscht sind.

Beispiele

Das Bild von 3ist -5. Zuerst 3wird 7durch Funktion 1 abgebildet ; wird dann durch Funktion 2 7abgebildet 10; wird dann 10durch Funktion 3 auf -5` abgebildet.

Der Zyklus der Länge 1 ist 0. Der Zyklus der Länge 2 ist -1 1. Der Zyklus der Länge 3 ist -3 2 -2usw.

Code erklärt

Die Funktionen 1 und 3 sind unkompliziert.

Funktion 2 ermittelt den unteren Endpunkt des entsprechenden Eingabeblocks. Wenn zum Beispiel der Eingabe dieser Funktion ist 9es findet 7(siehe Blöcke oben). Anschließend wird der obere Endpunkt ausgewählt, der sich 10im Beispiel befindet. Die kreisförmige Verschiebung des Blocks wird dank der 1-basierten, modularen Indizierung von MATL erreicht.

         % FUNCTION 1
         % Implicit input
E|       % Multiply by two. Absolute value
G0<      % 1 if input is negative, 0 otherwise
-        % Subtract
Q        % Add 1
XJ       % Copy to clipboard J. Used as input to the next function

         % FUNCTION 2
:        % Range [1 2 ... J], where J denotes the input to this function
tQ*      % Duplicate, increment by 1, multiply
2/       % Divide by 2
0hS      % Prepend a 0. This is needed in case J is 0
tJ<f     % Duplicate. Find indices that are less than the input J
0)       % Pick the last index.
)        % Apply as index to obtain input value that ends previous block
Q        % Add 1: start of current block
2M       % Push the two arguments to second-to-last function call
Q)       % Add 1 and use as index: end of current block
&:       % Inclusive binary range: generate input block 
J        % Push J (input to function 2)
6M-      % Subtract start of block
)        % Apply as index (1-based, modular). This realizes the shifting

         % FUNCTION 3
2/       % Divide by 2
ttk>     % Duplicate. 1 if decimal part is not 0; 0 otherwise
Eq       % Multiply by 2, add 1
*        % Multiply
k        % Round down
         % Implicit display
Luis Mendo
quelle
das ist eine verdrehung der sp3000 s funktion oder?
Abr001am
@ Agawa001 Oh ist es? Ich habe die andere Herausforderung nicht gesehen. Ich werde einen Blick darauf werfen
Luis Mendo
Oh. Es ist definitiv so. Zumindest stellt das klar, dass meine Argumentation, wenn auch nicht original, richtig war :-)
Luis Mendo
Es ist überraschend, wie eng mehrere Gedanken miteinander verbunden sind, um enge Ideen auszustrahlen.
Abr001am
4

Python 2, 55 Bytes

g=lambda n,k=1:n/k and~g(~n+k*(n>0),k+1)+k*(n>0)or-~n%k

59 Bytes:

g=lambda n,k=1:n<0and~g(~n,2)or n/k and k+g(n-k,k+2)or-~n%k

Erstellt die Zyklen

[0]
[-1, -2]
[1, 2, 3]
[-3, -4, -5, -6]
[4, 5, 6, 7, 8]
...

Geändert von meiner Lösung auf der früheren Herausforderung , die von der Sp3000-Konstruktion modifiziert wurde .

Die Funktion

g=lambda n,k=1:n/k and k+g(n-k,k+2)or-~n%k

macht ungerade Zyklen von nicht negativen Zahlen

[0]
[1, 2, 3]
[4, 5, 6, 7, 8]
...

Um die richtige Zyklusgröße zu finden k, verschieben Sie die Eingabe num, k=1,3,5,7,...bis das Ergebnis im Intervall liegt [0,k). Durchlaufen Sie dieses Intervall mit der Operation n->(n+1)%kund machen Sie dann alle an der Eingabe vorgenommenen Subtraktionen rückgängig. Dies wird rekursiv von implementiert k+g(n-k,k+2).

Jetzt brauchen wir das Negative, um die geraden Zyklen zu machen. Beachten Sie, dass wir Zyklen mit gerader Größe erhalten , wenn wir gzunächst mit k=2in änderng

[0, 1]
[2, 3, 4, 5]
[6, 7, 8, 9, 10, 11]
...

Diese werden über das Bit-Komplement negativ ~. Wenn nalso negativ ist, bewerten wir einfach g(n)als ~g(~n,2).

xnor
quelle
Ich weiß nicht, ob es hilft, aber eine andere Art der Berechnung kscheint zu sein Math.floor(Math.sqrt(n))*2+1.
Neil
@Neil Ich habe versucht, die Grenzen und Zyklusgrößen arithmetisch zu bestimmen und sogar die gesamte Berechnung auf diese Weise durchzuführen, aber diese Ausdrücke sind in Python langwierig und ich fand die Rekursion kürzer.
xnor
3

Python 3, 110 Bytes

Ich habe immer noch nicht herausgefunden, wie ich dort ein Lambda bekommen kann

Wenn n eine Dreieckszahl ist [1,3,6,10,15,21,28 usw.], dann ist f (n) die Reihenfolge in der Liste multipliziert mit der negativen. Wenn die Zahl negativ ist, geben Sie 1 + die nächstkleinere Dreieckszahl. sonst inkrementieren.

Beispiel: 5 ist keine Dreieckszahl, also addiere 1.

Bei der nächsten Iteration haben wir 6. 6 ist eine Dreieckszahl und es ist die 3. in der Liste, also kommt -3 heraus.

Das Programm gibt diese Listen

Länge 1: [0]

Länge 2: [1, -1]

Länge 3: [2,3, -2]

Länge 4: [4,5,6, -3]

Länge 5: [7,8,9,10, -4]

x=int(input())
if x<0:print((x**2+x)/2+1)
else:
 a=((8*x+1)**.5-1)/2
 if a%1:print(x+1)
 else:print(-a)

Bearbeiten: Nochmals vielen Dank an @TuukkaX für das Entfernen überschüssiger Zeichen.

Magenta
quelle
1
Sie könnten 0.5zu .5und input('')zu wechseln input().
Yytsi
2

Python 3, 146 Bytes

Für jede Zahl größer als 0 gibt es gerade Schleifen (len 2,4,6,8 ...) und ungerade Schleifen kleiner als 0 (1,3,5,7). 0 ist 0 zugeordnet.

(-3, -2, -1), (0), (1,2), (3,4,5,6)

Karten zu

(-2, -1, -3), (0), (2,1), (6,3,4,5)

f=lambda x:1+2*int(abs(x)**.5)if x<1 else 2*int(x**.5+.5)
x=int(input());n=f(x)
if x>0:b=n*(n-2)/4
else:b=-((n+1)/2)**2
print(b+1+(x-b-2)%n)

Bearbeiten: @TuukkaX hat 8 Bytes von der vorherigen Lösung entfernt. Und noch 3.

Magenta
quelle
1
Ich denke, Sie können ein Leerzeichen vor der if-Anweisung in der ersten Zeile entfernen. Und mikönnte in etwas kleineres geändert werden, wie z b.
Yytsi
Hier ist das gleiche Programm, das gespielt wird:f=lambda x:1+2*int(abs(x)**0.5)if x<1 else 2*int(x**0.5+0.5) x=int(input()) n=f(x) if x>0:b=n*(n-2)/4 else:b=-((n+1)/2)**2 print(b+1+(x-b-2)%n)
Yytsi
1
Danke, @TuukkaX. Ich habe die 2-stellige Variable 'mi' vergessen.
Magenta
1
Ich habe auch input('')zu input(). Die Anführungszeichen sind nutzlos, da wir nichts auf die Konsole drucken müssen, wenn wir nur die Eingabe erhalten möchten.
Yytsi
1
Noch kürzer. Die Nullen vor den Punkten wurden entfernt. f=lambda x:1+2*int(abs(x)**.5)if x<1 else 2*int(x**.5+.5) x=int(input());n=f(x) if x>0:b=n*(n-2)/4 else:b=-((n+1)/2)**2 print(b+1+(x-b-2)%n)
Yytsi
2

Matlab (423)

function u=f(n),if(~n)u=n;else,x=abs(n);y=factor(x);for o=1:nnz(y),e=prod(nchoosek(y,o)',1);a=log(x)./log(e);b=find(a-fix(a)<exp(-9),1);if ~isempty(b),k=e(b);l=fix(a(b));break;end;end,if(abs(n)==1)k=2;l=0;end,if(k==2)l=l+1;x=x*2;end,e=dec2base(l,k)-48;o=xor(e,circshift(e,[0 1]));g=~o(end);if(~o|nnz(o==1)~=numel(e)-g),u=n*k;else,if((-1)^g==sign(n)),u=sign(n)*k^(base2dec([e(2:end-1) 1]+48,k)-(k==2));else,u=n*k;end,end,end
  • Nicht konkurrierend, weil es einen guten Rekord bricht, für das letzte Ranking kondidiert zu sein, während ich mich bemühe, es so kurz wie möglich zu halten.

  • Einige nicht-sensorische Fehler in Bezug auf die Genauigkeit in Matlab, die ich nur herausfinden konnte, wenn ich meinen Code sarkatistisch groß machte. Andererseits war die Zuordnung, für die ich mich entschied, in Bezug auf Hauptfaktoren und n-ary Logarithmus.

Ausführung

 f(2)

 1

 f(1)

 2

 f(-2)

 -4

 f(-4)

 -8

 f(-8)

 -1

 f(0)

 0



 ----------------------------

Erläuterung

  • Zunächst wusste ich, dass jede Zahl als Produkt von Exponenten von Primzahlen N=e1^x1*e2^x2...aus dieser Basis geschrieben werden kann. Ich entschied mich, Bilder von Zyklen abzubilden, Cdie aus dem größten Exponenten des kleinsten Faktors (nicht unbedingt der Primzahl) extrahiert werden, dessen perfekte Potenz N ist .

  • in einfacheren Worten, N=P^xwenn P die kleinste perfekte Wurzel ist, xbezeichnet genau zwei wesentliche Terme für den Zyklus: x=Ʃ(r*P^i)Ein Term Pist die Basis des Zyklus sowie eine perfekte Wurzel für die Hauptzahl N und kist der Grad des Zyklus C=p^k, wobei ivariiert zwischen 1 und k, wird der Koeffizient rfür jedes folgende Vorbild um 1 erhöht und durch P-1 begrenzt, bis alle Koeffizienten auf r = 1 gesetzt sind, also bewegen wir uns zum Beginn dieses Zyklus.

  • Um Kollisionen zwischen Zyklen zu vermeiden, ist die Wahl der Exponentiation von Primzahlen anstelle ihrer Produkte genau, da als Beispiel für zwei Zyklen von Basen 3und 2einem Treffpunkt zwischen ihnen 3*2dies vermieden werden kann, da ein Zyklus durch seinen Grad mehr als seinen definiert wird Basis, und für den Treffpunkt gibt es einen weiteren Zyklus von Basis 6und Grad 1.

  • Negative Zahlen stellen eine Ausnahme dar, da ich ungerade Grade für negative Zahlen und gerade Grade für den Rest reserviert habe. Wie ?

    Für jede in einen Zyklus eingebettete Zahl N P^kwird geschrieben P^(a0*P^i0+a1*P^i1+...), dass die Menge (a0*P^i0+a1*P^i1+...)in P-ary-Basis als transaltiert a0,a1,....wird, um diesen Punkt zu verdeutlichen, wenn (p = 2) die Sequenz in binärer Basis sein muss. Wie vorab bekannt ist, ohne die Bedingung für positive / negative Grade und die Ausnahme (+/- 1) festzulegen, befindet sich eine Zahl N kgenau dann an den Rändern eines Gradzyklus, wenn die Sequenz Aals 1111..{k+1}..10oder 111..{k}..1für alle Basen geschrieben ist, andernfalls Es ist keine Drehung erforderlich, so dass durch Zuweisen einer negativen / positiven Bedingung für einen jeweiligen ungeraden / geraden Grad k/k'für beide eine ungerade Sequenz in der Form geschrieben wird 101..{k}..100, eine gerade Sequenz in der Form 101..{k'}..10für eine Anfangskante eines jeweils negativen / positiven Zahlenzyklus geschrieben wird .

    Beispiel:

    Wenn man eine Zahl N=2^10nimmt x=10=2^1+2^3, die Sequenz A geschrieben ist A=1010, symptomatisiert diese Art von Sequenz eine endliche Flanke des positiven Zahlenzyklus, das heißt C=2^3, das nächste Bild ist das der Anfangskante, A=011das heißt 8, aber indem man dieses Ergebnis auf (+ / standardisiert) -) 1 Ausnahme 2^10/2wird zugeordnet 8/2und das vorherige Bild darf nicht gedreht werden.

    Wenn man eine Zahl N=-3^9nimmt x=9=3^2, wird die Folge A geschrieben A=100, diese Art von Folge symptomatisiert eine endliche Flanke des negativen Zahlenzyklus, das heißt C=3^1, das nächste Bild ist das der Anfangskante, A=01das heißt 3, aber durch Anpassen dieses Ergebnisses an negativ / positiv Zustandskarten -3^9zu -3.

  • Für das Paar (-/+)1hatte ich vor, es innerhalb einer Anzahl von Zyklusbasen einzudringen 2, in dem Deckmantel, dass eine gewöhnliche Folge von zyklischen Gruppen {2,4}{8,16,32,64}..in einer anderen Form gebildet wird {1,2}{4,8,16,32}.., dies verhindert den Verlust vorheriger Elemente, und die durchgeführte Opeation verschiebt sich nur mit dem Knallen ein neues Element in.


Ergebnisse:

Führen Sie dieses kleine Codeblatt aus, um die ersten vernünftigen Bereiche zyklischer Zahlen zu überprüfen:

for (i=1:6) 
index=1;if(max(factor(i))>=5) index=0;end
for ind=0:index
j=f(((-1)^ind)*i); while(((-1)^ind)*i~=j)fprintf('%d ',j);j=f(j);end,fprintf('%d \n',(-1)^ind*i),pause,end,
end

Dies führt zu diesen Ergebnissen

 2 1 
 -2 -4 -8 -1 
 1 2 
 -4 -8 -1 -2 
 9 27 3 
 -9 -27 -81 -243 -729 -2187 -6561 -19683 -3 
 8 16 32 64 128 256 512 4 
 -8 -1 -2 -4 
 25 125 625 3125 5 
 36 216 1296 7776 46656 6 
 -36 -216 -1296 -7776 -46656 -279936 -1679616 -10077696 -60466176 -362797056 -2.176782e+009 -1.306069e+010 ??? Error using ==> factor at 27

Der letzte ist ein Segmentierungsfehler, der jedoch in den Standardbereich für vorzeichenbehaftete Ganzzahlen [-127,127] passt.

Abr001am
quelle
Ich habe diese Technik vor einiger Zeit verwendet, um Hash-Funktionen in einem meiner alten C-Programme zu definieren. Sie funktioniert einwandfrei!
Abr001am
0

JavaScript (ES6), 73 Byte

f=(n,i=0,j=0,k=0,l=1,m=i<0?-i:~i)=>n-i?f(n,m,k++?j:i,k%=l,l+!k):++k-l?m:j

Zählt die Sequenz (0, -1, 1, -2, 2, -3, 3, ...) auf, bis sie gefunden wird n, und zählt dabei die Zyklen. ienthält den aktuellen Eintrag; jenthält den Beginn des aktuellen Zyklus, kden Index innerhalb des Zyklus, ldie Länge des aktuellen Zyklus und mden nächsten Eintrag in der Sequenz. Sobald wir gefunden nhaben, nehmen wir, job wir am Ende eines Zyklus sind oder mnicht.

Neil
quelle