Zabawa z permutacjami

17

Kto nie lubi absolutnie permutacji, prawda? Wiem, że są niesamowici - tyle radości!

Cóż, dlaczego nie skorzystać z tej zabawy i uczynić go funner ?

Oto wyzwanie:

Biorąc pod uwagę dane wejściowe w dokładnej formie: nPrgdzie njest pobierana pula i rjest liczbą wyborów z tej puli ( ni rsą liczbami całkowitymi), wyprowadza / zwraca dokładną liczbę permutacji. Dla tych, którzy są nieco zardzewiali terminologią: Permutation, def. 2a .

Jednak tutaj pojawia się wyzwanie (sprawia, że ​​nie jest to zbyt łatwe):

Nie możesz używać żadnej wbudowanej biblioteki, frameworku lub metody dla swojej funkcji permutacji. Nie możesz używać metody silni, metody permutacji ani niczego w tym rodzaju; musisz wszystko napisać sam.

Jeśli potrzebne są dalsze wyjaśnienia, proszę nie wahaj się powiedzieć mi w komentarzach, a niezwłocznie podejmę odpowiednie działania.


Oto przykład we / wy:

Przykładowa funkcja to permute(String) -> int

Wejście:

permute("3P2")

Wynik:

6

To jest golf golfowy, więc wygrywa najkrótszy kod!

Daniel
źródło
2
Aww. Myślałem, że to wyzwanie dotyczy grup permutacyjnych . Fajne rzeczy. To też jest fajne i ściśle związane z grupami permutacji. Uwielbiam wyzwanie.
Justin,
Kiedy mówisz, że nie ma metod wbudowanych ani bibliotek, masz na myśli permutacje, czy cokolwiek innego? Czy mogę użyć wbudowanego, splitaby podzielić wejście na P? Co z funkcją, która konwertuje ciąg na liczbę?
xnor
3
Czy odpowiedzi mogą to zakładać 0 <= r <= n?
Peter Taylor,
1
@Dopapp Czy masz na myśli, że r nie jest większe niż n ?
Dennis,
1
@RetoKoradi - Przypuszczam, że starając się nie zmuszać większości plakatów do ponownej odpowiedzi, po prostu nie wolno ci używać żadnych metod / funkcji silnia lub permutacji.
Daniel

Odpowiedzi:

4

CJam, 15 14 bajtów

r~\;~\),>UXt:*

Wypróbuj online w interpretatorze CJam .

Jak to działa

r              e# Read a token ("nPr") from STDIN.
 ~             e# Evaluate. This pushes the numbers n, Pi and r on the stack.
  \;           e# Discard Pi.
    ~          e# Take the bitwise NOT of r. Pushes -(r+1).
     \)        e# Increment n.    
       ,       e# Turn n+1 into [0 ... n].
        >      e# Keep only the last r+1 elements.
         UXt   e# Replace the first element with 1.
               e# This avoid dealing with the egde case nP0 separately.
            :* e# Compute their product.
Dennis
źródło
4

Perl, 27 bajtów

