Amusez-vous avec les permutations

17

Qui n'aime absolument pas les permutations, non? Je sais, ils sont incroyables - tellement amusant!

Eh bien, pourquoi ne pas prendre ce plaisir et le rendre plus amusant ?

Voici le défi:

Étant donné une entrée sous la forme exacte:, nPrnest le pool pris et rest le nombre de sélections de ce pool (et net rsont des entiers), affiche / renvoie le nombre exact de permutations. Pour ceux d'entre vous qui sont un peu rouillés avec la terminologie: Permutation, def. 2a .

Cependant, c'est là que le défi entre en jeu (le rend pas trop facile):

Vous ne pouvez utiliser aucune bibliothèque, structure ou méthode intégrée pour votre fonction de permutation. Vous ne pouvez pas utiliser une méthode factorielle, une méthode de permutation ou quoi que ce soit du genre; vous devez tout écrire vous-même.

Si des éclaircissements supplémentaires sont nécessaires, n'hésitez pas à me le dire dans les commentaires et j'agirai rapidement en conséquence.


Voici un exemple d'E / S:

La fonction d'échantillon est permute(String) -> int

Contribution:

permute("3P2")

Production:

6

C'est le code-golf, donc le code le plus court gagne!

Daniel
la source
2
Aww. Je pensais que ce défi serait sur les groupes de permutation . Truc cool. C'est cool aussi, et étroitement lié aux groupes de permutation. J'adore le défi.
Justin
Lorsque vous dites qu'il n'y a pas de méthodes intégrées ou de bibliothèque, voulez-vous dire pour les permutations ou pour quoi que ce soit? Puis-je utiliser le intégré splitpour diviser l'entrée à la P? Qu'en est-il d'une fonction qui convertit une chaîne en nombre?
xnor
3
Les réponses peuvent-elles supposer cela 0 <= r <= n?
Peter Taylor
1
@Dopapp Voulez-vous dire que r n'est pas supérieur à n ?
Dennis
1
@RetoKoradi - Je suppose que dans un effort pour ne pas forcer la plupart des affiches à refaire leurs réponses, vous n'êtes tout simplement pas autorisé à utiliser des méthodes / fonctions factorielles ou de permutation.
Daniel

Réponses:

4

CJam, 15 14 octets

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

Essayez-le en ligne dans l' interpréteur CJam .

Comment ça fonctionne

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
la source
4

Perl, 27 octets

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

En comptant le shebang comme 4, l'entrée provient de stdin.


Exemple d'utilisation

$ echo 3P2 | perl npr.pl
6

$ echo 7P4 | perl npr.pl
840
primo
la source
Quelle sorte d'option est l61?
feersum
@feersum il est défini $\sur 1(caractère 49, octal 61).
primo
3

Haskell, 71 66 octets

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

Trucs assez simples: diviser au 'P' puis prendre le produit entre (n-k + 1) et n.

Merci à nimi pour leur idée d'utiliser des gardes de modèle plutôt qu'une whereclause, cela a réduit de 5 octets.

arjanen
la source
2

Minkolang 0,11 , 13 25 19 octets

Merci à Sp3000 de l' avoir suggéré!

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

Essayez-le ici.

Explication

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

Cela utilise le même algorithme que celui d'Alex: n P k= n(n-1)(n-2)...(n-k+1).

El'endia Starman
la source
2

Julia, 63 58 48 octets

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

Cela crée une fonction sans nom qui accepte une chaîne et retourne un entier. Pour l'appeler, donnez-lui un nom, par exemple f=s->....

Non golfé:

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

Cela utilise le fait que le nombre de permutations est n ( n -1) ( n -2) ... ( n - k +1).

10 octets enregistrés grâce à Glen O!

Alex A.
la source
Pas besoin Int, donc vous pouvez simplement utiliser map(parse,...).
Glen O
@GlenO Mon esprit a été époustouflé. Je ne savais pas que Intc'était nécessaire dans cette situation. Merci beaucoup!
Alex A.
2

Utilitaires Bash + Linux, 33

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

jotproduit la séquence d' rentiers commençant par n-r+1et les sépare avec *. Cette expression est canalisée pour bcune évaluation arithmétique.

Traumatisme numérique
la source
1

MATLAB, 54 octets

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

J'ai essayé de le rendre plus petit, mais MATLAB est vraiment mal à obtenir des entrées. Il faut 32 caractères juste pour obtenir les deux nombres de la chaîne d'entrée!

Code assez explicite. Obtenez l'entrée sous la forme %dP%doù% d est un entier. Divisez cela en net r. Affichez ensuite le produit de chaque entier de la plage n-r+1à n. Fait intéressant, cela fonctionne même pour xP0donner la bonne réponse de 1. En effet, dans MATLAB, la prod()fonction renvoie 1 si vous essayez de faire le produit d'un tableau vide. Chaque fois qu'il rest nul, la plage sera un tableau vide, donc le bingo-test nous obtenons 1.


