26
\$\begingroup\$

Randomness is fun. Challenges with no point are fun.

Write a function that, given integer input n, will output a set (unordered, unique) of exactly n random integers between 1 and n^2 (inclusive) such that the sum of all integers is equal to n^2.

Randomness does not have to be uniform, provided each valid set has a non-zero chance to occur.

Shortest answer in bytes (per each language) wins.

Examples

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

Bonus Task: Is there a formula to calculate the number of valid permutations for a given n?

\$\endgroup\$
19
  • 2
    \$\begingroup\$ related, but quite different \$\endgroup\$
    – Giuseppe
    Nov 20, 2018 at 14:49
  • 1
    \$\begingroup\$ (p/s: If you have a fast algorithm but takes more bytes, consider waiting until the speed edition (currently in sandbox) to post it.) \$\endgroup\$
    – DELETE_ME
    Nov 20, 2018 at 15:04
  • 1
    \$\begingroup\$ @EriktheOutgolfer Although there are (much) better ways than generating all sets and pick a random one, they're much harder to implement and likely longer. Keep them for the speed edition. \$\endgroup\$
    – DELETE_ME
    Nov 20, 2018 at 15:08
  • 2
    \$\begingroup\$ The number of sets is OEIS A107379. \$\endgroup\$
    – nwellnhof
    Nov 20, 2018 at 23:16
  • 1
    \$\begingroup\$ It's both. See the comment "Also the number of partitions of n^2 into n distinct parts." \$\endgroup\$
    – nwellnhof
    Nov 21, 2018 at 3:31

24 Answers 24

9
\$\begingroup\$

Brachylog (v2), 15 bytes (random) or 13 bytes (all possibilities)

Random

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

Try it online!

Function submission (seen in TIO with a wrapper making it into a full program).

Explanation

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

All possibilities

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

Try it online!

Function submission, which generates all possible outputs.

Explanation

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

I'm fairly surprised that ∧≜ works (you'd normally have to write ∧~≜ in order to brute-force the output rather than the input), but it turns out that has an input=output assumption so it doesn't matter which way round you run it.

Bonus task

In order to get some insight into the sequence of the number of possibilities, I created a different TIO wrapper which runs the program on successive integers to give the sequence of output counts:

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

A trip to OEIS discovers that this is already a known sequence, A107379, described pretty much as in the question (apparently you get the same sequence if you restrict it to odd numbers). The page lists several formulas for the sequence (although none is particularly simple; the second looks like a direct formula for the value but I don't understand the notation).

\$\endgroup\$
4
  • \$\begingroup\$ The second formula is "the coefficient of x^(n*(n-1)/2) in the series expansion of Product_{k=1..n} 1/(1 - x^k)" (not direct at all, unfortunately) \$\endgroup\$
    – DELETE_ME
    Nov 20, 2018 at 17:18
  • \$\begingroup\$ Placing the "all different" constraint before the random labelization step (e.g. A≠≜₁ᵐ) makes the run time much faster on average. \$\endgroup\$
    – Fatalize
    Nov 21, 2018 at 8:54
  • \$\begingroup\$ I don't understand why you made this a community wiki. Those are an archaic way to have editable posts before it was possible to edit. \$\endgroup\$
    – pipe
    Nov 21, 2018 at 15:32
  • \$\begingroup\$ @pipe codegolf.stackexchange.com/questions/172716/true-color-code/… \$\endgroup\$ Nov 21, 2018 at 17:04
7
\$\begingroup\$

05AB1E, 11 bytes

nÅœʒDÙQ}sùΩ

Try it online or verify all test cases.

Explanation:

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)
\$\endgroup\$
5
\$\begingroup\$

Python (2 or 3), 85 bytes

def f(n):r=sample(range(1,n*n+1),n);return(n*n==sum(r))*r or f(n)
from random import*

Try it online!

\$\endgroup\$
5
\$\begingroup\$

R, 68, 75 48 bytes (random) and 70 bytes (deterministic)

@Giuseppe's rejection sampling method:

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

Try it online!

Golfed original:

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

Try it online!

The *!!1:2 business is to avoid the odd way sample act when the first argument has length 1.

