Произвольная случайность

26

Случайность это весело. Проблемы без смысла весело.

Напишите функцию, которая при заданном целочисленном вводе nвыведет набор (неупорядоченный, уникальный) точно nслучайных целых чисел между 1и n^2(включительно) таким образом, чтобы сумма всех целых чисел была равна n^2.

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

Кратчайший ответ в байтах (на каждый язык) выигрывает.

Примеры

Input (n) = 1, Target (n^2) = 1
Sample of possible outputs:
1

Input = 2, Target = 4
Sample of possible outputs:
3, 1
1, 3

Input = 3, Target = 9
Sample of possible outputs:
6, 1, 2
3, 5, 1
4, 3, 2

Input = 4, Target = 16
Sample of possible outputs:
1, 3, 5, 7
2, 4, 1, 9
8, 3, 1, 4

Input = 5, Target = 25
Sample of possible outputs:
11, 4, 7, 1, 2
2, 3, 1, 11, 8
6, 1, 3, 7, 8

Input = 8, Target = 64
Sample of possible outputs:
10, 3, 9, 7, 6, 19, 8, 2
7, 16, 2, 3, 9, 4, 13, 10
7, 9, 21, 2, 5, 13, 6, 1

Бонусное задание: существует ли формула для расчета количества действительных перестановок для данного n?

Skidsdev
источник
2
связанные , но совсем другие
Джузеппе
1
(p / s: если у вас быстрый алгоритм, но он занимает больше байтов, подумайте над ожиданием публикации в скоростном издании (в настоящее время в песочнице).)
user202729
1
@EriktheOutgolfer Хотя есть (намного) лучшие способы, чем генерация всех наборов и выбор случайных, их гораздо сложнее реализовать и, вероятно, дольше. Сохраните их для скоростного издания.
user202729
2
Количество комплектов OEIS A107379 .
nwellnhof
1
Это оба. Смотрите комментарий "Также количество разбиений n ^ 2 на n отдельных частей."
nwellnhof

Ответы:

9

Brachylog (v2), 15 байтов (случайный) или 13 байтов (все возможности)

случайный

~lℕ₁ᵐA+√?∧A≜₁ᵐ≠

Попробуйте онлайн!

Представление функции (видно в TIO с оберткой, превращающей ее в полноценную программу).

объяснение

~lℕ₁ᵐA+√?∧A≜₁ᵐ≠
~l               Specify a property of a list: its length is equal to the input,
    ᵐ              and it is composed entirely of
  ℕ₁                 integers ≥ 1,
       √           for which the square root of the
      +              sum of the list
        ?              is the input.
     A   ∧A      Restricting yourself to lists with that property,
           ≜₁      pick random possible values
             ᵐ       for each element in turn,
              ≠    until you find one whose elements are all distinct.

Все возможности

~lℕ₁ᵐ<₁.+√?∧≜

Попробуйте онлайн!

Функция представления, которая генерирует все возможные выходы.

объяснение

~lℕ₁ᵐ<₁.+√?∧≜
~l               Specify a property of a list: its length is equal to the input,
    ᵐ              it is composed entirely of
  ℕ₁                 integers ≥ 1,
     <₁            it is strictly increasing,
         √         and the square root of the
        +            sum of the list
          ?            is the input.
       .   ∧≜    Generate all specific lists with that property.

Я довольно удивлен, что это ∧≜работает (вам, как правило, придется писать ∧~≜для того, чтобы перебрать выходные данные, а не входные данные), но оказывается, что имеет предположение input = output, поэтому не имеет значения, в какую сторону вас обойти запустить его.

Бонусное задание

Чтобы получить представление о последовательности числа возможностей, я создал другую оболочку TIO, которая запускает программу с последовательными целыми числами, чтобы получить последовательность выходных значений:

1,1,3,9,30,110,436,1801,7657,33401

