Веселье с перестановками

17

Кто не любит перестановки, верно? Я знаю, они потрясающие - так весело!

Ну, почему бы не принять это удовольствие и сделать его веселее ?

Вот проблема:

Учитывая ввод в точной форме:, nPrгде n- пул, взятый из и rколичество выборок из этого пула (и nи rявляются целыми числами), выведите / верните точное количество перестановок. Для тех из вас, кто немного разбирается в терминологии: перестановка, def. 2а .

Тем не менее, вот где задача вступает в игру (делает это не слишком легко):

Вы не можете использовать какую-либо встроенную библиотеку, структуру или метод для своей функции перестановки. Вы не можете использовать метод факториала, метод перестановки или что-либо подобное; Вы должны написать все сами.

Если необходимы дальнейшие разъяснения, пожалуйста, не стесняйтесь сообщить мне в комментариях, и я буду действовать соответственно.


Вот пример ввода / вывода:

Функция образца permute(String) -> int

Входные данные:

permute("3P2")

Выход:

6

Это код-гольф, поэтому выигрывает самый короткий код!

code-golf math permutations Даниил
источник
2
Оо. Я думал, что этот вызов будет на перестановочных группах . Классная вещь. Это тоже круто и тесно связано с группами перестановок. Люблю вызов.
Джастин
Когда вы говорите, что нет встроенных или библиотечных методов, вы имеете в виду перестановки или что-нибудь еще? Могу ли я использовать встроенный, splitчтобы разделить вход на P? Как насчет функции, которая преобразует строку в число?
xnor
3
Могут ли ответы предполагать это 0 <= r <= n?
Питер Тейлор
1
@Dopapp Вы имеете в виду, что r не больше, чем n ?
Денис
1
@RetoKoradi - Я полагаю, что для того, чтобы не заставлять большинство авторов повторять свои ответы, вам просто не разрешается использовать какие-либо факторные или перестановочные методы / функции.
Даниэль

Ответы:

4

CJam, 15 14 байтов

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

Попробуйте онлайн в интерпретаторе CJam .

Как это устроено

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 байт

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

Считая Шебанг как 4, ввод берется из стандартного ввода.

Образец использования

$ echo 3P2 | perl npr.pl
6

$ echo 7P4 | perl npr.pl
840
Примо
источник
Какой вариант l61?
feersum
@feersum он устанавливает , $\чтобы 1(полукокс 49, восьмеричный 61).
Примо
3

Haskell, 71 66 байт

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

Довольно простые вещи: разделите на 'P', затем возьмите произведение между (n-k + 1) и n.

Спасибо Ними за их идею использовать шаблонные ограждения, а не whereпункт, он сбрил 5 байтов.

arjanen
источник
2

Минколанг 0,11 , 13 25 19 байтов

Спасибо Sp3000 за предложение этого!

1nnd3&1N.[d1-]x$*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

Здесь используется тот же алгоритм, что и у Алекса: n P k= n(n-1)(n-2)...(n-k+1).

Эльендия Старман
источник
2

Юлия, 63 58 48 байтов

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

Это создает безымянную функцию, которая принимает строку и возвращает целое число. Чтобы назвать его, дайте ему имя, например f=s->....

Ungolfed:

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

При этом используется тот факт, что число перестановок равно n ( n -1) ( n -2) ... ( n - k +1).

Сохранено 10 байтов благодаря Glen O!

Алекс А.
источник
Нет необходимости Int, так что вы можете просто использовать map(parse,...).
Глен О
@GlenO Мой разум был взорван. Я не осознавал, что Intбыло необходимо в этой ситуации. Спасибо!
Алекс А.
2

Утилиты Bash + Linux, 33

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

jotпроизводит последовательность rцелых чисел, начиная с n-r+1, и разделяет их с *. Это выражение используется bcдля арифметической оценки.

Цифровая травма
источник
1

MATLAB, 54 байта

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

Пытался сделать его меньше, но одна из вещей, с которыми MATLAB действительно плохо справляется, это получение информации. Требуется 32 символа только для того, чтобы получить два числа из входной строки!

Достаточно понятный код. Получить ввод в форме, %dP%dгде% d является целым числом. Разделите это на nи r. Затем отобразите произведение каждого целого числа в диапазоне n-r+1до n. Интересно, что это работает даже для того, чтобы xP0дать правильный ответ 1. Это потому, что в MATLAB prod()функция возвращает 1, если вы пытаетесь создать пустой массив. Всякий раз, когдаr ноль, диапазон будет пустым массивом, поэтому мы получаем 1.