\$\endgroup\$
9
  • \$\begingroup\$ @Giuseppe "fixed" :-) \$\endgroup\$
    – ngm
    Nov 20, 2018 at 18:57
  • \$\begingroup\$ very nice. using p directly as an index instead of calculating it and re-using it should save some bytes. \$\endgroup\$
    – Giuseppe
    Nov 20, 2018 at 18:59
  • 1
    \$\begingroup\$ I have function(n){while(sum(F)!=n^2)F=sample(n^2,n);F} for 48 as well... \$\endgroup\$
    – Giuseppe
    Nov 20, 2018 at 19:00
  • 1
    \$\begingroup\$ @J.Doe to avoid the issue when calling something like sample(2,1) which happens with n=2. So rep just guarantees that this will never happen. There might be a better way but this was quick and I was mad at sample. \$\endgroup\$
    – ngm
    Nov 20, 2018 at 20:17
  • 1
    \$\begingroup\$ You can save a byte with x*!!1:2 over rep(x,2) if your meta question gets a no. \$\endgroup\$
    – J.Doe
    Nov 20, 2018 at 20:35
4
\$\begingroup\$

Jelly, 9 bytes

²œcS=¥Ƈ²X

Try it online!

Generate all n-combinations of the list [1..n²], filter to keep those with sum n², then pick a random one.

\$\endgroup\$
0
4
\$\begingroup\$

Java 10, 250 242 222 bytes

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 bytes thanks to @nwellnhof.

Watch out, Java coming through.. It's 'only' five times as long as the other four answers combined, so not too bad I guess.. rofl.
It does run n=1 through n=25 (combined) in less than 2 seconds though, so I'll probably post a modified version to the speed version of this challenge (that's currently still in the Sandbox) as well.

Try it online.

Explanation:

In pseudo-code we do the following:

1) Generate an array of size n+1 containing: 0, n squared, and n-1 amount of random integers in the range [0, n squared)
2) Sort this array
3) Create a second array of size n containing the forward differences of pairs
These first three steps will give us an array containing n random integers (in the range [0, n squared) that sum to n squared.
4a) If not all random values are unique, or any of them is 0: try again from step 1
4b) Else: return this differences array as result

As for the actual code:

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)
\$\endgroup\$
10
  • 1
    \$\begingroup\$ n=25 in under 2 seconds is impressive! I'll have to read through the explanation and see how it does it. Is it still a bruteforce method? \$\endgroup\$
    – Mayube
    Nov 20, 2018 at 16:59
  • \$\begingroup\$ Is it uniform? - \$\endgroup\$
    – DELETE_ME
    Nov 20, 2018 at 17:13
  • \$\begingroup\$ @user202729 Although I'm not sure how to prove it, I think it is. The Java builtin is uniform, and it uses that to get random values in the range [0, n squared) first, and then calculates the differences between those sorted random values (including leading 0 and trailing n squared. So I'm pretty sure those differences are uniform as well. But again, I'm not sure how to prove it. Uniformity in randomness isn't really my expertise tbh. \$\endgroup\$ Nov 20, 2018 at 17:27
  • 3
    \$\begingroup\$ You never read from the differences array d or am I missing something? \$\endgroup\$
    – nwellnhof
    Nov 20, 2018 at 21:31
  • 1
    \$\begingroup\$ I'm kind of happy with my 127 bytes solution :D \$\endgroup\$ Nov 21, 2018 at 9:26
4
\$\begingroup\$

Perl 6, 41 bytes

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

Try it online!

  • (1 .. $_²) is the range of numbers from 1 to the square of the input number
  • .pick($_) randomly chooses a distinct subset of that range
  • xx * replicates the preceding expression infinitely
  • first *.sum == $_² selects the first of those number sets that sums to the square of the input number
\$\endgroup\$
1
  • \$\begingroup\$ 40 bytes \$\endgroup\$
    – Jo King
    Nov 20, 2018 at 21:59
2
\$\begingroup\$

Pyth, 13 12 bytes

Ofq*QQsT.cS*

Try it online here. Note that the online interpreter runs into a MemoryError for inputs greater than 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