Поездка в OEIS обнаруживает, что это уже известная последовательность, A107379 , описанная почти так же, как в вопросе (очевидно, вы получите ту же последовательность, если вы ограничите ее нечетными числами). На странице перечислены несколько формул для последовательности (хотя ни одна из них не является особенно простой; вторая выглядит как прямая формула для значения, но я не понимаю обозначения).

оборота ais523
источник
Вторая формула - «коэффициент x^(n*(n-1)/2)расширения в серии Product_{k=1..n} 1/(1 - x^k)» (к сожалению,
совсем
Помещение ограничения «все по-другому» до шага произвольной маркировки (например A≠≜₁ᵐ) делает время выполнения в среднем намного быстрее.
Роковая
Я не понимаю, почему вы сделали это вики-сообществом. Это архаичный способ иметь редактируемые посты до того, как их можно было редактировать.
труба
7

05AB1E , 11 байт

nÅœʒDÙQ}sùΩ

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

n             # Take the square of the (implicit) input
              #  i.e. 3 → 9
 Ŝ           # Get all integer-lists using integers in the range [1, val) that sum to val
              #  i.e. 9 → [[1,1,1,1,1,1,1,1,1],...,[1,3,5],...,[9]]
   ʒ   }      # Filter the list to only keep lists with unique values:
    D         # Duplicate the current value
     Ù        # Uniquify it
              #  i.e. [2,2,5] → [2,5]
      Q       # Check if it's still the same
              #  i.e. [2,2,5] and [2,5] → 0 (falsey)
        s     # Swap to take the (implicit) input again
         ù    # Only leave lists of that size
              #  i.e. [[1,2,6],[1,3,5],[1,8],[2,3,4],[2,7],[3,6],[4,5],[9]] and 3
              #   → [[1,2,6],[1,3,5],[2,3,4]]
          Ω   # Pick a random list from the list of lists (and output implicitly)
Кевин Круйссен
источник
5

R , 68, 75 48 байтов (случайный) и 70 байтов (детерминированный)

Метод выборки отклонения @ Джузеппе:

function(n){while(sum(F)!=n^2)F=sample(n^2,n);F}

Попробуйте онлайн!

Гольф оригинал:

function(n,m=combn(1:n^2,n))m[,sample(which(colSums(m)==n^2)*!!1:2,1)]

Попробуйте онлайн!

Задача *!!1:2состоит в том, чтобы избежать странных sampleдействий, когда первый аргумент имеет длину 1.

НГМ
источник
@Giuseppe "исправлено" :-)
нгм
очень хорошо. использование pнепосредственно в качестве индекса вместо вычисления и повторного использования должно сохранить некоторые байты.
Джузеппе
1
У меня тоже function(n){while(sum(F)!=n^2)F=sample(n^2,n);F}48 ...
Джузеппе
1
@ J. Чтобы избежать проблемы при вызове чего-то подобного, sample(2,1)что происходит с n=2. Так repчто просто гарантирует, что этого никогда не произойдет. Возможно, есть лучший способ, но это было быстро, и я был зол на sample.
НГМ
1
Вы можете сохранить байт с x*!!1:2более чем, rep(x,2)если ваш мета-вопрос получает нет.
J.Doe
4

Java 10, 250 242 222 байта

import java.util.*;n->{for(;;){int i=n+1,r[]=new int[i],d[]=new int[n];for(r[n<2?0:1]=n*n;i-->2;r[i]=(int)(Math.random()*n*n));var S=new HashSet();for(Arrays.sort(r),i=n;i-->0;)S.add(d[i]=r[i+1]-r[i]);if(!S.contains(0)&S.size()==n)return S;}}

-20 байт благодаря @nwellnhof .

Остерегайтесь, Java приходит ... Это «всего» в пять раз дольше, чем остальные четыре ответа вместе взятые, так что, думаю, не так уж и плохо… rofl.
Он мчит n=1через n=25(комбинированный) менее чем за 2 секунды , хотя, так что я , вероятно , опубликовать измененную версию до версии скорости этой задачи (которая в настоящее время все еще находится в песочнице) , а также.

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

Объяснение:

В псевдокоде мы делаем следующее:

1) Создание массива размера , n+1содержащий: 0, nквадрат, а n-1количество случайных чисел в диапазоне от [0, n squared)
2) Сортировки этого массива
3) создать второй массив размера , nсодержащий вперед различие пар
Этого первые три шаг даст нам массив , содержащий nслучайный образ целые числа (в диапазоне [0, n squared)от суммы до nквадрата.
4a) Если не все случайные значения уникальны или любое из них равно 0: повторите попытку с шага 1
4b) Остальное: вернуть этот массив разностей в качестве результата

Что касается фактического кода:

import java.util.*;      // Required import for HashSet and Arrays
n->{                     // Method with int parameter and Set return-type
  for(;;){               //  Loop indefinitely
    int i=n+1,           //   Set `i` to `n+1`
        r[]=new int[i];  //   Create an array of size `n+1`
    var S=new HashSet(); //   Result-set, starting empty
    for(r[n<2?           //   If `n` is 1:
           0             //    Set the first item in the first array to:
          :              //   Else:
           1]            //    Set the second item in the first array to:
             =n*n;       //   `n` squared
        i-->2;)          //   Loop `i` in the range [`n`, 2]:
      r[i]=              //    Set the `i`'th value in the first array to:
           (int)(Math.random()*n*n); 
                         //     A random value in the range [0, `n` squared)
    for(Arrays.sort(r),  //   Sort the first array
        i=n;i-->0;)      //   Loop `i` in the range (`n`, 0]:
      S.add(             //    Add to the Set:
        r[i+1]-r[i]);    //     The `i+1`'th and `i`'th difference of the first array
    if(!S.contains(0)    //   If the Set does not contain a 0
       &S.size()==n)     //   and its size is equal to `n`:
      return S;}}        //    Return this Set as the result
                         //   (Implicit else: continue the infinite loop)