Это также прекрасно работает с Octave . Вы можете попробовать это онлайн здесь .

Том Карпентер
источник
1

Javascript, 59 57 байт

s=>(f=(n,k)=>k?(n- --k)*f(n,k):1,f.apply(f,s.split('P')))
Naouak
источник
1

Java (594 - байт)

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
источник
1

J, 23 байта

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

Анонимная функция. Пример:

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

Объяснение:

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

Используемая мной функция « стоп» может граничить со счетом как со встроенной ... Она лежит где-то между общностью оператора умножения и спецификой факториального оператора.

Линн
источник
1

APL, 23

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

Принимает строку в качестве аргумента. Объяснение:

              ⍵⊂⍨⍵≠'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
источник
Какой APL это? Я получаю ошибку с моей копией Dyalog.
lirtosiast
1
@ThomasKwa Используйте ⎕ML←3в 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

Довольно просто. Обрабатывает ввод числа как a,b. Сохраняет работающий продукт как P, который умножается на первые bчлены a, a-1, a-2, ....

XNOR
источник
2
Я не вижу, как input()не может привести к ошибке.
feersum
@feersum Я попробовал, и он действительно выдает синтаксическую ошибку.
Алекс А.
Я принимал ввод с кавычками "3P2", которые, как мне кажется, обычно разрешены, но здесь задача говорит «ввод в точной форме», поэтому я изменяю его на функцию, которая принимает строку.
xnor
1

TI-BASIC, 52 байта

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 есть функция «произведение списка», поэтому обойти ограничения на встроенные функции не так уж сложно. Тем не менее, TI-BASIC не поддерживает пустые списки, поэтому нам нужно

Чтобы извлечь два числа, я извлекаю первое число как подстроку. Это дорого ; занимает всю вторую строку. Чтобы избежать необходимости делать это снова для второго числа, я устанавливаю переменную P на это число и вычисляю всю строку, используя expr(, а затем делю на P².

Наконец, я беру случайную перестановку списка между двумя числами (стараясь добавить одно ко второму числу) и беру продукт.

lirtosiast
источник
1

Уроборос , 47 45 байт

Некоторые из них довольно уродливы - я думаю, что это может быть дальше в гольфе.

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

Каждая строка кода в Уроборосе представляет собой змею, которая ест свой хвост.

Змея 1

Sпереключается на общий стек r.rчитает одно число, дублирует его и читает другое. (Нечисловые символы, такие Pкак пропускаются.) Вычитает -два. Если вход был 7P2, у нас теперь 7, 5в общем стеке. В заключение,1( ест финальный персонаж змеи. Поскольку это символ, на котором находится указатель инструкции, змея умирает.

Змея 2

)sничего не делает в первый раз. .!+дублирует вершину стека snake 2, проверяет, равен ли он нулю, и, если это так, добавляет 1. На первой итерации, стек пуст и обрабатывается так, как если бы он содержал бесконечные нули, так что это толкает1 ; на более поздних итерациях стек содержит ненулевое значение, и это не имеет никакого эффекта.

Далее Sпереключаемся на общий стек, где у нас есть номер nи счетчик для расчета продукта. 1+увеличивает счетчик. .@@.@\<!дублирует как числа, так и нажимает 1, если nвсе еще больше или равно счетчику, 0 в противном случае. @@*Yзатем умножает счетчик на эту величину и копирует копию в стек змеи 2.

s.!+переключается обратно в стек Snake 2 и использует тот же код, что и раньше, чтобы преобразовать верхнее число в 1, если оно было 0, и оставить его таким же, в противном случае. Затем *умножает результат на частичное произведение, которое находилось в этом стеке.

Теперь вернемся к общему стеку ( S), продублируем counter-or-zero ( .) и дважды обнуляем его ( !!), чтобы превратить ненулевой счетчик в 1. 4*.(Умножаем это на 4, дублируем и съедаем столько символов из конец змеи.

  • Если мы не достигли условия остановки, у нас есть 4 в стеке. Четыре символа после (сгорают, и управление возвращается к началу кода. Здесь )регургитирует четыре символа, sпереключается обратно в стек Snake 2, и выполнение продолжается.
  • Если счетчик прошел n, у нас в стеке 0, и ничего не съедено. snпереключается на стек Snake 2 и выводит верхнее значение в виде числа; затем 1(ест последний символ и умирает.

В результате продукт (r+1)*(r+2)*...*nрассчитывается и выводится.

Попробуйте это

Показать фрагмент кода

DLosc
источник