Diversión con permutaciones

17

¿Quién no ama absolutamente las permutaciones, verdad? Lo sé, son increíbles, ¡muy divertidos!

Bueno, ¿por qué no tomar esta diversión y hacerla más divertida ?

Aquí está el desafío:

Dada una entrada en la forma exacta:, de nPrdónde nse toma el grupo y res el número de selecciones de ese grupo ( ny rson números enteros), genera / devuelve el número exacto de permutaciones. Para aquellos de ustedes que están un poco oxidados con la terminología: Permutación, def. 2a .

Sin embargo, aquí es donde entra en juego el desafío (hace que no sea demasiado fácil):

No puede utilizar ninguna biblioteca, marco o método incorporado para su función de permutación. No puede usar un método factorial, un método de permutación ni nada por el estilo; debes escribir todo tú mismo.

Si necesita más aclaraciones, no dude en informarme en los comentarios y actuaré de inmediato.


Aquí hay un ejemplo de E / S:

La función de muestra es permute(String) -> int

Entrada:

permute("3P2")

Salida:

6

Este es el código de golf, ¡el código más corto gana!

Daniel
fuente
2
Aww. Pensé que este desafío estaría en los grupos de permutación . Cosas interesantes. Esto también es genial y está estrechamente relacionado con los grupos de permutación. Amo el desafío.
Justin
Cuando dice que no hay métodos incorporados o de biblioteca, ¿quiere decir permutaciones o algo? ¿Puedo usar el incorporado splitpara dividir la entrada en el P? ¿Qué pasa con una función que convierte una cadena en un número?
xnor
3
¿Pueden las respuestas asumir eso 0 <= r <= n?
Peter Taylor
1
@Dopapp ¿Quiere decir que r no es mayor que n ?
Dennis
1
@RetoKoradi: supongo que en un esfuerzo por no obligar a la mayoría de los carteles a rehacer sus respuestas, simplemente no se le permite usar ningún método / función factorial o de permutación.
Daniel

Respuestas:

4

CJam, 15 14 bytes

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

Pruébelo en línea en el intérprete de CJam .

Cómo funciona

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
fuente
4

Perl, 27 bytes

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

Contando el shebang como 4, la entrada se toma de stdin.


Uso de muestra

$ echo 3P2 | perl npr.pl
6

$ echo 7P4 | perl npr.pl
840
primo
fuente
¿Qué tipo de opción es l61?
fiesta del
@feersum se establece $\en 1(char 49, octal 61).
primo
3

Haskell 71 66 bytes

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

Cosas bastante sencillas: dividir en la 'P' y luego tomar el producto entre (n-k + 1) yn.

Gracias a nimi por su idea de usar guardias de patrones en lugar de una wherecláusula, redujo 5 bytes.

arjanen
fuente
2

Minkolang 0.11 , 13 25 19 bytes

¡Gracias a Sp3000 por sugerir esto!

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

Pruébalo aquí

Explicación

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

Esto usa el mismo algoritmo que el de Alex: n P k= n(n-1)(n-2)...(n-k+1).

El'endia Starman
fuente
2

Julia, 63 58 48 bytes

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

Esto crea una función sin nombre que acepta una cadena y devuelve un entero. Para llamarlo, dale un nombre, por ejemplo f=s->....

Sin 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

Esto utiliza el hecho de que el número de permutaciones es n ( n -1) ( n -2) ... ( n - k +1).

Guardado 10 bytes gracias a Glen O!

Alex A.
fuente
No es necesario Int, así que puedes usarlo map(parse,...).
Glen O
@GlenO Mi mente ha quedado impresionada. No me di cuenta de que Intera necesario en esa situación. ¡Muchas gracias!
Alex A.
2

Bash + utilidades de Linux, 33

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

jotproduce la secuencia de renteros que comienza en n-r+1, y los separa con *. Esta expresión se canaliza bcpara la evaluación aritmética.

Trauma digital
fuente
1

MATLAB, 54 bytes

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

Intenté hacerlo más pequeño, pero una de las cosas en las que MATLAB es realmente malo es obtener entradas. ¡Solo se necesitan 32 caracteres para obtener los dos números de la cadena de entrada!

Código bastante autoexplicativo. Obtenga la entrada en el formulario %dP%ddonde% d es un número entero. Divide eso en ny r. Luego muestre el producto de cada entero en el rango n-r+1de n. Curiosamente, esto funciona incluso para xP0dar la respuesta correcta de 1. Esto se debe a que en MATLAB la prod()función devuelve 1 si intenta hacer el producto de una matriz vacía. Siempre que rsea ​​cero, el rango será una matriz vacía, entonces bingo obtenemos 1.


