Każda możliwa długość cyklu

21

Można powiedzieć, że funkcja (lub program), która pobiera dane wejściowe i dostarcza dane wyjściowe, ma cykl, jeśli wielokrotne wywoływanie funkcji na swoim wyjściu ostatecznie osiągnie pierwotny numer. Na przykład weź następującą funkcję:

Input:  n    1 2 3 4 5 6
Output: f(n) 5 7 1 3 4 9

Jeśli zaczniemy n=1, f(n)=5, f(f(n))=f(5)=4, f(f(f(n)))=f(4)=3, f(f(f(f(n))))=f(3)=1.

To jest napisane (1 5 4 3). Ponieważ w tej pętli znajdują się 4 unikalne liczby, jest to cykl o długości 4.


Twoim zadaniem jest napisanie programu lub funkcji, która ma cykle o każdej możliwej długości. Oznacza to, że musi istnieć cykl o długości 1, o długości 2 i tak dalej.

Ponadto, twoja funkcja / program musi być od dodatnich liczb całkowitych do dodatnich liczb całkowitych i musi być bijectywny , co oznacza, że ​​musi być dokładnie jedna wartość wejściowa dla każdej możliwej wartości wyjściowej, ponad wszystkimi liczbami całkowitymi dodatnimi. Innymi słowy, funkcja / program musi obliczyć permutację dodatnich liczb całkowitych.


Szczegóły: Dowolny standardowy system wejścia / wyjścia jest dozwolony, w tym STDIN, STDOUT, argument funkcji, return itp. Zabronione są standardowe luki.

Nie musisz martwić się o ograniczenia swoich typów danych - powyższe właściwości muszą posiadać tylko przy założeniu, że intalbo floatmoże posiadać dowolną wartość, na przykład.

Nie ma ograniczeń w zachowaniu funkcji na wejściach, które nie są dodatnimi liczbami całkowitymi, a te wejścia / wyjścia zostaną zignorowane.


Punktacja to golf w bajtach, wygrywa najkrótszy kod.

isaacg
źródło
„musi istnieć cykl o długości 1, o długości 2 itd.” Należy to interpretować jako „musi istnieć co najmniej cykl o długości 1, co najmniej jeden o długości 2 itd.” lub „musi być być dokładnie cyklem o długości 1, jednym o długości 2 itd. ”.
Bakuriu
@ Bakuriu Co najmniej jeden cykl każdej dodatniej długości.
isaacg

Odpowiedzi:

11

Pyth, 11 8 bajtów

.<W-0zz1

O wiele bardziej nudne niż moja poprzednia odpowiedź.

Każda liczba zawierająca 0 cyfr jest odwzorowywana na siebie. Każdy inny numer odwzorowuje na liczbę, której cyfry są obrócone o 1. Więc na przykład:

1 -> 1
10 -> 10
15 -> 51 -> 15
104 -> 104
123 -> 231 -> 312 -> 123
orlp
źródło
8

Python 2, 56 55 54 bajtów

n=input()
a=b=1
while a+b<=n:a+=b;b+=1
print(n+~a)%b+a

Oto pierwsze 21 wyników:

[1, 3, 2, 6, 4, 5, 10, 7, 8, 9, 15, 11, 12, 13, 14, 21, 16, 17, 18, 19, 20]

Wzór jest oczywisty, jeśli podzielimy listę na mniejsze części:

 1    2  3    4  5  6    7  8  9  10    11  12  13  14  15    16  17  18  19  20  21
[1]  [3, 2]  [6, 4, 5]  [10, 7, 8, 9]  [15, 11, 12, 13, 14]  [21, 16, 17, 18, 19, 20]
Sp3000
źródło
Cholera, tego też chciałem się spodziewać, ale z zamkniętą formą.
orlp
1
Interesujące ... wartości a są zgodne z sekwencją A000124 . Ale chyba już o tym wiedziałeś: P
Kade
Zauważ, że ta sekwencja to oeis.org/A066182 .
orlp
8