Кевин Круйссен
источник
1
n=25менее чем за 2 секунды впечатляет! Я должен прочитать объяснение и посмотреть, как оно это делает. Это все еще метод грубой силы?
Скидсдев
Это униформа? -
user202729
@ user202729 Хотя я не уверен, как это доказать, я думаю, что это так. Встроенная Java-программа является однородной, и она использует ее, чтобы [0, n squared)сначала получить случайные значения в диапазоне , а затем вычисляет различия между этими отсортированными случайными значениями (включая начальное 0и конечное значения n squared. Поэтому я почти уверен, что эти различия также одинаковы. Но снова Я не уверен, как это доказать. Равномерность в случайности на самом деле не моя экспертиза
Кевин Круйссен
3
Вы никогда не читали из массива различий dили я что-то упустил?
nwellnhof
1
Я вроде доволен своим решением на 127 байтов : D
Оливье Грегуар
4

Perl 6 , 41 байт

{first *.sum==$_²,(1..$_²).pick($_)xx*}

Попробуйте онлайн!

  • (1 .. $_²) диапазон чисел от 1 до квадрата входного числа
  • .pick($_) случайным образом выбирает отдельное подмножество этого диапазона
  • xx * повторяет предыдущее выражение бесконечно
  • first *.sum == $_² выбирает первый из этих наборов чисел, который суммируется с квадратом входного числа
Шон
источник
40 байтов
Джо Кинг,
2

Pyth, 13 12 байт

Ofq*QQsT.cS*

Попробуйте это онлайн здесь . Обратите внимание, что онлайн-интерпретатор сталкивается с MemoryError для входных данных больше 5.

Ofq*QQsT.cS*QQQ   Implicit: Q=eval(input())
                 Trailing QQQ inferred
          S*QQQ   [1-Q*Q]
        .c    Q   All combinations of the above of length Q, without repeats
 f                Keep elements of the above, as T, where the following is truthy:
      sT            Is the sum of T...
  q                 ... equal to...
   *QQ              ... Q*Q?
O                 Choose a random element of those remaining sets, implicit print

Изменить: сохранить байт, используя альтернативный подход. Предыдущая версия: Of&qQlT{IT./*

Sok
источник
2

Python 3 , 136 134 127 121 114 байтов

from random import*
def f(n):
	s={randint(1,n*n)for _ in range(n)}
	return len(s)==n and sum(s)==n*n and s or f(n)

Попробуйте онлайн!

Меня поправил комментатор, и теперь он достигает максимальной глубины рекурсии при f (5) вместо f (1). Намного ближе к тому, чтобы быть реальным конкурирующим ответом.

Я видел, как это делает f (5) один раз , и я работаю над тем, чтобы реализовать это с помощью shuffle.

Я попытался сделать несколько лямбда-выражений для s=..., но это не помогло в байтах. Может быть, кто-то еще может что-то сделать с этим: s=(lambda n:{randint(1,n*n)for _ in range(n)})(n)

Спасибо Кевину за то, что он сбрил еще 7 байтов.

гигафлоп
источник
1
Таким образом, это использует рекурсию, чтобы "восстановить" набор, если сгенерированный является недействительным? Определенно, что-то не так с вашим кодом, если он достигает глубины рекурсии f(1), единственный возможный массив, который должен быть сгенерирован, n=1это [1]также много лишних пробелов, которые нужно удалить здесь. Помните, что это сложная задача для игры в гольф, поэтому цель состоит в том, чтобы достичь наименьшего количества участников
Skidsdev
1
range(1,n)-> range(n)Я считаю, должен устранить ошибку.
Джонатан Аллан
1
Это должно исправить вашу ошибку, а также удалить лишние пробелы. Я полагаю, что здесь есть
куда
1
Хотя рекурсия слегка ухудшается с 5 до 4, вы можете объединить два оператора возврата следующим образом: return len(s)==n and sum(s)==n*n and s or f(n)( Попробуйте онлайн 114 байтов ).
Кевин Круйссен
1
Вы можете иметь все это на одной линии. 111 байт
Джо Кинг,
2

APL (Dyalog Unicode) , 20 байтов SBCS

Анонимный префикс лямбда.

{s=+/c←⍵?s←⍵*2:c⋄∇⍵}

Попробуйте онлайн!

{} "Дфн"; это аргумент

⍵*2 приводить аргументы

s← назначить s(для s quare)

⍵? найти nслучайные индексы от 1… sбез замены

c← назначить c(для c andidate)

+/ суммировать их

s= по сравнению с s

: если равно

  c вернуть кандидата

 еще

  ∇⍵ повторять аргумент

Адам
источник
Вы видели 18 байтов моего и H.PWiz ?
НГН
@ngn Нет, явно нет, но я проверил, что решение APL не было опубликовано до того, как я его разместил Почему никого из вас не было
Адам
хорошо, как только я играю в гольф и показываю это саду, нет никакого стимула отправлять :)
ngn
@ngn Для тебя нет, но для меня есть.
Адам
1
конечно, и я думаю, что вы делаете большую работу по популяризации apl здесь. я просто убедился, что вы знаете, что более короткие решения были найдены, и, вероятно, лучше объяснить одно из них (или вариант) вместо этого
ngn
2

APL (Dyalog Classic) , 18 байт

(≢?≢×≢)⍣(0=+.-∘≢)⍳

Попробуйте онлайн!

использования ⎕io←1

генерирует числа 1 2 ... n

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

длина, т.е. n

≢?≢×≢выбирайте случайно nразные целые числа от 1 до n2

+.-∘≢ вычтите длину из каждого числа и суммы

0= если сумма равна 0, остановите цикл, в противном случае попробуйте снова

СПП
источник
1

MATL , 18 13 байт

`xGU:GZrtsGU-

Попробуйте онлайн!

`	# do..while:
x	# delete from stack. This implicitly reads input the first time
	# and removes it. It also deletes the previous invalid answer.
GU:	# paste input and push [1...n^2]
GZr	# select a single combination of n elements from [1..n^2]
tsGU-	# is the sum equal to N^2? if yes, terminate and print results, else goto top
Giuseppe
источник
Я бы не стал пробовать это в R - случайные символы почти никогда не создают правильную программу.
НГМ
@ngm hahaha Полагаю, объяснение в порядке.
Джузеппе
1

Japt, 12 байт

²õ àU ö@²¥Xx

Попытайся

                 :Implicit input of integer U
²                :U squared
 õ               :Range [1,U²]
   àU            :Combinations of length U
      ö@         :Return a random element that returns true when passed through the following function as X
        ²        :  U squared
         ¥       :  Equals
          Xx     :  X reduced by addition
мохнатый
источник
Согласно комментарию, сделанному OP, порядок элементов в выходных данных не имеет значения, поэтому àдолжен быть в порядке.
Камил Дракари
Спасибо, @KamilDrakari. Обновлено.
лохматый
1

Java (JDK) , 127 байт

n->{for(int s;;){var r=new java.util.TreeSet();for(s=n*n;s>0;)r.add(s-(s-=Math.random()*n*n+1));if(r.size()==n&s==0)return r;}}

Попробуйте онлайн!

Бесконечный цикл до совпадения набора с критериями.

Я надеюсь, у вас есть время, потому что это очень круто! Это даже не может идти до 10 без времени ожидания.

Оливье Грегуар
источник
Вы можете сыграть в гольф 3 байта, изменив if(r.size()==n&s==0)на if(r.size()+s==n).
Кевин Круйссен
@KevinCruijssen Я тоже об этом думал, но нет, не могу, потому что s может быть -1, а n может быть размером () - 1.
Оливье Грегуар,
Ах, подождите, вы продолжаете добавлять элементы в набор s>0, пока размер может быть больше, чем n. Хорошо, в этом случае это действительно не работает. nявляется константой, но, к сожалению, оба sи r.size()являются переменными, которые могут быть как ниже, так и выше 0и nсоответственно.
Кевин Круйссен,
1

Пакет, 182 145 байтов

@set/an=%1,r=n*n,l=r+1
@for /l %%i in (%1,-1,1)do @set/at=n*(n-=1)/2,m=(r+t+n)/-~n,r-=l=m+%random%%%((l-=x=r+1-t)*(l^>^>31)+x-m)&call echo %%l%%

Объяснение: Вычисляет минимально и максимально допустимый выбор, учитывая, что числа должны быть выбраны в порядке убывания, и выбирает случайное значение в пределах диапазона. Пример для ввода 4:

  • Начнем с 16 слева. Мы не можем выбрать 11 или больше, потому что оставшиеся 3 выбора должны добавить как минимум к 6. Нам также нужно выбрать по крайней мере 6, потому что если мы выберем только 5, оставшиеся 3 выбора могут добавить только к 9, что не является достаточно для 16. Выбираем случайное значение от 6 до 10, скажем 6.
  • У нас осталось 10. Мы не можем выбрать 8 или больше, потому что оставшиеся 2 выбора должны добавить как минимум к 3. Как это происходит, мы не можем выбрать 6 или больше, потому что мы выбрали 6 в прошлый раз. Нам также нужно выбрать по крайней мере 5, потому что если мы выберем только 4, оставшиеся 2 выбора могут добавить только к 5, в общей сложности 15. Мы выбираем случайное значение от 5 до 5, скажем 5 (!).
  • У нас осталось 5 Мы не можем выбрать 5 или больше, потому что оставшийся выбор должен добавить по крайней мере 1, а также потому, что мы выбрали 5 в прошлый раз. Нам также нужно выбрать как минимум 3, потому что, если мы выберем только 2, оставшийся выбор может быть только 1, для общего количества 14. Мы выбираем случайное значение от 3 до 4, скажем, 4.
  • У нас 1 осталось. Как оказалось, алгоритм выбирает диапазон от 1 до 1, и мы выбираем 1 в качестве конечного числа.
Нил
источник
1

JavaScript, 647 291 261 260 259 251 239 байт

Спасибо @Veskah за -10 байт в оригинальной версии и «О, да, вы выводите все наборы, тогда как для вызова требуется случайный набор»

(n,g=m=n**2,r=[...Array(g||1)].map(_=>m--).sort(_=>.5-Math.random()).slice(-n),c=_=>eval(r.join`+`),i=_=>r.includes(_))=>[...{*0(){while(g>1&&c()!=g){for(z of r){y=c();r[m++%n]=y>g&&!(!(z-1)||i(z-1))?z-1:y<g&&!i(z+1)?z+1:z}}yield*r}}[0]()]

Попробуйте онлайн!

Создайте массив n^2индексов на основе 1, случайным образом отсортируйте массив, нарежьте nэлементы из массива. При этом сумма случайных элементов не равна n^2циклу массива случайных элементов; если сумма элементов массива больше чем n^2и текущий элемент -1не равен нулю или текущий элемент -1не находится в текущем массиве, вычтите 1; если сумма массива меньше, чем n^2текущий элемент +1отсутствует в массиве, добавьте 1к элементу. Если сумма массива равна n^2разрывному циклу, выведите массив.

guest271314
источник
1
637 байт , потянув z.join в переменную, иk++
Veskah
@Veskah Два цикла, whileвероятно, также можно сократить до тела одной функции, которая принимает параметры; и может заменить условные операторы (троичные) для if..elseоператоров; среди других частей кода, которые, скорее всего, могут быть скорректированы для гольфа; например, удаление letзаявлений.
guest271314
@Veskah 601 байт без замены троичного дляif..else
guest271314
1
О да, вы выводите все наборы, в то время как вызов требует случайного возврата (подробности см. В комментариях к ОП)
Веска
@Veskah Должно быть, неправильно истолковали задачу и примеры или были слишком сосредоточены на решении этой части вопроса « Бонусное задание: есть ли формула для расчета количества действительных перестановок для данного n, тестирование , если алгоритм последовательно возвращенное ожидаемый результат для n^2вывода массивов , генерируемых в одном вызове функции, и одновременно с учетом сходства на этот вопрос N-мерный N ^ N массив заполнен N .
guest271314
0

Japt , 20 байт

²õ ö¬oU íUõ+)Õæ@²¥Xx

Попробуйте онлайн!

Чрезвычайно сильно использует «неравномерную» случайность, почти всегда выводит первые nнечетные числа, которые суммируются с n^2. Теоретически он может вывести любой другой допустимый набор, хотя я смог подтвердить это только для малого n.

Объяснение:

²õ                      :Generate the range [1...n^2]
   ö¬                   :Order it randomly
     oU                 :Get the last n items
        í   )Õ          :Put it in an array with...
         Uõ+            : The first n odd numbers
              æ_        :Get the first one where...
                  Xx    : The sum
                ²¥      : equals n^2
Камил Дракари
источник
0

C (gcc) , 128 125 байтов

p(_){printf("%d ",_);}f(n,x,y,i){x=n*n;y=1;for(i=0;++i<n;p(y),x-=y++)while(rand()&&(n-i)*(n-i+1)/2+(n-i)*(y+1)+y<x)y++;p(x);}

Попробуйте онлайн!

-3 байта благодаря потолку

ПРИМЕЧАНИЕ: вероятность очень очень далеко от равномерной. См. Объяснение того, что я имею в виду, и лучший способ проверить, работает ли он (сделав распределение ближе к равномерному [но все еще очень далеким от него]).

Как?

Основная идея состоит в том, чтобы выбирать только увеличивающиеся числа, чтобы не беспокоиться о дубликатах. Всякий раз, когда мы выбираем число, у нас есть ненулевой шанс «пропустить» его, если это допустимо.

xky

y+(y+1)+(y+2)+...
x
k(k+1)2+k(y+1)+y<x

Тем не менее логика заключается в том, чтобы иметь возможность отбросить любое, yкоторое удовлетворяет приведенному выше уравнению.

Код

p(_){printf("%d ",_);}  // Define print(int)
f(n,x,y,i){             // Define f(n,...) as the function we want
    x=n*n;              // Set x to n^2
    y=1;                // Set y to 1
    for(i=0;++i<n;){    // n-1 times do...
        while(rand()&&  // While rand() is non-zero [very very likely] AND
            (n-i)*      // (n-i) is the 'k' in the formula
            (n-i+1)/2+  // This first half takes care of the increment
            (n-i)*(y+1) // This second half takes care of the y+1 starting point
            +y<x)       // The +y takes care of the current value of y
        y++;            // If rand() returned non-zero and we can skip y, do so
    p(y);               // Print y
    x-=y++;             // Subtract y from the total and increment it
    }p(x);}             // Print what's left over.

Уловка, которую я упомянул для лучшего тестирования кода, заключается в замене rand()&&на rand()%2&&так, что есть вероятность 50-50, что любой заданный y будет пропущен, а не 1, RAND_MAXесли любой заданный y будет использован.

LambdaBeta
источник
Я был бы рад, если бы кто-нибудь проверил мою математику на последовательность. Мне также интересно, может ли этот тип решения упростить задачу с равномерной случайной скоростью. Формула устанавливает верхнюю и нижнюю границы ответа, приводит ли равномерное случайное число в этом диапазоне к равномерным случайным результатам? Я не понимаю, почему нет - но я давно не делал много комбинаторики.
LambdaBeta
Предлагаю p(y),x-=y++)while(rand()&&(i-n)*((~n+i)/2+~y)+y<x)y++;вместо){while(rand()&&(n-i)*(n-i+1)/2+(n-i)*(y+1)+y<x)y++;p(y);x-=y++;}
floorcat
@ceilingcat Мне нравятся эти небольшие улучшения, которые вы найдете. Я всегда так фокусируюсь на общем алгоритме, который забываю оптимизировать для реализации (я в основном перехожу в режим игры в гольф с автопилотом, когда у меня работает источник без игры в гольф, поэтому я скучаю по многим
сборам
Эй, не только у вас есть эти синтаксические гольфы. Я нахожу небольшие улучшения во многих ответах на C / C ++, подобных этим (кроме ваших, @ceilingcat обычно их подбирает).
Захари
Да, я заметил, что вы, наверное, самые активные клюшки на C / C ++ (можем ли мы использовать put, чтобы расширить аналогию с гольфом до нескольких последних ударов? Почему нет!). Меня всегда впечатляет, что вы можете понять код игры в гольф достаточно хорошо, чтобы улучшить его.
LambdaBeta
0

Mathematica 40 байтов

RandomChoice[IntegerPartitions[n^2, {n}]]
Дэвид Дж. Аист
источник
1
Прежде всего это n ^ 2, а не 2 ^ n. Во-вторых, ваша программа должна быть функциональной, а также гольфовой. Попробуйте это RandomChoice@IntegerPartitions[#^2,{#}]&
J42161217
1
Также результат должен быть (неупорядоченным, уникальным), но эта функция не работает в обоих случаях
J42161217
0

Wolfram Language (Mathematica) , 49 байтов

(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&

Попробуйте онлайн!

Гольф версия от @ J42161217.


Wolfram Language (Mathematica) , 62 байта

Range[#-1,0,-1]+RandomChoice@IntegerPartitions[#*(#+1)/2,{#}]&

Попробуйте онлайн!

Как это работает

n2nn2(n2n)/2=(n2+n)/20n1n10


Ответ на Бонусное задание

Бонусное задание: существует ли формула для расчета количества действительных перестановок для данного n?

part(n,k)nk

part(n,k)=part(n1,k1)+part(nk,k)

part(n,1)=1n<kpart(n,k)=0

part(n2+n2,n)

что в Mathematica:

Length@IntegerPartitions[#*(#+1)/2,{#}]&

Попробуйте онлайн!

фонтанчик для питья
источник
Это код гольфа .. 49 байтов(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
J42161217