Arbitrary Randomness
up vote
26
down vote
favorite
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
?
code-golf random combinatorics
|
show 14 more comments
up vote
26
down vote
favorite
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
?
code-golf random combinatorics
2
related, but quite different
– Giuseppe
Nov 20 at 14:49
1
(p/s: If you have a fast algorithm but takes more bytes, consider waiting until the speed edition (currently in sandbox) to post it.)
– user202729
Nov 20 at 15:04
1
@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.
– user202729
Nov 20 at 15:08
2
The number of sets is OEIS A107379.
– nwellnhof
Nov 20 at 23:16
1
It's both. See the comment "Also the number of partitions of n^2 into n distinct parts."
– nwellnhof
Nov 21 at 3:31
|
show 14 more comments
up vote
26
down vote
favorite
up vote
26
down vote
favorite
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
?
code-golf random combinatorics
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
?
code-golf random combinatorics
code-golf random combinatorics
edited Nov 21 at 9:15
nwellnhof
6,4751125
6,4751125
asked Nov 20 at 14:45
Skidsdev
6,2382972
6,2382972
2
related, but quite different
– Giuseppe
Nov 20 at 14:49
1
(p/s: If you have a fast algorithm but takes more bytes, consider waiting until the speed edition (currently in sandbox) to post it.)
– user202729
Nov 20 at 15:04
1
@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.
– user202729
Nov 20 at 15:08
2
The number of sets is OEIS A107379.
– nwellnhof
Nov 20 at 23:16
1
It's both. See the comment "Also the number of partitions of n^2 into n distinct parts."
– nwellnhof
Nov 21 at 3:31
|
show 14 more comments
2
related, but quite different
– Giuseppe
Nov 20 at 14:49
1
(p/s: If you have a fast algorithm but takes more bytes, consider waiting until the speed edition (currently in sandbox) to post it.)
– user202729
Nov 20 at 15:04
1
@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.
– user202729
Nov 20 at 15:08
2
The number of sets is OEIS A107379.
– nwellnhof
Nov 20 at 23:16
1
It's both. See the comment "Also the number of partitions of n^2 into n distinct parts."
– nwellnhof
Nov 21 at 3:31
2
2
related, but quite different
– Giuseppe
Nov 20 at 14:49
related, but quite different
– Giuseppe
Nov 20 at 14:49
1
1
(p/s: If you have a fast algorithm but takes more bytes, consider waiting until the speed edition (currently in sandbox) to post it.)
– user202729
Nov 20 at 15:04
(p/s: If you have a fast algorithm but takes more bytes, consider waiting until the speed edition (currently in sandbox) to post it.)
– user202729
Nov 20 at 15:04
1
1
@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.
– user202729
Nov 20 at 15:08
@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.
– user202729
Nov 20 at 15:08
2
2
The number of sets is OEIS A107379.
– nwellnhof
Nov 20 at 23:16
The number of sets is OEIS A107379.
– nwellnhof
Nov 20 at 23:16
1
1
It's both. See the comment "Also the number of partitions of n^2 into n distinct parts."
– nwellnhof
Nov 21 at 3:31
It's both. See the comment "Also the number of partitions of n^2 into n distinct parts."
– nwellnhof
Nov 21 at 3:31
|
show 14 more comments
24 Answers
24
active
oldest
votes
up vote
8
down vote
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).
The second formula is "the coefficient ofx^(n*(n-1)/2)
in the series expansion ofProduct_{k=1..n} 1/(1 - x^k)
" (not direct at all, unfortunately)
– user202729
Nov 20 at 17:18
Placing the "all different" constraint before the random labelization step (e.g.A≠≜₁ᵐ
) makes the run time much faster on average.
– Fatalize
Nov 21 at 8:54
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.
– pipe
Nov 21 at 15:32
@pipe codegolf.stackexchange.com/questions/172716/true-color-code/…
– guest271314
Nov 21 at 17:04
add a comment |
up vote
7
down vote
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)
add a comment |
up vote
5
down vote
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!
add a comment |
up vote
5
down vote
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.
@Giuseppe "fixed" :-)
– ngm
Nov 20 at 18:57
very nice. usingp
directly as an index instead of calculating it and re-using it should save some bytes.
– Giuseppe
Nov 20 at 18:59
1
I havefunction(n){while(sum(F)!=n^2)F=sample(n^2,n);F}
for 48 as well...
– Giuseppe
Nov 20 at 19:00
1
@J.Doe to avoid the issue when calling something likesample(2,1)
which happens withn=2
. Sorep
just guarantees that this will never happen. There might be a better way but this was quick and I was mad atsample
.
– ngm
Nov 20 at 20:17
1
You can save a byte withx*!!1:2
overrep(x,2)
if your meta question gets a no.
– J.Doe
Nov 20 at 20:35
|
show 4 more comments
up vote
4
down vote
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.
add a comment |
up vote
4
down vote
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)
1
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?
– Skidsdev
Nov 20 at 16:59
Is it uniform? -
– user202729
Nov 20 at 17:13
@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 leading0
and trailingn 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.
– Kevin Cruijssen
Nov 20 at 17:27
3
You never read from the differences arrayd
or am I missing something?
– nwellnhof
Nov 20 at 21:31
1
I'm kind of happy with my 127 bytes solution :D
– Olivier Grégoire
Nov 21 at 9:26
|
show 5 more comments
up vote
4
down vote
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
40 bytes
– Jo King
Nov 20 at 21:59
add a comment |
up vote
2
down vote
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./*
add a comment |
up vote
2
down vote
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.
1
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 atf(1)
, the only possible array that should be generable atn=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
– Skidsdev
Nov 20 at 18:32
1
range(1,n)
->range(n)
I believe should resolve the bug.
– Jonathan Allan
Nov 20 at 18:34
1
This should fix your bug, and also removes extraneous whitespace. I imagine there's a lot more room for golfing too
– Skidsdev
Nov 20 at 18:35
1
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).
– Kevin Cruijssen
Nov 20 at 19:38
1
You can have it all on one line. 111 bytes
– Jo King
Nov 20 at 22:02
|
show 1 more comment
up vote
2
down vote
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
did you see my and H.PWiz's 18 bytes?
– ngn
Nov 25 at 16:21
@ngn No, clearly not, but I checked that no APL solution was posted before I posted. Why didn't any of you‽
– Adám
Nov 25 at 16:26
well, once i've golfed it and shown it to the orchard, there's hardly any incentive to post :)
– ngn
Nov 25 at 16:30
@ngn For you, no, but for me there is.
– Adám
Nov 25 at 16:36
1
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
– ngn
Nov 25 at 18:24
|
show 2 more comments
up vote
2
down vote
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 n
2
+.-∘≢
subtract the length from each number and sum
0=
if the sum is 0, stop looping, otherwise try again
add a comment |
up vote
1
down vote
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
I wouldn't try this in R - random characters almost never produce a valid program.
– ngm
Nov 20 at 18:48
@ngm hahaha I suppose an explanation is in order.
– Giuseppe
Nov 20 at 18:48
add a comment |
up vote
1
down vote
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
According to a comment made by the OP, order of elements in the output is irrelevant soà
should be fine.
– Kamil Drakari
Nov 20 at 18:52
Thanks, @KamilDrakari. Updated.
– Shaggy
Nov 20 at 19:15
add a comment |
up vote
1
down vote
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.
You can golf 3 bytes by changingif(r.size()==n&s==0)
toif(r.size()+s==n)
.
– Kevin Cruijssen
Nov 22 at 21:35
@KevinCruijssen I've thought about it too, but no I can't because s could be -1 and n could be size() - 1.
– Olivier Grégoire
Nov 22 at 22:03
Ah wait, you keep adding items to the set as long ass>0
, so the size can be larger thann
. Ok, in that case it indeed doesn't work.n
is a constant, but unfortunately boths
andr.size()
are variables that can be both below or above0
andn
respectively.
– Kevin Cruijssen
Nov 23 at 11:53
add a comment |
up vote
1
down vote
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.
add a comment |
up vote
1
down vote
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.
1
637 bytes by pulling z.join into a variable, andk++
– Veskah
Nov 22 at 23:51
@Veskah The twowhile
loops could probably also be reduced to the body of a single function which accepts parameters; and could substitute conditional operators (ternary) for theif..else
statements; among other portions of the code that could more than likely be adjusted for golf; i.e.g., removinglet
statements.
– guest271314
Nov 23 at 0:00
@Veskah 601 bytes without substituting ternary forif..else
– guest271314
Nov 23 at 0:06
1
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)
– Veskah
Nov 23 at 0:11
@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 givenn
?". testing if the algorithm consistently returned expected result forn^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.
– guest271314
Nov 23 at 0:22
|
show 1 more comment
up vote
0
down vote
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
add a comment |
up vote
0
down vote
Ruby, 46 bytes
->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}
Try it online!
add a comment |
up vote
0
down vote
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.
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.
– LambdaBeta
Nov 20 at 22:43
Suggestp(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++;}
– ceilingcat
Nov 20 at 23:30
@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)
– LambdaBeta
Nov 21 at 15:46
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).
– Zacharý
Nov 21 at 17:47
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.
– LambdaBeta
Nov 21 at 18:30
add a comment |
up vote
0
down vote
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 oe=e rem n^2)(genRandInt(?0)))))
Try it online!
add a comment |
up vote
0
down vote
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)
add a comment |
up vote
0
down vote
Kotlin, 32 bytes
{(1..it*it).shuffled().take(it)}
Try it online!
1
The sum needs to be n^2
– 12Me21
Nov 24 at 14:12
add a comment |
up vote
0
down vote
Mathematica 40 bytes
RandomChoice[IntegerPartitions[n^2, {n}]]
1
First of all it is n^2, not 2^n. Secondly, your program must be a function and also a golfed one. Try thisRandomChoice@IntegerPartitions[#^2,{#}]&
– J42161217
Nov 25 at 11:04
1
Also the result must be (unordered, unique) but this function fails in both
– J42161217
Nov 25 at 11:21
add a comment |
up vote
0
down vote
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!
This is code golf.. 49 bytes(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
– J42161217
Nov 25 at 11:38
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "200"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f176284%2farbitrary-randomness%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
24 Answers
24
active
oldest
votes
24 Answers
24
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
8
down vote
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).
The second formula is "the coefficient ofx^(n*(n-1)/2)
in the series expansion ofProduct_{k=1..n} 1/(1 - x^k)
" (not direct at all, unfortunately)
– user202729
Nov 20 at 17:18
Placing the "all different" constraint before the random labelization step (e.g.A≠≜₁ᵐ
) makes the run time much faster on average.
– Fatalize
Nov 21 at 8:54
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.
– pipe
Nov 21 at 15:32
@pipe codegolf.stackexchange.com/questions/172716/true-color-code/…
– guest271314
Nov 21 at 17:04
add a comment |
up vote
8
down vote
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).
The second formula is "the coefficient ofx^(n*(n-1)/2)
in the series expansion ofProduct_{k=1..n} 1/(1 - x^k)
" (not direct at all, unfortunately)
– user202729
Nov 20 at 17:18
Placing the "all different" constraint before the random labelization step (e.g.A≠≜₁ᵐ
) makes the run time much faster on average.
– Fatalize
Nov 21 at 8:54
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.
– pipe
Nov 21 at 15:32
@pipe codegolf.stackexchange.com/questions/172716/true-color-code/…
– guest271314
Nov 21 at 17:04
add a comment |
up vote
8
down vote
up vote
8
down vote
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).
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).
edited Nov 20 at 15:30
community wiki
3 revs
ais523
The second formula is "the coefficient ofx^(n*(n-1)/2)
in the series expansion ofProduct_{k=1..n} 1/(1 - x^k)
" (not direct at all, unfortunately)
– user202729
Nov 20 at 17:18
Placing the "all different" constraint before the random labelization step (e.g.A≠≜₁ᵐ
) makes the run time much faster on average.
– Fatalize
Nov 21 at 8:54
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.
– pipe
Nov 21 at 15:32
@pipe codegolf.stackexchange.com/questions/172716/true-color-code/…
– guest271314
Nov 21 at 17:04
add a comment |
The second formula is "the coefficient ofx^(n*(n-1)/2)
in the series expansion ofProduct_{k=1..n} 1/(1 - x^k)
" (not direct at all, unfortunately)
– user202729
Nov 20 at 17:18
Placing the "all different" constraint before the random labelization step (e.g.A≠≜₁ᵐ
) makes the run time much faster on average.
– Fatalize
Nov 21 at 8:54
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.
– pipe
Nov 21 at 15:32
@pipe codegolf.stackexchange.com/questions/172716/true-color-code/…
– guest271314
Nov 21 at 17:04
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)– user202729
Nov 20 at 17:18
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)– user202729
Nov 20 at 17:18
Placing the "all different" constraint before the random labelization step (e.g.
A≠≜₁ᵐ
) makes the run time much faster on average.– Fatalize
Nov 21 at 8:54
Placing the "all different" constraint before the random labelization step (e.g.
A≠≜₁ᵐ
) makes the run time much faster on average.– Fatalize
Nov 21 at 8:54
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.
– pipe
Nov 21 at 15:32
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.
– pipe
Nov 21 at 15:32
@pipe codegolf.stackexchange.com/questions/172716/true-color-code/…
– guest271314
Nov 21 at 17:04
@pipe codegolf.stackexchange.com/questions/172716/true-color-code/…
– guest271314
Nov 21 at 17:04
add a comment |
up vote
7
down vote
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)
add a comment |
up vote
7
down vote
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)
add a comment |
up vote
7
down vote
up vote
7
down vote
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)
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)
edited Nov 20 at 15:08
answered Nov 20 at 14:55
Kevin Cruijssen
35.4k554186
35.4k554186
add a comment |
add a comment |
up vote
5
down vote
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!
add a comment |
up vote
5
down vote
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!
add a comment |
up vote
5
down vote
up vote
5
down vote
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!
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!
answered Nov 20 at 18:55
Jonathan Allan
50.6k534165
50.6k534165
add a comment |
add a comment |
up vote
5
down vote
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.
@Giuseppe "fixed" :-)
– ngm
Nov 20 at 18:57
very nice. usingp
directly as an index instead of calculating it and re-using it should save some bytes.
– Giuseppe
Nov 20 at 18:59
1
I havefunction(n){while(sum(F)!=n^2)F=sample(n^2,n);F}
for 48 as well...
– Giuseppe
Nov 20 at 19:00
1
@J.Doe to avoid the issue when calling something likesample(2,1)
which happens withn=2
. Sorep
just guarantees that this will never happen. There might be a better way but this was quick and I was mad atsample
.
– ngm
Nov 20 at 20:17
1
You can save a byte withx*!!1:2
overrep(x,2)
if your meta question gets a no.
– J.Doe
Nov 20 at 20:35
|
show 4 more comments
up vote
5
down vote
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.
@Giuseppe "fixed" :-)
– ngm
Nov 20 at 18:57
very nice. usingp
directly as an index instead of calculating it and re-using it should save some bytes.
– Giuseppe
Nov 20 at 18:59
1
I havefunction(n){while(sum(F)!=n^2)F=sample(n^2,n);F}
for 48 as well...
– Giuseppe
Nov 20 at 19:00
1
@J.Doe to avoid the issue when calling something likesample(2,1)
which happens withn=2
. Sorep
just guarantees that this will never happen. There might be a better way but this was quick and I was mad atsample
.
– ngm
Nov 20 at 20:17
1
You can save a byte withx*!!1:2
overrep(x,2)
if your meta question gets a no.
– J.Doe
Nov 20 at 20:35
|
show 4 more comments
up vote
5
down vote
up vote
5
down vote
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.
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.
edited Nov 21 at 16:23
answered Nov 20 at 18:47
ngm
3,11923
3,11923
@Giuseppe "fixed" :-)
– ngm
Nov 20 at 18:57
very nice. usingp
directly as an index instead of calculating it and re-using it should save some bytes.
– Giuseppe
Nov 20 at 18:59
1
I havefunction(n){while(sum(F)!=n^2)F=sample(n^2,n);F}
for 48 as well...
– Giuseppe
Nov 20 at 19:00
1
@J.Doe to avoid the issue when calling something likesample(2,1)
which happens withn=2
. Sorep
just guarantees that this will never happen. There might be a better way but this was quick and I was mad atsample
.
– ngm
Nov 20 at 20:17
1
You can save a byte withx*!!1:2
overrep(x,2)
if your meta question gets a no.
– J.Doe
Nov 20 at 20:35
|
show 4 more comments
@Giuseppe "fixed" :-)
– ngm
Nov 20 at 18:57
very nice. usingp
directly as an index instead of calculating it and re-using it should save some bytes.
– Giuseppe
Nov 20 at 18:59
1
I havefunction(n){while(sum(F)!=n^2)F=sample(n^2,n);F}
for 48 as well...
– Giuseppe
Nov 20 at 19:00
1
@J.Doe to avoid the issue when calling something likesample(2,1)
which happens withn=2
. Sorep
just guarantees that this will never happen. There might be a better way but this was quick and I was mad atsample
.
– ngm
Nov 20 at 20:17
1
You can save a byte withx*!!1:2
overrep(x,2)
if your meta question gets a no.
– J.Doe
Nov 20 at 20:35
@Giuseppe "fixed" :-)
– ngm
Nov 20 at 18:57
@Giuseppe "fixed" :-)
– ngm
Nov 20 at 18:57
very nice. using
p
directly as an index instead of calculating it and re-using it should save some bytes.– Giuseppe
Nov 20 at 18:59
very nice. using
p
directly as an index instead of calculating it and re-using it should save some bytes.– Giuseppe
Nov 20 at 18:59
1
1
I have
function(n){while(sum(F)!=n^2)F=sample(n^2,n);F}
for 48 as well...– Giuseppe
Nov 20 at 19:00
I have
function(n){while(sum(F)!=n^2)F=sample(n^2,n);F}
for 48 as well...– Giuseppe
Nov 20 at 19:00
1
1
@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
.– ngm
Nov 20 at 20:17
@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
.– ngm
Nov 20 at 20:17
1
1
You can save a byte with
x*!!1:2
over rep(x,2)
if your meta question gets a no.– J.Doe
Nov 20 at 20:35
You can save a byte with
x*!!1:2
over rep(x,2)
if your meta question gets a no.– J.Doe
Nov 20 at 20:35
|
show 4 more comments
up vote
4
down vote
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.
add a comment |
up vote
4
down vote
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.
add a comment |
up vote
4
down vote
up vote
4
down vote
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.
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.
answered Nov 20 at 15:05
user202729
13.9k12551
13.9k12551
add a comment |
add a comment |
up vote
4
down vote
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)
1
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?
– Skidsdev
Nov 20 at 16:59
Is it uniform? -
– user202729
Nov 20 at 17:13
@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 leading0
and trailingn 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.
– Kevin Cruijssen
Nov 20 at 17:27
3
You never read from the differences arrayd
or am I missing something?
– nwellnhof
Nov 20 at 21:31
1
I'm kind of happy with my 127 bytes solution :D
– Olivier Grégoire
Nov 21 at 9:26
|
show 5 more comments
up vote
4
down vote
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)
1
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?
– Skidsdev
Nov 20 at 16:59
Is it uniform? -
– user202729
Nov 20 at 17:13
@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 leading0
and trailingn 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.
– Kevin Cruijssen
Nov 20 at 17:27
3
You never read from the differences arrayd
or am I missing something?
– nwellnhof
Nov 20 at 21:31
1
I'm kind of happy with my 127 bytes solution :D
– Olivier Grégoire
Nov 21 at 9:26
|
show 5 more comments
up vote
4
down vote
up vote
4
down vote
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)
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)
edited Nov 20 at 22:29
answered Nov 20 at 16:20
Kevin Cruijssen
35.4k554186
35.4k554186
1
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?
– Skidsdev
Nov 20 at 16:59
Is it uniform? -
– user202729
Nov 20 at 17:13
@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 leading0
and trailingn 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.
– Kevin Cruijssen
Nov 20 at 17:27
3
You never read from the differences arrayd
or am I missing something?
– nwellnhof
Nov 20 at 21:31
1
I'm kind of happy with my 127 bytes solution :D
– Olivier Grégoire
Nov 21 at 9:26
|
show 5 more comments
1
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?
– Skidsdev
Nov 20 at 16:59
Is it uniform? -
– user202729
Nov 20 at 17:13
@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 leading0
and trailingn 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.
– Kevin Cruijssen
Nov 20 at 17:27
3
You never read from the differences arrayd
or am I missing something?
– nwellnhof
Nov 20 at 21:31
1
I'm kind of happy with my 127 bytes solution :D
– Olivier Grégoire
Nov 21 at 9:26
1
1
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?– Skidsdev
Nov 20 at 16:59
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?– Skidsdev
Nov 20 at 16:59
Is it uniform? -
– user202729
Nov 20 at 17:13
Is it uniform? -
– user202729
Nov 20 at 17:13
@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.– Kevin Cruijssen
Nov 20 at 17:27
@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.– Kevin Cruijssen
Nov 20 at 17:27
3
3
You never read from the differences array
d
or am I missing something?– nwellnhof
Nov 20 at 21:31
You never read from the differences array
d
or am I missing something?– nwellnhof
Nov 20 at 21:31
1
1
I'm kind of happy with my 127 bytes solution :D
– Olivier Grégoire
Nov 21 at 9:26
I'm kind of happy with my 127 bytes solution :D
– Olivier Grégoire
Nov 21 at 9:26
|
show 5 more comments
up vote
4
down vote
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
40 bytes
– Jo King
Nov 20 at 21:59
add a comment |
up vote
4
down vote
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
40 bytes
– Jo King
Nov 20 at 21:59
add a comment |
up vote
4
down vote
up vote
4
down vote
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
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
edited Nov 21 at 23:48
answered Nov 20 at 20:21
Sean
3,28636
3,28636
40 bytes
– Jo King
Nov 20 at 21:59
add a comment |
40 bytes
– Jo King
Nov 20 at 21:59
40 bytes
– Jo King
Nov 20 at 21:59
40 bytes
– Jo King
Nov 20 at 21:59
add a comment |
up vote
2
down vote
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./*
add a comment |
up vote
2
down vote
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./*
add a comment |
up vote
2
down vote
up vote
2
down vote
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./*
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./*
edited Nov 20 at 16:26
answered Nov 20 at 15:09
Sok
3,499722
3,499722
add a comment |
add a comment |
up vote
2
down vote
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.
1
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 atf(1)
, the only possible array that should be generable atn=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
– Skidsdev
Nov 20 at 18:32
1
range(1,n)
->range(n)
I believe should resolve the bug.
– Jonathan Allan
Nov 20 at 18:34
1
This should fix your bug, and also removes extraneous whitespace. I imagine there's a lot more room for golfing too
– Skidsdev
Nov 20 at 18:35
1
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).
– Kevin Cruijssen
Nov 20 at 19:38
1
You can have it all on one line. 111 bytes
– Jo King
Nov 20 at 22:02
|
show 1 more comment
up vote
2
down vote
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.
1
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 atf(1)
, the only possible array that should be generable atn=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
– Skidsdev
Nov 20 at 18:32
1
range(1,n)
->range(n)
I believe should resolve the bug.
– Jonathan Allan
Nov 20 at 18:34
1
This should fix your bug, and also removes extraneous whitespace. I imagine there's a lot more room for golfing too
– Skidsdev
Nov 20 at 18:35
1
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).
– Kevin Cruijssen
Nov 20 at 19:38
1
You can have it all on one line. 111 bytes
– Jo King
Nov 20 at 22:02
|
show 1 more comment
up vote
2
down vote
up vote
2
down vote
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.
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.
edited Nov 20 at 20:12
answered Nov 20 at 18:29
Gigaflop
2216
2216
1
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 atf(1)
, the only possible array that should be generable atn=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
– Skidsdev
Nov 20 at 18:32
1
range(1,n)
->range(n)
I believe should resolve the bug.
– Jonathan Allan
Nov 20 at 18:34
1
This should fix your bug, and also removes extraneous whitespace. I imagine there's a lot more room for golfing too
– Skidsdev
Nov 20 at 18:35
1
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).
– Kevin Cruijssen
Nov 20 at 19:38
1
You can have it all on one line. 111 bytes
– Jo King
Nov 20 at 22:02
|
show 1 more comment
1
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 atf(1)
, the only possible array that should be generable atn=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
– Skidsdev
Nov 20 at 18:32
1
range(1,n)
->range(n)
I believe should resolve the bug.
– Jonathan Allan
Nov 20 at 18:34
1
This should fix your bug, and also removes extraneous whitespace. I imagine there's a lot more room for golfing too
– Skidsdev
Nov 20 at 18:35
1
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).
– Kevin Cruijssen
Nov 20 at 19:38
1
You can have it all on one line. 111 bytes
– Jo King
Nov 20 at 22:02
1
1
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– Skidsdev
Nov 20 at 18:32
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– Skidsdev
Nov 20 at 18:32
1
1
range(1,n)
-> range(n)
I believe should resolve the bug.– Jonathan Allan
Nov 20 at 18:34
range(1,n)
-> range(n)
I believe should resolve the bug.– Jonathan Allan
Nov 20 at 18:34
1
1
This should fix your bug, and also removes extraneous whitespace. I imagine there's a lot more room for golfing too
– Skidsdev
Nov 20 at 18:35
This should fix your bug, and also removes extraneous whitespace. I imagine there's a lot more room for golfing too
– Skidsdev
Nov 20 at 18:35
1
1
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).– Kevin Cruijssen
Nov 20 at 19:38
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).– Kevin Cruijssen
Nov 20 at 19:38
1
1
You can have it all on one line. 111 bytes
– Jo King
Nov 20 at 22:02
You can have it all on one line. 111 bytes
– Jo King
Nov 20 at 22:02
|
show 1 more comment
up vote
2
down vote
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
did you see my and H.PWiz's 18 bytes?
– ngn
Nov 25 at 16:21
@ngn No, clearly not, but I checked that no APL solution was posted before I posted. Why didn't any of you‽
– Adám
Nov 25 at 16:26
well, once i've golfed it and shown it to the orchard, there's hardly any incentive to post :)
– ngn
Nov 25 at 16:30
@ngn For you, no, but for me there is.
– Adám
Nov 25 at 16:36
1
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
– ngn
Nov 25 at 18:24
|
show 2 more comments
up vote
2
down vote
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
did you see my and H.PWiz's 18 bytes?
– ngn
Nov 25 at 16:21
@ngn No, clearly not, but I checked that no APL solution was posted before I posted. Why didn't any of you‽
– Adám
Nov 25 at 16:26
well, once i've golfed it and shown it to the orchard, there's hardly any incentive to post :)
– ngn
Nov 25 at 16:30
@ngn For you, no, but for me there is.
– Adám
Nov 25 at 16:36
1
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
– ngn
Nov 25 at 18:24
|
show 2 more comments
up vote
2
down vote
up vote
2
down vote
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
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
answered Nov 25 at 10:56
Adám
28.5k269188
28.5k269188
did you see my and H.PWiz's 18 bytes?
– ngn
Nov 25 at 16:21
@ngn No, clearly not, but I checked that no APL solution was posted before I posted. Why didn't any of you‽
– Adám
Nov 25 at 16:26
well, once i've golfed it and shown it to the orchard, there's hardly any incentive to post :)
– ngn
Nov 25 at 16:30
@ngn For you, no, but for me there is.
– Adám
Nov 25 at 16:36
1
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
– ngn
Nov 25 at 18:24
|
show 2 more comments
did you see my and H.PWiz's 18 bytes?
– ngn
Nov 25 at 16:21
@ngn No, clearly not, but I checked that no APL solution was posted before I posted. Why didn't any of you‽
– Adám
Nov 25 at 16:26
well, once i've golfed it and shown it to the orchard, there's hardly any incentive to post :)
– ngn
Nov 25 at 16:30
@ngn For you, no, but for me there is.
– Adám
Nov 25 at 16:36
1
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
– ngn
Nov 25 at 18:24
did you see my and H.PWiz's 18 bytes?
– ngn
Nov 25 at 16:21
did you see my and H.PWiz's 18 bytes?
– ngn
Nov 25 at 16:21
@ngn No, clearly not, but I checked that no APL solution was posted before I posted. Why didn't any of you‽
– Adám
Nov 25 at 16:26
@ngn No, clearly not, but I checked that no APL solution was posted before I posted. Why didn't any of you‽
– Adám
Nov 25 at 16:26
well, once i've golfed it and shown it to the orchard, there's hardly any incentive to post :)
– ngn
Nov 25 at 16:30
well, once i've golfed it and shown it to the orchard, there's hardly any incentive to post :)
– ngn
Nov 25 at 16:30
@ngn For you, no, but for me there is.
– Adám
Nov 25 at 16:36
@ngn For you, no, but for me there is.
– Adám
Nov 25 at 16:36
1
1
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
– ngn
Nov 25 at 18:24
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
– ngn
Nov 25 at 18:24
|
show 2 more comments
up vote
2
down vote
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 n
2
+.-∘≢
subtract the length from each number and sum
0=
if the sum is 0, stop looping, otherwise try again
add a comment |
up vote
2
down vote
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 n
2
+.-∘≢
subtract the length from each number and sum
0=
if the sum is 0, stop looping, otherwise try again
add a comment |
up vote
2
down vote
up vote
2
down vote
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 n
2
+.-∘≢
subtract the length from each number and sum
0=
if the sum is 0, stop looping, otherwise try again
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 n
2
+.-∘≢
subtract the length from each number and sum
0=
if the sum is 0, stop looping, otherwise try again
answered Nov 25 at 18:32
ngn
6,67312459
6,67312459
add a comment |
add a comment |
up vote
1
down vote
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
I wouldn't try this in R - random characters almost never produce a valid program.
– ngm
Nov 20 at 18:48
@ngm hahaha I suppose an explanation is in order.
– Giuseppe
Nov 20 at 18:48
add a comment |
up vote
1
down vote
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
I wouldn't try this in R - random characters almost never produce a valid program.
– ngm
Nov 20 at 18:48
@ngm hahaha I suppose an explanation is in order.
– Giuseppe
Nov 20 at 18:48
add a comment |
up vote
1
down vote
up vote
1
down vote
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
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
edited Nov 20 at 19:09
answered Nov 20 at 18:37
Giuseppe
16.5k31052
16.5k31052
I wouldn't try this in R - random characters almost never produce a valid program.
– ngm
Nov 20 at 18:48
@ngm hahaha I suppose an explanation is in order.
– Giuseppe
Nov 20 at 18:48
add a comment |
I wouldn't try this in R - random characters almost never produce a valid program.
– ngm
Nov 20 at 18:48
@ngm hahaha I suppose an explanation is in order.
– Giuseppe
Nov 20 at 18:48
I wouldn't try this in R - random characters almost never produce a valid program.
– ngm
Nov 20 at 18:48
I wouldn't try this in R - random characters almost never produce a valid program.
– ngm
Nov 20 at 18:48
@ngm hahaha I suppose an explanation is in order.
– Giuseppe
Nov 20 at 18:48
@ngm hahaha I suppose an explanation is in order.
– Giuseppe
Nov 20 at 18:48
add a comment |
up vote
1
down vote
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
According to a comment made by the OP, order of elements in the output is irrelevant soà
should be fine.
– Kamil Drakari
Nov 20 at 18:52
Thanks, @KamilDrakari. Updated.
– Shaggy
Nov 20 at 19:15
add a comment |
up vote
1
down vote
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
According to a comment made by the OP, order of elements in the output is irrelevant soà
should be fine.
– Kamil Drakari
Nov 20 at 18:52
Thanks, @KamilDrakari. Updated.
– Shaggy
Nov 20 at 19:15
add a comment |
up vote
1
down vote
up vote
1
down vote
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
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
edited Nov 20 at 19:14
answered Nov 20 at 17:55
Shaggy
18.7k21663
18.7k21663
According to a comment made by the OP, order of elements in the output is irrelevant soà
should be fine.
– Kamil Drakari
Nov 20 at 18:52
Thanks, @KamilDrakari. Updated.
– Shaggy
Nov 20 at 19:15
add a comment |
According to a comment made by the OP, order of elements in the output is irrelevant soà
should be fine.
– Kamil Drakari
Nov 20 at 18:52
Thanks, @KamilDrakari. Updated.
– Shaggy
Nov 20 at 19:15
According to a comment made by the OP, order of elements in the output is irrelevant so
à
should be fine.– Kamil Drakari
Nov 20 at 18:52
According to a comment made by the OP, order of elements in the output is irrelevant so
à
should be fine.– Kamil Drakari
Nov 20 at 18:52
Thanks, @KamilDrakari. Updated.
– Shaggy
Nov 20 at 19:15
Thanks, @KamilDrakari. Updated.
– Shaggy
Nov 20 at 19:15
add a comment |
up vote
1
down vote
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.
You can golf 3 bytes by changingif(r.size()==n&s==0)
toif(r.size()+s==n)
.
– Kevin Cruijssen
Nov 22 at 21:35
@KevinCruijssen I've thought about it too, but no I can't because s could be -1 and n could be size() - 1.
– Olivier Grégoire
Nov 22 at 22:03
Ah wait, you keep adding items to the set as long ass>0
, so the size can be larger thann
. Ok, in that case it indeed doesn't work.n
is a constant, but unfortunately boths
andr.size()
are variables that can be both below or above0
andn
respectively.
– Kevin Cruijssen
Nov 23 at 11:53
add a comment |
up vote
1
down vote
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.
You can golf 3 bytes by changingif(r.size()==n&s==0)
toif(r.size()+s==n)
.
– Kevin Cruijssen
Nov 22 at 21:35
@KevinCruijssen I've thought about it too, but no I can't because s could be -1 and n could be size() - 1.
– Olivier Grégoire
Nov 22 at 22:03
Ah wait, you keep adding items to the set as long ass>0
, so the size can be larger thann
. Ok, in that case it indeed doesn't work.n
is a constant, but unfortunately boths
andr.size()
are variables that can be both below or above0
andn
respectively.
– Kevin Cruijssen
Nov 23 at 11:53
add a comment |
up vote
1
down vote
up vote
1
down vote
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.
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.
edited Nov 21 at 9:30
answered Nov 21 at 8:46
Olivier Grégoire
8,70711843
8,70711843
You can golf 3 bytes by changingif(r.size()==n&s==0)
toif(r.size()+s==n)
.
– Kevin Cruijssen
Nov 22 at 21:35
@KevinCruijssen I've thought about it too, but no I can't because s could be -1 and n could be size() - 1.
– Olivier Grégoire
Nov 22 at 22:03
Ah wait, you keep adding items to the set as long ass>0
, so the size can be larger thann
. Ok, in that case it indeed doesn't work.n
is a constant, but unfortunately boths
andr.size()
are variables that can be both below or above0
andn
respectively.
– Kevin Cruijssen
Nov 23 at 11:53
add a comment |
You can golf 3 bytes by changingif(r.size()==n&s==0)
toif(r.size()+s==n)
.
– Kevin Cruijssen
Nov 22 at 21:35
@KevinCruijssen I've thought about it too, but no I can't because s could be -1 and n could be size() - 1.
– Olivier Grégoire
Nov 22 at 22:03
Ah wait, you keep adding items to the set as long ass>0
, so the size can be larger thann
. Ok, in that case it indeed doesn't work.n
is a constant, but unfortunately boths
andr.size()
are variables that can be both below or above0
andn
respectively.
– Kevin Cruijssen
Nov 23 at 11:53
You can golf 3 bytes by changing
if(r.size()==n&s==0)
to if(r.size()+s==n)
.– Kevin Cruijssen
Nov 22 at 21:35
You can golf 3 bytes by changing
if(r.size()==n&s==0)
to if(r.size()+s==n)
.– Kevin Cruijssen
Nov 22 at 21:35
@KevinCruijssen I've thought about it too, but no I can't because s could be -1 and n could be size() - 1.
– Olivier Grégoire
Nov 22 at 22:03
@KevinCruijssen I've thought about it too, but no I can't because s could be -1 and n could be size() - 1.
– Olivier Grégoire
Nov 22 at 22:03
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.– Kevin Cruijssen
Nov 23 at 11:53
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.– Kevin Cruijssen
Nov 23 at 11:53
add a comment |
up vote
1
down vote
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.
add a comment |
up vote
1
down vote
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.
add a comment |
up vote
1
down vote
up vote
1
down vote
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.
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.
edited Nov 23 at 1:16
answered Nov 23 at 0:14
Neil
78.9k744175
78.9k744175
add a comment |
add a comment |
up vote
1
down vote
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.
1
637 bytes by pulling z.join into a variable, andk++
– Veskah
Nov 22 at 23:51
@Veskah The twowhile
loops could probably also be reduced to the body of a single function which accepts parameters; and could substitute conditional operators (ternary) for theif..else
statements; among other portions of the code that could more than likely be adjusted for golf; i.e.g., removinglet
statements.
– guest271314
Nov 23 at 0:00
@Veskah 601 bytes without substituting ternary forif..else
– guest271314
Nov 23 at 0:06
1
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)
– Veskah
Nov 23 at 0:11
@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 givenn
?". testing if the algorithm consistently returned expected result forn^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.
– guest271314
Nov 23 at 0:22
|
show 1 more comment
up vote
1
down vote
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.
1
637 bytes by pulling z.join into a variable, andk++
– Veskah
Nov 22 at 23:51
@Veskah The twowhile
loops could probably also be reduced to the body of a single function which accepts parameters; and could substitute conditional operators (ternary) for theif..else
statements; among other portions of the code that could more than likely be adjusted for golf; i.e.g., removinglet
statements.
– guest271314
Nov 23 at 0:00
@Veskah 601 bytes without substituting ternary forif..else
– guest271314
Nov 23 at 0:06
1
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)
– Veskah
Nov 23 at 0:11
@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 givenn
?". testing if the algorithm consistently returned expected result forn^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.
– guest271314
Nov 23 at 0:22
|
show 1 more comment
up vote
1
down vote
up vote
1
down vote
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.
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.
edited Nov 26 at 10:40
answered Nov 22 at 22:43
guest271314
317211
317211
1
637 bytes by pulling z.join into a variable, andk++
– Veskah
Nov 22 at 23:51
@Veskah The twowhile
loops could probably also be reduced to the body of a single function which accepts parameters; and could substitute conditional operators (ternary) for theif..else
statements; among other portions of the code that could more than likely be adjusted for golf; i.e.g., removinglet
statements.
– guest271314
Nov 23 at 0:00
@Veskah 601 bytes without substituting ternary forif..else
– guest271314
Nov 23 at 0:06
1
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)
– Veskah
Nov 23 at 0:11
@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 givenn
?". testing if the algorithm consistently returned expected result forn^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.
– guest271314
Nov 23 at 0:22
|
show 1 more comment
1
637 bytes by pulling z.join into a variable, andk++
– Veskah
Nov 22 at 23:51
@Veskah The twowhile
loops could probably also be reduced to the body of a single function which accepts parameters; and could substitute conditional operators (ternary) for theif..else
statements; among other portions of the code that could more than likely be adjusted for golf; i.e.g., removinglet
statements.
– guest271314
Nov 23 at 0:00
@Veskah 601 bytes without substituting ternary forif..else
– guest271314
Nov 23 at 0:06
1
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)
– Veskah
Nov 23 at 0:11
@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 givenn
?". testing if the algorithm consistently returned expected result forn^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.
– guest271314
Nov 23 at 0:22
1
1
637 bytes by pulling z.join into a variable, and
k++
– Veskah
Nov 22 at 23:51
637 bytes by pulling z.join into a variable, and
k++
– Veskah
Nov 22 at 23:51
@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.– guest271314
Nov 23 at 0:00
@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.– guest271314
Nov 23 at 0:00
@Veskah 601 bytes without substituting ternary for
if..else
– guest271314
Nov 23 at 0:06
@Veskah 601 bytes without substituting ternary for
if..else
– guest271314
Nov 23 at 0:06
1
1
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)
– Veskah
Nov 23 at 0:11
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)
– Veskah
Nov 23 at 0:11
@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.– guest271314
Nov 23 at 0:22
@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.– guest271314
Nov 23 at 0:22
|
show 1 more comment
up vote
0
down vote
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
add a comment |
up vote
0
down vote
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
add a comment |
up vote
0
down vote
up vote
0
down vote
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
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
answered Nov 20 at 18:48
Kamil Drakari
2,931416
2,931416
add a comment |
add a comment |
up vote
0
down vote
Ruby, 46 bytes
->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}
Try it online!
add a comment |
up vote
0
down vote
Ruby, 46 bytes
->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}
Try it online!
add a comment |
up vote
0
down vote
up vote
0
down vote
Ruby, 46 bytes
->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}
Try it online!
Ruby, 46 bytes
->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}
Try it online!
answered Nov 21 at 9:13
G B
7,6561328
7,6561328
add a comment |
add a comment |
up vote
0
down vote
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.
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.
– LambdaBeta
Nov 20 at 22:43
Suggestp(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++;}
– ceilingcat
Nov 20 at 23:30
@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)
– LambdaBeta
Nov 21 at 15:46
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).
– Zacharý
Nov 21 at 17:47
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.
– LambdaBeta
Nov 21 at 18:30
add a comment |
up vote
0
down vote
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.
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.
– LambdaBeta
Nov 20 at 22:43
Suggestp(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++;}
– ceilingcat
Nov 20 at 23:30
@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)
– LambdaBeta
Nov 21 at 15:46
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).
– Zacharý
Nov 21 at 17:47
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.
– LambdaBeta
Nov 21 at 18:30
add a comment |
up vote
0
down vote
up vote
0
down vote
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.
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.
edited Nov 21 at 15:44
answered Nov 20 at 22:36
LambdaBeta
2,099418
2,099418
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.
– LambdaBeta
Nov 20 at 22:43
Suggestp(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++;}
– ceilingcat
Nov 20 at 23:30
@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)
– LambdaBeta
Nov 21 at 15:46
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).
– Zacharý
Nov 21 at 17:47
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.
– LambdaBeta
Nov 21 at 18:30
add a comment |
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.
– LambdaBeta
Nov 20 at 22:43
Suggestp(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++;}
– ceilingcat
Nov 20 at 23:30
@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)
– LambdaBeta
Nov 21 at 15:46
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).
– Zacharý
Nov 21 at 17:47
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.
– LambdaBeta
Nov 21 at 18:30
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.
– LambdaBeta
Nov 20 at 22:43
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.
– LambdaBeta
Nov 20 at 22:43
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++;}
– ceilingcat
Nov 20 at 23:30
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++;}
– ceilingcat
Nov 20 at 23:30
@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)
– LambdaBeta
Nov 21 at 15:46
@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)
– LambdaBeta
Nov 21 at 15:46
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).
– Zacharý
Nov 21 at 17:47
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).
– Zacharý
Nov 21 at 17:47
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.
– LambdaBeta
Nov 21 at 18:30
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.
– LambdaBeta
Nov 21 at 18:30
add a comment |
up vote
0
down vote
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 oe=e rem n^2)(genRandInt(?0)))))
Try it online!
add a comment |
up vote
0
down vote
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 oe=e rem n^2)(genRandInt(?0)))))
Try it online!
add a comment |
up vote
0
down vote
up vote
0
down vote
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 oe=e rem n^2)(genRandInt(?0)))))
Try it online!
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 oe=e rem n^2)(genRandInt(?0)))))
Try it online!
edited Nov 21 at 21:12
answered Nov 21 at 21:02
Οurous
6,29811032
6,29811032
add a comment |
add a comment |
up vote
0
down vote
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)
add a comment |
up vote
0
down vote
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)
add a comment |
up vote
0
down vote
up vote
0
down vote
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)
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)
answered Nov 21 at 22:01
ArBo
212
212
add a comment |
add a comment |
up vote
0
down vote
Kotlin, 32 bytes
{(1..it*it).shuffled().take(it)}
Try it online!
1
The sum needs to be n^2
– 12Me21
Nov 24 at 14:12
add a comment |
up vote
0
down vote
Kotlin, 32 bytes
{(1..it*it).shuffled().take(it)}
Try it online!
1
The sum needs to be n^2
– 12Me21
Nov 24 at 14:12
add a comment |
up vote
0
down vote
up vote
0
down vote
Kotlin, 32 bytes
{(1..it*it).shuffled().take(it)}
Try it online!
Kotlin, 32 bytes
{(1..it*it).shuffled().take(it)}
Try it online!
answered Nov 24 at 6:52
snail_
1,517415
1,517415
1
The sum needs to be n^2
– 12Me21
Nov 24 at 14:12
add a comment |
1
The sum needs to be n^2
– 12Me21
Nov 24 at 14:12
1
1
The sum needs to be n^2
– 12Me21
Nov 24 at 14:12
The sum needs to be n^2
– 12Me21
Nov 24 at 14:12
add a comment |
up vote
0
down vote
Mathematica 40 bytes
RandomChoice[IntegerPartitions[n^2, {n}]]
1
First of all it is n^2, not 2^n. Secondly, your program must be a function and also a golfed one. Try thisRandomChoice@IntegerPartitions[#^2,{#}]&
– J42161217
Nov 25 at 11:04
1
Also the result must be (unordered, unique) but this function fails in both
– J42161217
Nov 25 at 11:21
add a comment |
up vote
0
down vote
Mathematica 40 bytes
RandomChoice[IntegerPartitions[n^2, {n}]]
1
First of all it is n^2, not 2^n. Secondly, your program must be a function and also a golfed one. Try thisRandomChoice@IntegerPartitions[#^2,{#}]&
– J42161217
Nov 25 at 11:04
1
Also the result must be (unordered, unique) but this function fails in both
– J42161217
Nov 25 at 11:21
add a comment |
up vote
0
down vote
up vote
0
down vote
Mathematica 40 bytes
RandomChoice[IntegerPartitions[n^2, {n}]]
Mathematica 40 bytes
RandomChoice[IntegerPartitions[n^2, {n}]]
edited Nov 25 at 20:01
answered Nov 22 at 8:03
David G. Stork
1837
1837
1
First of all it is n^2, not 2^n. Secondly, your program must be a function and also a golfed one. Try thisRandomChoice@IntegerPartitions[#^2,{#}]&
– J42161217
Nov 25 at 11:04
1
Also the result must be (unordered, unique) but this function fails in both
– J42161217
Nov 25 at 11:21
add a comment |
1
First of all it is n^2, not 2^n. Secondly, your program must be a function and also a golfed one. Try thisRandomChoice@IntegerPartitions[#^2,{#}]&
– J42161217
Nov 25 at 11:04
1
Also the result must be (unordered, unique) but this function fails in both
– J42161217
Nov 25 at 11:21
1
1
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,{#}]&
– J42161217
Nov 25 at 11:04
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,{#}]&
– J42161217
Nov 25 at 11:04
1
1
Also the result must be (unordered, unique) but this function fails in both
– J42161217
Nov 25 at 11:21
Also the result must be (unordered, unique) but this function fails in both
– J42161217
Nov 25 at 11:21
add a comment |
up vote
0
down vote
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!
This is code golf.. 49 bytes(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
– J42161217
Nov 25 at 11:38
add a comment |
up vote
0
down vote
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!
This is code golf.. 49 bytes(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
– J42161217
Nov 25 at 11:38
add a comment |
up vote
0
down vote
up vote
0
down vote
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!
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!
edited Nov 26 at 0:21
answered Nov 25 at 6:04
Bubbler
6,204759
6,204759
This is code golf.. 49 bytes(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
– J42161217
Nov 25 at 11:38
add a comment |
This is code golf.. 49 bytes(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
– J42161217
Nov 25 at 11:38
This is code golf.. 49 bytes
(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
– J42161217
Nov 25 at 11:38
This is code golf.. 49 bytes
(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
– J42161217
Nov 25 at 11:38
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f176284%2farbitrary-randomness%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
related, but quite different
– Giuseppe
Nov 20 at 14:49
1
(p/s: If you have a fast algorithm but takes more bytes, consider waiting until the speed edition (currently in sandbox) to post it.)
– user202729
Nov 20 at 15:04
1
@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.
– user202729
Nov 20 at 15:08
2
The number of sets is OEIS A107379.
– nwellnhof
Nov 20 at 23:16
1
It's both. See the comment "Also the number of partitions of n^2 into n distinct parts."
– nwellnhof
Nov 21 at 3:31