Pyth, 25 bajtów

+hK/*J/h@h*8tQ2 2tJ2%-QKJ

Jest to taka sama sekwencja jak @ Sp3000, ale z zamkniętą formą. Formularz zamknięty to:

M (n) = piętro ((1 + sqrt (1 + 8 * (n - 1))) / 2) B (n) = M (n) * (M (n) - 1) / 2 f (n) = B (n) + ((n - B (n) + 1) mod M (n))

orlp
źródło
5

Python3, 40 bajtów

n=input();print([n[1:]+n[0],n]['0'in n])

Każda liczba zawierająca 0 cyfr jest odwzorowywana na siebie. Każdy inny numer odwzorowuje na liczbę, której cyfry są obrócone o 1. Więc na przykład:

1 -> 1
10 -> 10
15 -> 51 -> 15
104 -> 104
123 -> 231 -> 312 -> 123
orlp
źródło
1
Déjà vu! Fajnie jest zobaczyć to w dwóch językach!
Denham Coote,
3

Rubin, 22 + 1 = 23

Z flagą wiersza polecenia -puruchom

~/(.)(.?)/
$_=$1+$'+$2

Podany jako wejście ciąg znaków reprezentujący liczbę (bez końca nowej linii), utrzymuje pierwszą cyfrę na stałym poziomie, a następnie obraca resztę w lewo, a więc 1234staje się 1342.

Można go zmniejszyć do 21 znaków za pomocą $_=$1+$'+$2if/(.)(.)/, ale drukuje ostrzeżenie.

histocrat
źródło
3

Rubin, 16 + 1 = 17

Z flagą wiersza polecenia -puruchom

$_=$_[/.0*$/]+$`

Jest to bardziej skomplikowana funkcja niż moja inna odpowiedź, ale zdarza się, że jest bardziej golfowa (i tolerancyjna dla nowych linii). Pobiera ostatnią niezerową cyfrę wejścia plus wszelkie zera końcowe i przenosi ją na początek liczby. Tak się 9010300staje3009010 . Dowolna liczba z n niezerowymi cyframi będzie częścią cyklu o długości n.

Wejście to ciąg znaków w dowolnej bazie poprzez STDIN, wyjście to ciąg znaków w tej bazie.

histocrat
źródło
2

Python, 43

Odwrotnością funkcji SP3000 jest realizowany rekurencyjnie.

f=lambda n,k=1:n>k and k+f(n-k,k+1)or n%k+1

Funkcja jest jednym cyklem, po którym następuje dwa cykle, po których następuje trzy cykl, ...

(1)(2 3)(4 5 6)(7 8 9 10)(11 12 13 14 15)...

Operacja n%k+1działa jak k-cykl na liczbach 1..k. Aby znaleźć odpowiedni ksposób użycia, przesuń wszystko w dół o k=1, następnie k=2itd n<=k. Aż do .

xnor
źródło
2

Pyth, 15 bajtów

Najkrótsza jak dotąd odpowiedź, która wykorzystuje operacje numeryczne zamiast operacji na łańcuchach.

.|.&Q_=.&_=x/Q2

    Q                input
            /Q2      input div 2
           x   Q     that XOR input
          =          assign that to Q
         _           negate that
       .&       Q    that AND Q
      =              assign that to Q
     _               negate that
  .&                 input AND that
.|               Q   that OR Q

Wpływ tej funkcji na reprezentację binarną polega na przedłużeniu bloku z prawej strony 1s do następnego 0; lub jeśli nie ma 0, aby zresetować go do jednego 1:

10010110100000 ↦  
10010110110000 ↦  
10010110111000 ↦  
10010110111100 ↦  
10010110111110 ↦  
10010110111111 ↦
10010110100000  

Pyth, 26 bajtów, zabawny wariant

.|.&Q_h.&/Q2+Qy=.&/Q2_h.|y

    Q                           input
         /Q2                    input div 2
             Q                  input
                  /Q2           input div 2
                         yQ     twice input
                       .|  Q    that OR input
                     _h         NOT that
                .&              (input div 2) AND that
               =                assign that to Q
              y                 twice that
            +                   input plus that
       .&                       (input div 2) AND that
     _h                         NOT that
  .&                            input AND that
.|                          Q   that OR Q

Wykonuje powyższą operację jednocześnie dla wszystkich bloków 1s, nie tylko skrajnie po prawej stronie - nadal używając tylko operacji bitowych i arytmetycznych.

1000010001001 ↦
1100011001101 ↦
1110011101001 ↦
1111010001101 ↦
1000011001001 ↦
1100011101101 ↦
1110010001001 ↦
1111011001101 ↦
1000011101001 ↦
1100010001101 ↦
1110011001001 ↦
1111011101101 ↦
1000010001001
Anders Kaseorg
źródło
1

Swift 1.2, 66 bajtów

func a(b:Int){var c=0,t=1,n=b
while n>c{n-=c;t+=c++}
print(n%c+t)}
Input:  1,   2, 3,  4, 5, 6,   7, 8, 9, 10,   11, 12, 13, 14, 15
Output: 1,   3, 2,  5, 6, 4,   8, 9, 10, 7,   12, 13, 14, 15, 11
David Skrundz
źródło
1

Brachylog , 5 bajtów

∋0&|↺

Wypróbuj online!

Port odpowiedzi Pyth @ orlp. Wychodzi prosto i schludnie:

∋0    % If input contains a 0 (since input is a single number, "contains" ∋ treats it as an array 
      %   of its digits, so this means "if any of input's digits are 0")
&     % Then output is the input
|     % Otherwise
↺     % Circularly shift the input once, and unify that with the output

Początkowo chciałem przenieść rozwiązanie @ Sp3000 do języka Python, ale zajęło to aż 23 bajty :

⟧∋B-₁⟦++₁A≤?;A--₁;B%;A+

Wypróbuj online!

sundar - Przywróć Monikę
źródło
0

JavaScript (ES6), 43 bajty

f=(n,i=1,j=1)=>n>j?f(n,++i,j+i):n++<j?n:n-i
Neil
źródło
0

Matlab (189)

  function u=f(n),if(~n|n==1)u=n;else,u=n;y=factor(n);z=y(y~=2);if ~isempty(z),t=y(y~=max(y));if isempty(t),u=y(end)*2^(nnz(y)-1);else,g=max(t);e=primes(g*2);u=n/g*e(find(e==g)+1);end,end,end

  • Funkcja:

    Odwzorowuje dowolną liczbę całkowitą według jej liczb pierwszych, jeśli liczba jest równa zero lub jest podzielona na 2 lub 1, liczba jest odwzorowywana na siebie, w przeciwnym razie wybieramy największy czynnik pierwszy z tej liczby, a następnie zwiększamy pozostałe różne czynniki pierwsze o najbliższą wartość większy współczynnik pierwszy, aż osiągniemy liczbę, biggest_prime^nktóra njest sumą wszystkich wykładników wszystkich czynników, po osiągnięciu tej liczby, zwracamy się max_prime*2^(n-1)i odtwarzamy ten sam cykl ponownie.

Abr001am
źródło
0

Matlab (137)

  function u=h(n),if(~n|n==1)u=n;else,u=n;y=factor(n);z=y(y~=2);if~isempty(z),e=nnz(y);f=nnz(z);if(~mod(e,f)&e-f)u=n/2^(e-f);else,u=u*2;end

  • Nieco podobne podejście, polegające na pomnożeniu stopniowo dowolnej liczby, która nie jest równa {0,1,2 ^ n}, 2dopóki nie natkniemy się na wykładnik, 2którego można podzielić przez sumę wykładników innych czynników pierwszych. następnie przechodzimy do początku cyklu dzieląc przez 2^(sum of exponents of other primes). pozostałe liczby są zmapowane do siebie.
Abr001am
źródło