Cela fonctionne également parfaitement avec Octave . Vous pouvez l'essayer en ligne ici .

Tom Carpenter
la source
1

Javascript, 59 57 octets

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

Java (594 - octets)

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
la source
1

J, 23 octets

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

Une fonction anonyme. Exemple:

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

Explication:

       (  ;._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.

La fonction de chantier que j'ai utilisée pourrait frôler le fait de compter comme une fonction intégrée ... Elle repose quelque part entre la généralité de l'opérateur de multiplication et la spécificité de l'opérateur factoriel.

Lynn
la source
1

APL, 23

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

Prend la chaîne comme argument. Explication:

              ⍵⊂⍨⍵≠'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.
user46915
la source
De quel APL s'agit-il? Je reçois une erreur avec ma copie de Dyalog.
lirtosiast
1
@ThomasKwa Utilisation ⎕ML←3dans Dyalog.
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

Assez simple. Traite l'entrée numérique comme a,b. Conserve un produit en cours d'exécution tel Pque multiplié par les premiers btermes de a, a-1, a-2, ....

xnor
la source
2
Je ne vois pas comment cela input()n'a pas pu entraîner une erreur.
feersum
@feersum Je l'ai essayé et il lance en effet une erreur de syntaxe.
Alex A.
Je prenais des entrées avec des guillemets comme "3P2", ce qui, je pense, est généralement autorisé, mais ici le défi dit "une entrée sous la forme exacte", donc je la change en une fonction qui prend une chaîne.
2015 à 2h01
1

TI-BASIC, 52 octets

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 a une fonction "produit d'une liste", donc contourner la restriction sur les builtins n'est pas trop difficile. Cependant, TI-BASIC ne prend pas en charge les listes vides. Nous devons donc

Pour extraire les deux nombres, j'extrais le premier nombre comme une sous-chaîne. C'est cher ; il occupe toute la deuxième ligne. Pour éviter d'avoir à refaire cela pour le deuxième nombre, j'ai défini la variable P sur ce nombre, et évalué la chaîne entière à l'aide expr(, puis divisée par P².

Enfin, je prends une permutation aléatoire de la liste entre les deux nombres (en prenant soin d'en ajouter un au deuxième nombre) et de prendre le produit.

lirtosiast
la source
1

Ouroboros , 47 45 octets

Une partie de cela est assez moche - j'imagine que cela pourrait être joué plus loin.

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

Chaque ligne de code dans Ouroboros représente un serpent mangeant sa queue.

Serpent 1

Sbascule vers la pile partagée. r.rlit un nombre, le duplique et en lit un autre. (Les caractères non numériques comme Psont ignorés.) -Soustrait les deux. Si l'entrée était 7P2, nous l'avons maintenant 7, 5sur la pile partagée. Enfin, 1(mange le dernier personnage du serpent. Puisque c'est le caractère sur lequel se trouve le pointeur d'instruction, le serpent meurt.

Serpent 2

)sne fait rien la première fois. .!+duplique le haut de la pile de snake 2, vérifie si elle est nulle, et si c'est le cas ajoute 1. Lors de la première itération, la pile est vide et traitée comme si elle contenait des zéros infinis, donc cela pousse 1; sur les itérations ultérieures, la pile contient une valeur non nulle et cela n'a aucun effet.

Ensuite, Spasse à la pile partagée, où nous avons le numéro net un compteur pour calculer le produit. 1+incrémente le compteur. .@@.@\<!duplique les deux nombres et pousse 1 si nest toujours supérieur ou égal au compteur, 0 sinon. @@*Ymultiplie ensuite le compteur par cette quantité et tire une copie sur la pile de serpent 2.

s.!+revient à la pile de snake 2 et utilise le même code que précédemment pour convertir le premier numéro en 1 s'il était égal à 0 et le conserver dans le cas contraire. *Multiplie ensuite le résultat par le produit partiel qui se trouvait sur cette pile.

Nous retournons maintenant à la pile partagée ( S), dupliquons le compteur ou zéro ( .), et l'annulons deux fois ( !!) pour transformer un compteur différent de zéro en 1. 4*.(multiplie cela par 4, duplique et mange autant de caractères du fin du serpent.

  • Si nous n'avons pas atteint la condition d'arrêt, nous avons un 4 sur la pile. Les quatre caractères après le (sont mangés et les boucles de contrôle jusqu'au début du code. Ici )régurgite quatre personnages, srevient à la pile de serpent 2 et l'exécution continue.
  • Si le compteur est passé n, nous avons un 0 sur la pile et rien n'est mangé. snbascule vers la pile de snake 2 et sort la valeur supérieure sous forme de nombre; puis 1(mange le dernier personnage et meurt.

Le résultat est que le produit (r+1)*(r+2)*...*nest calculé et sorti.

Essaye le

DLosc
la source