Esto también funciona perfectamente con Octave también. Puedes probarlo en línea aquí .

Tom Carpenter
fuente
1

Javascript, 59 57 bytes

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

Java (594 - bytes)

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
fuente
1

J, 23 bytes

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

Una función anónima. Ejemplo:

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

Explicación:

       (  ;._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 función de rebaje que utilicé podría limitarse a contar como una función incorporada ... Descansa en algún lugar entre la generalidad del operador de multiplicación y la especificidad del operador factorial.

Lynn
fuente
1

APL, 23

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

Toma la cadena como argumento. Explicación:

              ⍵⊂⍨⍵≠'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.
usuario46915
fuente
¿Qué APL es este? Recibo un error con mi copia de Dyalog.
lirtosiast el
1
@ThomasKwa Uso ⎕ML←3en Dyalog.
user46915
1

Pitón 2, 66

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

Muy claro. Procesa la entrada del número como a,b. Mantiene un producto en ejecución como P, que se multiplica por los primeros btérminos de a, a-1, a-2, ....

xnor
fuente
2
No veo cómo input()no podría dar lugar a un error.
feersum
@feersum Lo probé y de hecho arroja un error de sintaxis.
Alex A.
Estaba tomando entradas con citas como "3P2", lo que creo que generalmente está permitido, pero aquí el desafío dice "una entrada en la forma exacta", así que la cambio a una función que toma una cadena.
xnor
1

TI-BASIC, 52 bytes

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 tiene una función de "producto de una lista", por lo que evitar la restricción de las incorporaciones no es demasiado difícil. Sin embargo, TI-BASIC no admite listas vacías, por lo que debemos

Para extraer los dos números, extraigo el primer número como una subcadena. Esto es caro ; Ocupa toda la segunda línea. Para evitar tener que volver a hacer esto para el segundo número, configuro la variable P en ese número y evalúo la cadena completa usando expr(, luego divido por P².

Finalmente, tomo una permutación aleatoria de la lista entre los dos números (procurando agregar uno al segundo número) y tomo el producto.

lirtosiast
fuente
1

Ouroboros , 47 45 bytes

Algo de esto es bastante feo: me imagino que podría jugar más golf.

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

Cada línea de código en Ouroboros representa una serpiente que se come la cola.

Serpiente 1

Scambia a la pila compartida. r.rlee un número, lo duplica y lee otro. (Se omiten los caracteres no numéricos como P). -Resta los dos. Si la entrada fue 7P2, ahora tenemos 7, 5en la pila compartida. Finalmente, se 1(come el personaje final de la serpiente. Como este es el carácter en el que se encuentra el puntero de instrucción, la serpiente muere.

Serpiente 2

)s no hace nada la primera vez. .!+duplica la parte superior de la pila de la serpiente 2, comprueba si es cero y, si es así, agrega 1. En la primera iteración, la pila está vacía y se trata como si contuviera ceros infinitos, por lo que esto empuja 1; en iteraciones posteriores, la pila contiene un valor distinto de cero y esto no tiene ningún efecto.

A continuación, Scambia a la pila compartida, donde tenemos el número ny un contador para calcular el producto. 1+incrementa el contador. .@@.@\<!duplica ambos números y empuja 1 si naún es mayor o igual que el contador, 0 de lo contrario.@@*Yluego multiplica el contador por esta cantidad y tira una copia a la pila de la serpiente 2.

s.!+vuelve a la pila de la serpiente 2 y usa el mismo código que antes para convertir el número superior a 1 si era 0 y, de lo contrario, lo mantiene igual. Luego* multiplica el resultado por el producto parcial que estaba en esta pila.

Ahora volvemos a la pila compartida ( S), duplicamos el contador o cero ( .) y lo negamos dos veces ( !!) para convertir un contador distinto de cero en 1. 4*.(multiplica esto por 4, duplica y come tantos caracteres del Fin de la serpiente.

  • Si no hemos alcanzado la condición de detención, tenemos un 4 en la pila. Se (comen los cuatro caracteres después del y el control gira alrededor del principio del código. Aquí )regurgita cuatro caracteres, svuelve a la pila de la serpiente 2 y la ejecución continúa.
  • Si el contador ha pasado n, tenemos un 0 en la pila y no se come nada. sncambia a la pila de la serpiente 2 y genera el valor superior como un número; luego 1(come el último personaje y muere.

El resultado es que el producto (r+1)*(r+2)*...*nse calcula y se genera.

Pruébalo

DLosc
fuente