Edit: saved a byte by taking an alternative approach. Previous version: Of&qQlT{IT./*

\$\endgroup\$
2
\$\begingroup\$

Python 3, 136 134 127 121 114 bytes

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)

Try it online!

A commenter corrected me, and this now hits recursion max depth at f(5) instead of f(1). Much closer to being a real competing answer.

I've seen it do f(5) once, and I'm working on trying to implement this with shuffle.

I tried making some lambda expressions for s=..., but that didn't help on bytes. Maybe someone else can do something with this: s=(lambda n:{randint(1,n*n)for _ in range(n)})(n)

Thanks to Kevin for shaving off another 7 bytes.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ So this uses recursion to "regenerate" the set if the one generated is invalid? Definitely something wrong with your code if it's hitting recursion depth at f(1), the only possible array that should be generable at n=1 is [1] Also there's a lot of extraneous whitespace to be removed here. Remember this is a code-golf challenge, so the goal is to achieve the lowest bytecount \$\endgroup\$
    – Mayube
    Nov 20, 2018 at 18:32
  • 1
    \$\begingroup\$ range(1,n) -> range(n) I believe should resolve the bug. \$\endgroup\$ Nov 20, 2018 at 18:34
  • 1
    \$\begingroup\$ This should fix your bug, and also removes extraneous whitespace. I imagine there's a lot more room for golfing too \$\endgroup\$
    – Mayube
    Nov 20, 2018 at 18:35
  • 1
    \$\begingroup\$ Although the recursion slightly worsens from 5 to 4, you can combine your two return statements like this: return len(s)==n and sum(s)==n*n and s or f(n) (Try it online 114 bytes). \$\endgroup\$ Nov 20, 2018 at 19:38
  • 1
    \$\begingroup\$ You can have it all on one line. 111 bytes \$\endgroup\$
    – Jo King
    Nov 20, 2018 at 22:02
2
\$\begingroup\$

APL (Dyalog Unicode), 20 bytesSBCS

Anonymous prefix lambda.

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

Try it online!

{} "dfn"; is argument

⍵*2 square the argument

s← assign to s (for square)

⍵? find n random indices from 1…s without replacement

c← assign to c (for candidate)

+/ sum them

s= compare to s

: if equal

  c return the candidate

 else

  ∇⍵ recurse on the argument

\$\endgroup\$
7
  • \$\begingroup\$ did you see my and H.PWiz's 18 bytes? \$\endgroup\$
    – ngn
    Nov 25, 2018 at 16:21
  • \$\begingroup\$ @ngn No, clearly not, but I checked that no APL solution was posted before I posted. Why didn't any of you‽ \$\endgroup\$
    – Adám
    Nov 25, 2018 at 16:26
  • \$\begingroup\$ well, once i've golfed it and shown it to the orchard, there's hardly any incentive to post :) \$\endgroup\$
    – ngn
    Nov 25, 2018 at 16:30
  • \$\begingroup\$ @ngn For you, no, but for me there is. \$\endgroup\$
    – Adám
    Nov 25, 2018 at 16:36
  • 1
    \$\begingroup\$ certainly, and i think you're doing a great job popularizing apl here. i was just making sure you know shorter solutions have been found and it's probably better to explain one of them (or a variation) instead \$\endgroup\$
    – ngn
    Nov 25, 2018 at 18:24
2
\$\begingroup\$

APL (Dyalog Classic), 18 bytes

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

Try it online!

uses ⎕io←1

generates the numbers 1 2 ... n

(...)⍣(...) keep applying the function on the left until the function on the right returns true

length, i.e. n

≢?≢×≢ choose randomly n distinct integers between 1 and n2

+.-∘≢ subtract the length from each number and sum

0= if the sum is 0, stop looping, otherwise try again

\$\endgroup\$
1
\$\begingroup\$

MATL, 18 13 bytes

`xGU:GZrtsGU-

Try it online!

`	# 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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I wouldn't try this in R - random characters almost never produce a valid program. \$\endgroup\$
    – ngm
    Nov 20, 2018 at 18:48
  • \$\begingroup\$ @ngm hahaha I suppose an explanation is in order. \$\endgroup\$
    – Giuseppe
    Nov 20, 2018 at 18:48
1
\$\begingroup\$

Japt, 12 bytes

²õ àU ö@²¥Xx

Try it

                 :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
\$\endgroup\$
2
  • \$\begingroup\$ According to a comment made by the OP, order of elements in the output is irrelevant so à should be fine. \$\endgroup\$ Nov 20, 2018 at 18:52
  • \$\begingroup\$ Thanks, @KamilDrakari. Updated. \$\endgroup\$
    – Shaggy
    Nov 20, 2018 at 19:15
1
\$\begingroup\$

Java (JDK), 127 bytes

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

Try it online!

Infinite loop until a set with the criteria matches.

I hope you have the time, because it's very sloooooow! It can't even go to 10 without timing out.

\$\endgroup\$
3
  • \$\begingroup\$ You can golf 3 bytes by changing if(r.size()==n&s==0) to if(r.size()+s==n). \$\endgroup\$ Nov 22, 2018 at 21:35
  • \$\begingroup\$ @KevinCruijssen I've thought about it too, but no I can't because s could be -1 and n could be size() - 1. \$\endgroup\$ Nov 22, 2018 at 22:03
  • \$\begingroup\$ Ah wait, you keep adding items to the set as long as s>0, so the size can be larger than n. Ok, in that case it indeed doesn't work. n is a constant, but unfortunately both s and r.size() are variables that can be both below or above 0 and n respectively. \$\endgroup\$ Nov 23, 2018 at 11:53
1
\$\begingroup\$

Batch, 182 145 bytes

@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%%

Explanation: Calculates the minimum and maximum allowable pick, given that the numbers are to be picked in descending order, and chooses a random value within the range. Example for an input of 4:

  • We start with 16 left. We can't pick 11 or more because the remaining 3 picks must add to at least 6. We also need to pick at least 6, because if we only pick 5, the remaining 3 picks can only add to 9, which isn't enough for 16. We pick a random value from 6 to 10, say 6.
  • We have 10 left. We can't pick 8 or more because the remaining 2 picks must add to at least 3. As it happens, we can't pick 6 or more because we picked 6 last time. We also need to pick at least 5, because if we only pick 4, the remaining 2 picks can only add to 5, for a grand total of 15. We pick a random value from 5 to 5, say 5 (!).
  • We have 5 left. We can't pick 5 or more because the remaining pick must add to at least 1, and also because we picked 5 last time. We also need to pick at least 3, because if we only pick 2, the remaining pick can only be 1, for a grand total of 14. We pick a random value from 3 to 4, say 4.
  • We have 1 left. As it turns out, the algorithm chooses a range of 1 to 1, and we pick 1 as the final number.
\$\endgroup\$
1
\$\begingroup\$

JavaScript, 647 291 261 260 259 251 239 bytes

Thanks to @Veskah for -10 bytes at original version and "Oh yeah, you're outputting all the sets whereas the challenge asks for a random one to be returned"

(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]()]

Try it online!

Create an array of n^2 1-based indexes, sort array randomly, slice n elements from array. While the sum of the random elements does not equal n^2 loop array of random elements; if sum of array elements is greater than n^2 and current element -1 does not equal zero or current element -1 is not in current array, subtract 1; if sum of array is less than n^2 and current element +1 is not in array, add 1 to element. If array sum is equal to n^2 break loop, output array.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ 637 bytes by pulling z.join into a variable, and k++ \$\endgroup\$
    – Veskah
    Nov 22, 2018 at 23:51
  • \$\begingroup\$ @Veskah The two while loops could probably also be reduced to the body of a single function which accepts parameters; and could substitute conditional operators (ternary) for the if..else statements; among other portions of the code that could more than likely be adjusted for golf; i.e.g., removing let statements. \$\endgroup\$ Nov 23, 2018 at 0:00
  • \$\begingroup\$ @Veskah 601 bytes without substituting ternary for if..else \$\endgroup\$ Nov 23, 2018 at 0:06
  • 1
    \$\begingroup\$ Oh yeah, you're outputting all the sets whereas the challenge asks for a random one to be returned (See the OP comments for more details) \$\endgroup\$
    – Veskah
    Nov 23, 2018 at 0:11
  • \$\begingroup\$ @Veskah Must have misinterpreted the challenge and examples, or was too focused on solving this part of the question "Bonus Task: Is there a formula to calculate the number of valid permutations for a given n?". testing if the algorithm consistently returned expected result for n^2 output arrays generated in a single call to the function, and simultaneously considering the similarities to this question N-dimensional N^N array filled with N. \$\endgroup\$ Nov 23, 2018 at 0:22
0
\$\begingroup\$

Japt, 20 bytes

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

Try it online!

Extremely heavily takes advantage of "Non-uniform" randomness, almost always outputs the first n odd numbers, which happens to sum to n^2. In theory it can output any other valid set, though I've only been able to confirm that for small n.

Explanation:

²õ                      :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
\$\endgroup\$
0
\$\begingroup\$

Ruby, 46 bytes

->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 128 125 bytes

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

Try it online!

-3 bytes thanks to ceilingcat

NOTE: The probability is very very far from uniform. See explanation for what I mean and a better means to test that it works (by making the distribution closer to uniform [but still a far cry from it]).

How?

The basic idea is to only choose increasing numbers so as to not worry about duplicates. Whenever we pick a number we have a non-zero chance of 'skipping' it if allowable.

To decide if we can skip a number we need to know x the total left to be reached, k the number of elements we still have to use, and y the current candidate value. The smallest possible number that we could still pick would consist of $$y+(y+1)+(y+2)+...$$ added to the current value. In particular we require the above expression to be less than x. The formula will be $$\frac{k(k+1)}{2}+k(y+1)+y<x$$ Unfortunately we have to be a bit careful about rearranging this formula due to integer truncation in C, so I couldn't really find a way to golf it.

Nonetheless the logic is to have a chance to discard any y that satisfies the above equation.

The code

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.

The trick I mentioned to better test the code involves replacing rand()&& with rand()%2&& so that there is a 50-50 chance that any given y is skipped, rather than a 1 in RAND_MAX chance that any given y is used.

\$\endgroup\$
5
  • \$\begingroup\$ I would love it if someone checked my math for consistency. I also wonder if this type of solution could make the uniform random speed challenge simple. The formula places an upper and lower bound on the answer, does a uniform random number in that range result in uniform random results? I don't see why not - but I haven't done much combinatorics in awhile. \$\endgroup\$
    – LambdaBeta
    Nov 20, 2018 at 22:43
  • \$\begingroup\$ Suggest p(y),x-=y++)while(rand()&&(i-n)*((~n+i)/2+~y)+y<x)y++; instead of ){while(rand()&&(n-i)*(n-i+1)/2+(n-i)*(y+1)+y<x)y++;p(y);x-=y++;} \$\endgroup\$
    – ceilingcat
    Nov 20, 2018 at 23:30
  • \$\begingroup\$ @ceilingcat I love these little improvements you find. I always get so focussed on the overall algorithm I forget to optimize for implementation (I basically go autopilot golfing mode once I have a non-golfed source that works - so I miss a lot of savings) \$\endgroup\$
    – LambdaBeta
    Nov 21, 2018 at 15:46
  • \$\begingroup\$ Hey, it's not just you who has those syntax-golfs. I find little improvements in a lot of C/C++ answers like that (except not in yours, @ceilingcat usually snaps those up). \$\endgroup\$
    – Adalynn
    Nov 21, 2018 at 17:47
  • \$\begingroup\$ Yeah, I've noticed that you two are probably the most active C/C++ putters (can we use putting to extend the golf analogy to the last few strokes? Why not!). It always impresses me that you can even understand the golfed code well enough to improve it. \$\endgroup\$
    – LambdaBeta
    Nov 21, 2018 at 18:30
0
\$\begingroup\$

Clean, 172 bytes

import StdEnv,Math.Random,Data.List
? ::!Int->Int
?_=code{
ccall time "I:I"
}
$n=find(\s=length s==n&&sum s==n^2)(subsequences(nub(map(inc o\e=e rem n^2)(genRandInt(?0)))))

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Python (2 or 3), 84 bytes

from random import*;l=lambda n,s=[]:(sum(s)==n*n)*s or l(n,sample(range(1,n*n+1),n))

Try it online!

Hits max recursion depth at around l(5)

\$\endgroup\$
0
\$\begingroup\$

Kotlin, 32 bytes

{(1..it*it).shuffled().take(it)}

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The sum needs to be n^2 \$\endgroup\$
    – 12Me21
    Nov 24, 2018 at 14:12
0
\$\begingroup\$

Mathematica 40 bytes

RandomChoice[IntegerPartitions[n^2, {n}]]
\$\endgroup\$
2
  • 1
    \$\begingroup\$ First of all it is n^2, not 2^n. Secondly, your program must be a function and also a golfed one. Try this RandomChoice@IntegerPartitions[#^2,{#}]& \$\endgroup\$
    – ZaMoC
    Nov 25, 2018 at 11:04
  • 1
    \$\begingroup\$ Also the result must be (unordered, unique) but this function fails in both \$\endgroup\$
    – ZaMoC
    Nov 25, 2018 at 11:21
0
\$\begingroup\$

Wolfram Language (Mathematica), 49 bytes

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

Try it online!

Golfed version by @J42161217.


Wolfram Language (Mathematica), 62 bytes

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

Try it online!

How it works

Mainly based on this Math.SE question. In order to get partitions of \$n^2\$ into \$n\$ distinct parts, get partitions of \$n^2 - (n^2-n)/2 = (n^2+n)/2\$ instead and add \$0 \cdots n-1\$ to each element. Since Mathematica gives the partitions in decreasing order, \$n-1 \cdots 0\$ is added instead.


The answer to the Bonus Task

Bonus Task: Is there a formula to calculate the number of valid permutations for a given n?

Yes. Define \$part(n,k)\$ as the number of partitions of \$n\$ into exactly \$k\$ parts. Then it satisfies the following recurrence relation:

$$ part(n,k) = part(n-1,k-1) + part(n-k,k) $$

You can understand it as "If a partition contains a 1, remove it; otherwise, subtract 1 from every term". More explanation here on another Math.SE question. Combined with the initial conditions \$ part(n,1) = 1 \$ and \$ n < k \Rightarrow part(n,k) = 0 \$, you can compute it with a program. The desired answer will be:

$$ part(\frac{n^2+n}{2}, n) $$

which is, in Mathematica:

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

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ This is code golf.. 49 bytes (While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)& \$\endgroup\$
    – ZaMoC
    Nov 25, 2018 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.