#!perl -pl61
$\*=$`-$%++for/P/..$'}{

Licząc shebang jako 4, dane wejściowe są pobierane ze standardowego wejścia.


Przykładowe użycie

$ echo 3P2 | perl npr.pl
6

$ echo 7P4 | perl npr.pl
840
primo
źródło
Co to za opcja l61?
feersum
@feersum ustawia $\na 1(char 49, octal 61).
primo,
3

Haskell, 71 66 bajtów

p s|(u,_:x)<-span(/='P')s,(n,k)<-(read u,read x)=product[n-k+1..n]

Całkiem proste rzeczy: podziel na „P”, a następnie weź iloczyn między (n-k + 1) i n.

Dzięki nim za pomysł zastosowania strażników wzorów zamiast whereklauzuli, straciło 5 bajtów.

arjanen
źródło
2

Minkolang 0.11 , 13 25 19 bajtów

Dziękujemy Sp3000 za zasugerowanie tego!

1nnd3&1N.[d1-]x$*N.

Wypróbuj tutaj.

Wyjaśnienie

1        Push 1
n        Take integer from input (say, n)
n        Take integer from input (say, k); ignores non-numeric characters in the way
d3&1N.   Output 1 if k is 0
[   ]    Loop k times
 d1-     Duplicate top of stack and subtract 1
x        Dump top of stack
$*       Multiply all of it together
N.       Output as integer

Używa tego samego algorytmu jak Alexa: n P k= n(n-1)(n-2)...(n-k+1).

El'endia Starman
źródło
2

Julia, 63 58 48 bajtów

s->((n,r)=map(parse,split(s,"P"));prod(n-r+1:n))

Tworzy to nienazwaną funkcję, która akceptuje ciąg znaków i zwraca liczbę całkowitą. Aby to nazwać, nadaj mu nazwę, np f=s->....

Nie golfowany:

function f(s::AbstractString)
    # Get the pool and number of selections as integers
    n, r = map(parse, split(s, "P"))

    # Return the product of each number between n-r+1 and n
    return prod(n-r+1:n)
end

Wykorzystuje to fakt, że liczba permutacji wynosi n ( n -1) ( n -2) ... ( n - k +1).

Zaoszczędź 10 bajtów dzięki Glen O!

Alex A.
źródło
Nie ma potrzeby Int, więc możesz po prostu użyć map(parse,...).
Glen O
@GlenO Mój umysł został wysadzony w powietrze. Nie zdawałem sobie sprawy, Intże w tej sytuacji jest to konieczne. Dzięki wielkie!
Alex A.,
2

Narzędzia Bash + Linux, 33

jot -s\* ${1#*P} $[${1/P/-}+1]|bc

jottworzy sekwencję rliczb całkowitych rozpoczynającą się od n-r+1i oddziela je za pomocą *. To wyrażenie jest przesyłane potokowo do bcoceny arytmetycznej.

Cyfrowa trauma
źródło
1

MATLAB, 54 bajty

[n,r]=strread(input(''),'%dP%d');disp(prod((n-r+1):n))

Próbowałem go zmniejszyć, ale jedną z rzeczy, w których MATLAB jest naprawdę zły, jest uzyskiwanie danych wejściowych. Aby pobrać dwie liczby z ciągu wejściowego, potrzeba 32 znaków!

Dość oczywisty kod. Uzyskaj dane wejściowe w postaci, w %dP%dktórej% d jest liczbą całkowitą. Podziel to na ni r. Następnie wyświetl iloczyn każdej liczby całkowitej z zakresu n-r+1do n. Co ciekawe, działa to nawet dla xP0podania poprawnej odpowiedzi 1. Jest tak, ponieważ w MATLAB prod()funkcja zwraca 1, jeśli spróbujesz wykonać iloczyn pustej tablicy. Ilekroć rwynosi zero, zasięg będzie pustą tablicą, więc bingo dostajemy 1.


Działa to również doskonale z Octave . Możesz spróbować online tutaj .

Tom Carpenter
źródło
1

JavaScript, 59 57 bajtów

s=>(f=(n,k)=>k?(n- --k)*f(n,k):1,f.apply(f,s.split('P')))
Naouak
źródło
1

Java (594 - bajty)

import java.util.*;import java.lang.*;public class Perm {private String a;private static int[] nr=new int[2];private static int sum=1;Scanner in=new Scanner(System.in);public String input(){a=in.nextLine();return a;}public void converter(String a){this.a=a;String b=a.substring(0,1);String c=a.substring(2);nr[0]=Integer.parseInt(b);nr[1]=Integer.parseInt(c);}public int param(){for(int counter=0; counter < nr[1]; counter++){sum=sum*nr[0]--;}return sum;}public static void main(String args[]){Perm a;a=new Perm();String k=a.input();a.converter(k);int ans=a.param();System.out.println(ans);}}
Kamalnrf
źródło
1

J, 23 bajty

^!._1/@(".;._1)@('P'&,)

Anonimowa funkcja. Przykład:

   f =. ^!._1/@(".;._1)@('P'&,)
   f '10P4'
5040

Wyjaśnienie:

       (  ;._1)@('P'&,)   Split over 'P', and on each slice,
        ".                read a number.
      @                   Then,
^!._1/                    fold (/) with the built-in "stope function" (^!.k) for k=1.

Funkcja stope, której użyłem, może liczyć na liczenie jako wbudowane ... Opiera się ona gdzieś między ogólnością operatora mnożenia a specyfiką operatora silni.

Lynn
źródło
1

APL, 23

{{×/⍵↑⍳-⍺}/-⍎¨⍵⊂⍨⍵≠'P'}

Bierze ciąg jako argument. Wyjaśnienie:

              ⍵⊂⍨⍵≠'P'  ⍝ Split by 'P'.
           -⍎¨          ⍝ Convert to numbers and negate making a vector (−n −r)
 {       }/             ⍝ Reduce it by a defined function, which
      ⍳-⍺               ⍝ makes a vector of numbers from 1 to n (⍺)
    ⍵↑                  ⍝ takes r last elements (⍵←−r)
  ×/                    ⍝ and multiplies them together.
użytkownik46915
źródło
Która APL to jest? Otrzymuję błąd w mojej kopii Dyalogu.
lirtosiast
1
@ThomasKwa Użyj ⎕ML←3w Dyalogu.
user46915,
1

Python 2, 66

def f(s):a,b=map(int,s.split('P'));P=1;exec"P*=a;a-=1;"*b;print P

Całkiem proste. Przetwarza wprowadzoną liczbę jako a,b. Utrzymuje działający produkt jako Ppomnożony przez pierwsze bwarunki a, a-1, a-2, ....

xnor
źródło
2
Nie rozumiem, jak input()nie może spowodować błędu.
feersum
@feersum Próbowałem i rzeczywiście rzuca błąd składniowy.
Alex A.,
Wziąłem dane wejściowe z cytatami typu "3P2", które moim zdaniem są zwykle dozwolone, ale tutaj wyzwanie mówi „dane wejściowe w dokładnej formie”, więc zmieniam je na funkcję, która pobiera ciąg znaków.
xnor
1

TI-BASIC, 52 bajty

Ans→Str1
expr(sub(Ans,1,⁻1+inString(Ans,"P→P        ;n
1
If expr(Str1                               ;If n^2*r ≠ 0
prod(randIntNoRep(P,P+1-expr(Str1)/P²
Ans

TI-BASIC ma funkcję „produktu z listy”, więc obejście ograniczeń wbudowanych nie jest zbyt trudne. Jednak TI-BASIC nie obsługuje pustych list - więc musimy

Aby wyodrębnić dwie liczby, wyodrębniam pierwszą liczbę jako podłańcuch. To jest drogie ; zajmuje całą drugą linię. Aby nie musieć tego robić ponownie dla drugiej liczby, ustawiam zmienną P na tę liczbę i oceniam cały łańcuch za pomocą expr(, a następnie dzielę przez P².

Na koniec biorę losową permutację listy między dwiema liczbami (dbając o dodanie jednej do drugiej liczby) i biorę produkt.

lirtosiast
źródło
1

Ouroboros , 47 45 bajtów

Niektóre z nich są dość brzydkie - wyobrażam sobie, że można by dalej grać w golfa.

Sr.r-1(
)s.!+S1+.@@.@\<!@@*Ys.!+*S.!!4*.(sn1(

Każda linia kodu w Ouroboros reprezentuje węża jedzącego ogon.

Snake 1

Sprzełącza na wspólny stos. r.rodczytuje jeden numer, powiela go i odczytuje inny. (Znaki nieliczbowe, takie jak Psą pomijane.) Odejmuje -dwa. Jeśli dane wejściowe były 7P2, mamy teraz 7, 5na wspólnym stosie. Wreszcie 1(zjada ostateczną postać węża. Ponieważ jest to znak, na którym znajduje się wskaźnik instrukcji, wąż umiera.

Snake 2

)snic nie robi za pierwszym razem. .!+duplikuje górę stosu węża 2, sprawdza, czy wynosi zero, a jeśli tak, dodaje 1. Przy pierwszej iteracji stos jest pusty i traktowany tak, jakby zawierał nieskończone zera, więc przesuwa się 1; w późniejszych iteracjach stos zawiera niezerową wartość i nie ma to wpływu.

Następnie Sprzełącza się na wspólny stos, gdzie mamy liczbę ni licznik do obliczania produktu. 1+zwiększa licznik. .@@.@\<!duplikuje obie liczby i wypycha 1, jeśli nnadal jest większy lub równy licznikowi, 0 w przeciwnym razie. @@*Ynastępnie mnoży licznik przez tę liczbę i ciągnie kopię na stos węża 2.

s.!+przełącza się z powrotem na stos węża 2 i używa tego samego kodu, co wcześniej, aby przekonwertować najwyższy numer na 1, jeśli był równy 0, i w przeciwnym razie nie zmieniaj go. Następnie *mnoży wynik przez częściowy produkt, który siedział na tym stosie.

Wracamy teraz do współdzielonego stosu ( S), duplikujemy licznik lub zero ( .) i negujemy go dwukrotnie ( !!), aby zamienić niezerowy licznik na 1. 4*.(mnoży to przez 4, duplikuje i zjada tyle znaków z koniec węża.

  • Jeśli nie osiągnęliśmy warunku zatrzymania, mamy 4 na stosie. Cztery znaki po (są zjadane, a pętle kontrolne rozpoczynają się na początku kodu. Tutaj )regurgituje cztery znaki, sprzełącza się z powrotem na stos węża 2 i wykonywanie jest kontynuowane.
  • Jeśli licznik minął n, mamy na stosie 0 i nic nie zostaje zjedzone. snprzełącza na stos snake 2 i wyświetla najwyższą wartość jako liczbę; następnie 1(zjada ostatnią postać i umiera.

W rezultacie produkt (r+1)*(r+2)*...*njest obliczany i generowany.

Wypróbuj to

DLosc
źródło