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!


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.

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

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.


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).


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!


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.


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 .


1

JavaScript, 59 57 bajtów

s=>(f=(n,k)=>k?(n- --k)*f(n,k):1,f.apply(f,s.split('P')))

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

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.


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.

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, ....


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.


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

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.