Mixing
Arbitrary Randomness
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
edited Nov 21 '18 at 9:15
nwellnhof
6,49511125
asked Nov 20 '18 at 14:45
Skidsdev
6,3362974
|
show 14 more comments
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
edited Nov 21 '18 at 9:15
nwellnhof
6,49511125
asked Nov 20 '18 at 14:45
Skidsdev
6,3362974
2
related, but quite different
– Giuseppe
Nov 20 '18 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 '18 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 '18 at 15:08
2
The number of sets is OEIS A107379.
– nwellnhof
Nov 20 '18 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 '18 at 3:31
|
show 14 more comments
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
edited Nov 21 '18 at 9:15
nwellnhof
6,49511125
asked Nov 20 '18 at 14:45
Skidsdev
6,3362974
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 '18 at 9:15
nwellnhof
6,49511125
asked Nov 20 '18 at 14:45
Skidsdev
6,3362974
edited Nov 21 '18 at 9:15
nwellnhof
6,49511125
asked Nov 20 '18 at 14:45
Skidsdev
6,3362974
edited Nov 21 '18 at 9:15
nwellnhof
6,49511125
edited Nov 21 '18 at 9:15
nwellnhof
6,49511125
edited Nov 21 '18 at 9:15
nwellnhof
6,49511125
6,49511125
asked Nov 20 '18 at 14:45
Skidsdev
6,3362974
asked Nov 20 '18 at 14:45
Skidsdev
6,3362974
asked Nov 20 '18 at 14:45
Skidsdev
6,3362974
6,3362974
2
related, but quite different
– Giuseppe
Nov 20 '18 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 '18 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 '18 at 15:08
2
The number of sets is OEIS A107379.
– nwellnhof
Nov 20 '18 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 '18 at 3:31
|
show 14 more comments
2
related, but quite different
– Giuseppe
Nov 20 '18 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 '18 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 '18 at 15:08
2
The number of sets is OEIS A107379.
– nwellnhof
Nov 20 '18 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 '18 at 3:31
2
2
related, but quite different
– Giuseppe
Nov 20 '18 at 14:49
related, but quite different
– Giuseppe
Nov 20 '18 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 '18 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 '18 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 '18 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 '18 at 15:08
2
2
The number of sets is OEIS A107379.
– nwellnhof
Nov 20 '18 at 23:16
The number of sets is OEIS A107379.
– nwellnhof
Nov 20 '18 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 '18 at 3:31
It's both. See the comment "Also the number of partitions of n^2 into n distinct parts."
– nwellnhof
Nov 21 '18 at 3:31
|
show 14 more comments
24 Answers
24
active
oldest
votes
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 '18 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 '18 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 '18 at 15:32
@pipe codegolf.stackexchange.com/questions/172716/true-color-code/…
– guest271314
Nov 21 '18 at 17:04
add a comment |
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)
answered Nov 20 '18 at 14:55
Kevin Cruijssen
35.6k554186
add a comment |
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 '18 at 18:55
Jonathan Allan
50.7k534165
add a comment |
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.
answered Nov 20 '18 at 18:47
ngm
3,27924
@Giuseppe "fixed" :-)
– ngm
Nov 20 '18 at 18:57
very nice. usingpdirectly as an index instead of calculating it and re-using it should save some bytes.
– Giuseppe
Nov 20 '18 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 '18 at 19:00
1
@J.Doe to avoid the issue when calling something likesample(2,1)which happens withn=2. Sorepjust guarantees that this will never happen. There might be a better way but this was quick and I was mad atsample.
– ngm
Nov 20 '18 at 20:17
1
You can save a byte withx*!!1:2overrep(x,2)if your meta question gets a no.
– J.Doe
Nov 20 '18 at 20:35
|
show 4 more comments
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 '18 at 15:05
user202729
13.9k12551
add a comment |
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)
answered Nov 20 '18 at 16:20
Kevin Cruijssen
35.6k554186
1
n=25in 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 '18 at 16:59
Is it uniform? -
– user202729
Nov 20 '18 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 leading0and 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 '18 at 17:27
3
You never read from the differences arraydor am I missing something?
– nwellnhof
Nov 20 '18 at 21:31
1
I'm kind of happy with my 127 bytes solution :D
– Olivier Grégoire
Nov 21 '18 at 9:26
|
show 5 more comments
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
answered Nov 20 '18 at 20:21
Sean
3,44637
40 bytes
– Jo King
Nov 20 '18 at 21:59
add a comment |
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./*
answered Nov 20 '18 at 15:09
Sok
3,537722
add a comment |
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.
answered Nov 20 '18 at 18:29
Gigaflop
22117
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=1is[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 '18 at 18:32
1
range(1,n)->range(n)I believe should resolve the bug.
– Jonathan Allan
Nov 20 '18 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 '18 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 '18 at 19:38
1
You can have it all on one line. 111 bytes
– Jo King
Nov 20 '18 at 22:02
|
show 1 more comment
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 '18 at 10:56
Adám
28.8k269190
did you see my and H.PWiz's 18 bytes?
– ngn
Nov 25 '18 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 '18 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 '18 at 16:30
@ngn For you, no, but for me there is.
– Adám
Nov 25 '18 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 '18 at 18:24
|
show 2 more comments
APL (Dyalog Classic), 18 bytes
(≢?≢×≢)⍣(0=+.-∘≢)⍳
Try it online!
uses ⎕io←1
⍳ generates the numbers 1 2 ... n
(...)⍣(...) keep applying the function on the left until the function on the right returns true
≢ length, i.e. n
≢?≢×≢ choose randomly n distinct integers between 1 and n2
+.-∘≢ subtract the length from each number and sum
0= if the sum is 0, stop looping, otherwise try again
answered Nov 25 '18 at 18:32
ngn
6,94112559
add a comment |
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
answered Nov 20 '18 at 18:37
Giuseppe
16.6k31052
I wouldn't try this in R - random characters almost never produce a valid program.
– ngm
Nov 20 '18 at 18:48
@ngm hahaha I suppose an explanation is in order.
– Giuseppe
Nov 20 '18 at 18:48
add a comment |
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
answered Nov 20 '18 at 17:55
Shaggy
18.9k21666
According to a comment made by the OP, order of elements in the output is irrelevant soàshould be fine.
– Kamil Drakari
Nov 20 '18 at 18:52
Thanks, @KamilDrakari. Updated.
– Shaggy
Nov 20 '18 at 19:15
add a comment |
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.
answered Nov 21 '18 at 8:46
Olivier Grégoire
8,77711843
You can golf 3 bytes by changingif(r.size()==n&s==0)toif(r.size()+s==n).
– Kevin Cruijssen
Nov 22 '18 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 '18 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.nis a constant, but unfortunately bothsandr.size()are variables that can be both below or above0andnrespectively.
– Kevin Cruijssen
Nov 23 '18 at 11:53
add a comment |
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.
answered Nov 23 '18 at 0:14
Neil
79.4k744177
add a comment |
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.
answered Nov 22 '18 at 22:43
guest271314
317211
1
637 bytes by pulling z.join into a variable, andk++
– Veskah
Nov 22 '18 at 23:51
@Veskah The twowhileloops could probably also be reduced to the body of a single function which accepts parameters; and could substitute conditional operators (ternary) for theif..elsestatements; among other portions of the code that could more than likely be adjusted for golf; i.e.g., removingletstatements.
– guest271314
Nov 23 '18 at 0:00
@Veskah 601 bytes without substituting ternary forif..else
– guest271314
Nov 23 '18 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 '18 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^2output 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 '18 at 0:22
|
show 1 more comment
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 '18 at 18:48
Kamil Drakari
2,971416
add a comment |
Ruby, 46 bytes
->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}
Try it online!
answered Nov 21 '18 at 9:13
G B
7,6861328
add a comment |
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.
answered Nov 20 '18 at 22:36
LambdaBeta
2,109418
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 '18 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 '18 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 '18 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 '18 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 '18 at 18:30
add a comment |
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!
answered Nov 21 '18 at 21:02
Οurous
6,45311033
add a comment |
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 '18 at 22:01
ArBo
214
add a comment |
Kotlin, 32 bytes
{(1..it*it).shuffled().take(it)}
Try it online!
answered Nov 24 '18 at 6:52
snail_
1,557415
1
The sum needs to be n^2
– 12Me21
Nov 24 '18 at 14:12
add a comment |
Mathematica 40 bytes
RandomChoice[IntegerPartitions[n^2, {n}]]
answered Nov 22 '18 at 8:03
David G. Stork
20318
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 '18 at 11:04
1
Also the result must be (unordered, unique) but this function fails in both
– J42161217
Nov 25 '18 at 11:21
add a comment |
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!
answered Nov 25 '18 at 6:04
Bubbler
6,282759
This is code golf.. 49 bytes(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
– J42161217
Nov 25 '18 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',
autoActivateHeartbeat: false,
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
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 '18 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 '18 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 '18 at 15:32
@pipe codegolf.stackexchange.com/questions/172716/true-color-code/…
– guest271314
Nov 21 '18 at 17:04
add a comment |
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 '18 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 '18 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 '18 at 15:32
@pipe codegolf.stackexchange.com/questions/172716/true-color-code/…
– guest271314
Nov 21 '18 at 17:04
add a comment |
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 '18 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 '18 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 '18 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 '18 at 15:32
@pipe codegolf.stackexchange.com/questions/172716/true-color-code/…
– guest271314
Nov 21 '18 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 '18 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 '18 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 '18 at 15:32
@pipe codegolf.stackexchange.com/questions/172716/true-color-code/…
– guest271314
Nov 21 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 at 15:32
@pipe codegolf.stackexchange.com/questions/172716/true-color-code/…
– guest271314
Nov 21 '18 at 17:04
@pipe codegolf.stackexchange.com/questions/172716/true-color-code/…
– guest271314
Nov 21 '18 at 17:04
add a comment |
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)
answered Nov 20 '18 at 14:55
Kevin Cruijssen
35.6k554186
add a comment |
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)
answered Nov 20 '18 at 14:55
Kevin Cruijssen
35.6k554186
add a comment |
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)
answered Nov 20 '18 at 14:55
Kevin Cruijssen
35.6k554186
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)
answered Nov 20 '18 at 14:55
Kevin Cruijssen
35.6k554186
edited Nov 20 '18 at 15:08
answered Nov 20 '18 at 14:55
Kevin Cruijssen
35.6k554186
answered Nov 20 '18 at 14:55
Kevin Cruijssen
35.6k554186
answered Nov 20 '18 at 14:55
Kevin Cruijssen
35.6k554186
35.6k554186
add a comment |
add a comment |
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 '18 at 18:55
Jonathan Allan
50.7k534165
add a comment |
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 '18 at 18:55
Jonathan Allan
50.7k534165
add a comment |
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 '18 at 18:55
Jonathan Allan
50.7k534165
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 '18 at 18:55
Jonathan Allan
50.7k534165
answered Nov 20 '18 at 18:55
Jonathan Allan
50.7k534165
answered Nov 20 '18 at 18:55
Jonathan Allan
50.7k534165
answered Nov 20 '18 at 18:55
Jonathan Allan
50.7k534165
50.7k534165
add a comment |
add a comment |
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.
answered Nov 20 '18 at 18:47
ngm
3,27924
@Giuseppe "fixed" :-)
– ngm
Nov 20 '18 at 18:57
very nice. usingpdirectly as an index instead of calculating it and re-using it should save some bytes.
– Giuseppe
Nov 20 '18 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 '18 at 19:00
1
@J.Doe to avoid the issue when calling something likesample(2,1)which happens withn=2. Sorepjust guarantees that this will never happen. There might be a better way but this was quick and I was mad atsample.
– ngm
Nov 20 '18 at 20:17
1
You can save a byte withx*!!1:2overrep(x,2)if your meta question gets a no.
– J.Doe
Nov 20 '18 at 20:35
|
show 4 more comments
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.
answered Nov 20 '18 at 18:47
ngm
3,27924
@Giuseppe "fixed" :-)
– ngm
Nov 20 '18 at 18:57
very nice. usingpdirectly as an index instead of calculating it and re-using it should save some bytes.
– Giuseppe
Nov 20 '18 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 '18 at 19:00
1
@J.Doe to avoid the issue when calling something likesample(2,1)which happens withn=2. Sorepjust guarantees that this will never happen. There might be a better way but this was quick and I was mad atsample.
– ngm
Nov 20 '18 at 20:17
1
You can save a byte withx*!!1:2overrep(x,2)if your meta question gets a no.
– J.Doe
Nov 20 '18 at 20:35
|
show 4 more comments
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.
answered Nov 20 '18 at 18:47
ngm
3,27924
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.
answered Nov 20 '18 at 18:47
ngm
3,27924
edited Nov 21 '18 at 16:23
answered Nov 20 '18 at 18:47
ngm
3,27924
answered Nov 20 '18 at 18:47
ngm
3,27924
answered Nov 20 '18 at 18:47
ngm
3,27924
3,27924
@Giuseppe "fixed" :-)
– ngm
Nov 20 '18 at 18:57
very nice. usingpdirectly as an index instead of calculating it and re-using it should save some bytes.
– Giuseppe
Nov 20 '18 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 '18 at 19:00
1
@J.Doe to avoid the issue when calling something likesample(2,1)which happens withn=2. Sorepjust guarantees that this will never happen. There might be a better way but this was quick and I was mad atsample.
– ngm
Nov 20 '18 at 20:17
1
You can save a byte withx*!!1:2overrep(x,2)if your meta question gets a no.
– J.Doe
Nov 20 '18 at 20:35
|
show 4 more comments
@Giuseppe "fixed" :-)
– ngm
Nov 20 '18 at 18:57
very nice. usingpdirectly as an index instead of calculating it and re-using it should save some bytes.
– Giuseppe
Nov 20 '18 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 '18 at 19:00
1
@J.Doe to avoid the issue when calling something likesample(2,1)which happens withn=2. Sorepjust guarantees that this will never happen. There might be a better way but this was quick and I was mad atsample.
– ngm
Nov 20 '18 at 20:17
1
You can save a byte withx*!!1:2overrep(x,2)if your meta question gets a no.
– J.Doe
Nov 20 '18 at 20:35
@Giuseppe "fixed" :-)
– ngm
Nov 20 '18 at 18:57
@Giuseppe "fixed" :-)
– ngm
Nov 20 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 at 20:35
|
show 4 more comments
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 '18 at 15:05
user202729
13.9k12551
add a comment |
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 '18 at 15:05
user202729
13.9k12551
add a comment |
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 '18 at 15:05
user202729
13.9k12551
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 '18 at 15:05
user202729
13.9k12551
answered Nov 20 '18 at 15:05
user202729
13.9k12551
answered Nov 20 '18 at 15:05
user202729
13.9k12551
answered Nov 20 '18 at 15:05
user202729
13.9k12551
13.9k12551
add a comment |
add a comment |
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)
answered Nov 20 '18 at 16:20
Kevin Cruijssen
35.6k554186
1
n=25in 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 '18 at 16:59
Is it uniform? -
– user202729
Nov 20 '18 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 leading0and 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 '18 at 17:27
3
You never read from the differences arraydor am I missing something?
– nwellnhof
Nov 20 '18 at 21:31
1
I'm kind of happy with my 127 bytes solution :D
– Olivier Grégoire
Nov 21 '18 at 9:26
|
show 5 more comments
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)
answered Nov 20 '18 at 16:20
Kevin Cruijssen
35.6k554186
1
n=25in 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 '18 at 16:59
Is it uniform? -
– user202729
Nov 20 '18 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 leading0and 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 '18 at 17:27
3
You never read from the differences arraydor am I missing something?
– nwellnhof
Nov 20 '18 at 21:31
1
I'm kind of happy with my 127 bytes solution :D
– Olivier Grégoire
Nov 21 '18 at 9:26
|
show 5 more comments
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)
answered Nov 20 '18 at 16:20
Kevin Cruijssen
35.6k554186
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)
answered Nov 20 '18 at 16:20
Kevin Cruijssen
35.6k554186
edited Nov 20 '18 at 22:29
answered Nov 20 '18 at 16:20
Kevin Cruijssen
35.6k554186
answered Nov 20 '18 at 16:20
Kevin Cruijssen
35.6k554186
answered Nov 20 '18 at 16:20
Kevin Cruijssen
35.6k554186
35.6k554186
1
n=25in 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 '18 at 16:59
Is it uniform? -
– user202729
Nov 20 '18 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 leading0and 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 '18 at 17:27
3
You never read from the differences arraydor am I missing something?
– nwellnhof
Nov 20 '18 at 21:31
1
I'm kind of happy with my 127 bytes solution :D
– Olivier Grégoire
Nov 21 '18 at 9:26
|
show 5 more comments
1
n=25in 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 '18 at 16:59
Is it uniform? -
– user202729
Nov 20 '18 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 leading0and 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 '18 at 17:27
3
You never read from the differences arraydor am I missing something?
– nwellnhof
Nov 20 '18 at 21:31
1
I'm kind of happy with my 127 bytes solution :D
– Olivier Grégoire
Nov 21 '18 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 '18 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 '18 at 16:59
Is it uniform? -
– user202729
Nov 20 '18 at 17:13
Is it uniform? -
– user202729
Nov 20 '18 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 '18 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 '18 at 17:27
3
3
You never read from the differences array
d or am I missing something?– nwellnhof
Nov 20 '18 at 21:31
You never read from the differences array
d or am I missing something?– nwellnhof
Nov 20 '18 at 21:31
1
1
I'm kind of happy with my 127 bytes solution :D
– Olivier Grégoire
Nov 21 '18 at 9:26
I'm kind of happy with my 127 bytes solution :D
– Olivier Grégoire
Nov 21 '18 at 9:26
|
show 5 more comments
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
answered Nov 20 '18 at 20:21
Sean
3,44637
40 bytes
– Jo King
Nov 20 '18 at 21:59
add a comment |
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
answered Nov 20 '18 at 20:21
Sean
3,44637
40 bytes
– Jo King
Nov 20 '18 at 21:59
add a comment |
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
answered Nov 20 '18 at 20:21
Sean
3,44637
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
answered Nov 20 '18 at 20:21
Sean
3,44637
edited Nov 21 '18 at 23:48
answered Nov 20 '18 at 20:21
Sean
3,44637
answered Nov 20 '18 at 20:21
Sean
3,44637
answered Nov 20 '18 at 20:21
Sean
3,44637
3,44637
40 bytes
– Jo King
Nov 20 '18 at 21:59
add a comment |
40 bytes
– Jo King
Nov 20 '18 at 21:59
40 bytes
– Jo King
Nov 20 '18 at 21:59
40 bytes
– Jo King
Nov 20 '18 at 21:59
add a comment |
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./*
answered Nov 20 '18 at 15:09
Sok
3,537722
add a comment |
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./*
answered Nov 20 '18 at 15:09
Sok
3,537722
add a comment |
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./*
answered Nov 20 '18 at 15:09
Sok
3,537722
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./*
answered Nov 20 '18 at 15:09
Sok
3,537722
edited Nov 20 '18 at 16:26
answered Nov 20 '18 at 15:09
Sok
3,537722
answered Nov 20 '18 at 15:09
Sok
3,537722
answered Nov 20 '18 at 15:09
Sok
3,537722
3,537722
add a comment |
add a comment |
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.
answered Nov 20 '18 at 18:29
Gigaflop
22117
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=1is[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 '18 at 18:32
1
range(1,n)->range(n)I believe should resolve the bug.
– Jonathan Allan
Nov 20 '18 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 '18 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 '18 at 19:38
1
You can have it all on one line. 111 bytes
– Jo King
Nov 20 '18 at 22:02
|
show 1 more comment
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.
answered Nov 20 '18 at 18:29
Gigaflop
22117
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=1is[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 '18 at 18:32
1
range(1,n)->range(n)I believe should resolve the bug.
– Jonathan Allan
Nov 20 '18 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 '18 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 '18 at 19:38
1
You can have it all on one line. 111 bytes
– Jo King
Nov 20 '18 at 22:02
|
show 1 more comment
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.
answered Nov 20 '18 at 18:29
Gigaflop
22117
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.
answered Nov 20 '18 at 18:29
Gigaflop
22117
edited Nov 20 '18 at 20:12
answered Nov 20 '18 at 18:29
Gigaflop
22117
answered Nov 20 '18 at 18:29
Gigaflop
22117
answered Nov 20 '18 at 18:29
Gigaflop
22117
22117
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=1is[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 '18 at 18:32
1
range(1,n)->range(n)I believe should resolve the bug.
– Jonathan Allan
Nov 20 '18 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 '18 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 '18 at 19:38
1
You can have it all on one line. 111 bytes
– Jo King
Nov 20 '18 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=1is[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 '18 at 18:32
1
range(1,n)->range(n)I believe should resolve the bug.
– Jonathan Allan
Nov 20 '18 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 '18 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 '18 at 19:38
1
You can have it all on one line. 111 bytes
– Jo King
Nov 20 '18 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 '18 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 '18 at 18:32
1
1
range(1,n) -> range(n) I believe should resolve the bug.– Jonathan Allan
Nov 20 '18 at 18:34
range(1,n) -> range(n) I believe should resolve the bug.– Jonathan Allan
Nov 20 '18 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 '18 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 '18 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 '18 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 '18 at 19:38
1
1
You can have it all on one line. 111 bytes
– Jo King
Nov 20 '18 at 22:02
You can have it all on one line. 111 bytes
– Jo King
Nov 20 '18 at 22:02
|
show 1 more comment
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 '18 at 10:56
Adám
28.8k269190
did you see my and H.PWiz's 18 bytes?
– ngn
Nov 25 '18 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 '18 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 '18 at 16:30
@ngn For you, no, but for me there is.
– Adám
Nov 25 '18 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 '18 at 18:24
|
show 2 more comments
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 '18 at 10:56
Adám
28.8k269190
did you see my and H.PWiz's 18 bytes?
– ngn
Nov 25 '18 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 '18 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 '18 at 16:30
@ngn For you, no, but for me there is.
– Adám
Nov 25 '18 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 '18 at 18:24
|
show 2 more comments
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 '18 at 10:56
Adám
28.8k269190
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 '18 at 10:56
Adám
28.8k269190
answered Nov 25 '18 at 10:56
Adám
28.8k269190
answered Nov 25 '18 at 10:56
Adám
28.8k269190
answered Nov 25 '18 at 10:56
Adám
28.8k269190
28.8k269190
did you see my and H.PWiz's 18 bytes?
– ngn
Nov 25 '18 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 '18 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 '18 at 16:30
@ngn For you, no, but for me there is.
– Adám
Nov 25 '18 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 '18 at 18:24
|
show 2 more comments
did you see my and H.PWiz's 18 bytes?
– ngn
Nov 25 '18 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 '18 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 '18 at 16:30
@ngn For you, no, but for me there is.
– Adám
Nov 25 '18 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 '18 at 18:24
did you see my and H.PWiz's 18 bytes?
– ngn
Nov 25 '18 at 16:21
did you see my and H.PWiz's 18 bytes?
– ngn
Nov 25 '18 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 '18 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 '18 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 '18 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 '18 at 16:30
@ngn For you, no, but for me there is.
– Adám
Nov 25 '18 at 16:36
@ngn For you, no, but for me there is.
– Adám
Nov 25 '18 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 '18 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 '18 at 18:24
|
show 2 more comments
APL (Dyalog Classic), 18 bytes
(≢?≢×≢)⍣(0=+.-∘≢)⍳
Try it online!
uses ⎕io←1
⍳ generates the numbers 1 2 ... n
(...)⍣(...) keep applying the function on the left until the function on the right returns true
≢ length, i.e. n
≢?≢×≢ choose randomly n distinct integers between 1 and n2
+.-∘≢ subtract the length from each number and sum
0= if the sum is 0, stop looping, otherwise try again
answered Nov 25 '18 at 18:32
ngn
6,94112559
add a comment |
APL (Dyalog Classic), 18 bytes
(≢?≢×≢)⍣(0=+.-∘≢)⍳
Try it online!
uses ⎕io←1
⍳ generates the numbers 1 2 ... n
(...)⍣(...) keep applying the function on the left until the function on the right returns true
≢ length, i.e. n
≢?≢×≢ choose randomly n distinct integers between 1 and n2
+.-∘≢ subtract the length from each number and sum
0= if the sum is 0, stop looping, otherwise try again
answered Nov 25 '18 at 18:32
ngn
6,94112559
add a comment |
APL (Dyalog Classic), 18 bytes
(≢?≢×≢)⍣(0=+.-∘≢)⍳
Try it online!
uses ⎕io←1
⍳ generates the numbers 1 2 ... n
(...)⍣(...) keep applying the function on the left until the function on the right returns true
≢ length, i.e. n
≢?≢×≢ choose randomly n distinct integers between 1 and n2
+.-∘≢ subtract the length from each number and sum
0= if the sum is 0, stop looping, otherwise try again
answered Nov 25 '18 at 18:32
ngn
6,94112559
APL (Dyalog Classic), 18 bytes
(≢?≢×≢)⍣(0=+.-∘≢)⍳
Try it online!
uses ⎕io←1
⍳ generates the numbers 1 2 ... n
(...)⍣(...) keep applying the function on the left until the function on the right returns true
≢ length, i.e. n
≢?≢×≢ choose randomly n distinct integers between 1 and n2
+.-∘≢ subtract the length from each number and sum
0= if the sum is 0, stop looping, otherwise try again
answered Nov 25 '18 at 18:32
ngn
6,94112559
answered Nov 25 '18 at 18:32
ngn
6,94112559
answered Nov 25 '18 at 18:32
ngn
6,94112559
answered Nov 25 '18 at 18:32
ngn
6,94112559
6,94112559
add a comment |
add a comment |
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
answered Nov 20 '18 at 18:37
Giuseppe
16.6k31052
I wouldn't try this in R - random characters almost never produce a valid program.
– ngm
Nov 20 '18 at 18:48
@ngm hahaha I suppose an explanation is in order.
– Giuseppe
Nov 20 '18 at 18:48
add a comment |
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
answered Nov 20 '18 at 18:37
Giuseppe
16.6k31052
I wouldn't try this in R - random characters almost never produce a valid program.
– ngm
Nov 20 '18 at 18:48
@ngm hahaha I suppose an explanation is in order.
– Giuseppe
Nov 20 '18 at 18:48
add a comment |
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
answered Nov 20 '18 at 18:37
Giuseppe
16.6k31052
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
answered Nov 20 '18 at 18:37
Giuseppe
16.6k31052
edited Nov 20 '18 at 19:09
answered Nov 20 '18 at 18:37
Giuseppe
16.6k31052
answered Nov 20 '18 at 18:37
Giuseppe
16.6k31052
answered Nov 20 '18 at 18:37
Giuseppe
16.6k31052
16.6k31052
I wouldn't try this in R - random characters almost never produce a valid program.
– ngm
Nov 20 '18 at 18:48
@ngm hahaha I suppose an explanation is in order.
– Giuseppe
Nov 20 '18 at 18:48
add a comment |
I wouldn't try this in R - random characters almost never produce a valid program.
– ngm
Nov 20 '18 at 18:48
@ngm hahaha I suppose an explanation is in order.
– Giuseppe
Nov 20 '18 at 18:48
I wouldn't try this in R - random characters almost never produce a valid program.
– ngm
Nov 20 '18 at 18:48
I wouldn't try this in R - random characters almost never produce a valid program.
– ngm
Nov 20 '18 at 18:48
@ngm hahaha I suppose an explanation is in order.
– Giuseppe
Nov 20 '18 at 18:48
@ngm hahaha I suppose an explanation is in order.
– Giuseppe
Nov 20 '18 at 18:48
add a comment |
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
answered Nov 20 '18 at 17:55
Shaggy
18.9k21666
According to a comment made by the OP, order of elements in the output is irrelevant soàshould be fine.
– Kamil Drakari
Nov 20 '18 at 18:52
Thanks, @KamilDrakari. Updated.
– Shaggy
Nov 20 '18 at 19:15
add a comment |
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
answered Nov 20 '18 at 17:55
Shaggy
18.9k21666
According to a comment made by the OP, order of elements in the output is irrelevant soàshould be fine.
– Kamil Drakari
Nov 20 '18 at 18:52
Thanks, @KamilDrakari. Updated.
– Shaggy
Nov 20 '18 at 19:15
add a comment |
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
answered Nov 20 '18 at 17:55
Shaggy
18.9k21666
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
answered Nov 20 '18 at 17:55
Shaggy
18.9k21666
edited Nov 20 '18 at 19:14
answered Nov 20 '18 at 17:55
Shaggy
18.9k21666
answered Nov 20 '18 at 17:55
Shaggy
18.9k21666
answered Nov 20 '18 at 17:55
Shaggy
18.9k21666
18.9k21666
According to a comment made by the OP, order of elements in the output is irrelevant soàshould be fine.
– Kamil Drakari
Nov 20 '18 at 18:52
Thanks, @KamilDrakari. Updated.
– Shaggy
Nov 20 '18 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 '18 at 18:52
Thanks, @KamilDrakari. Updated.
– Shaggy
Nov 20 '18 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 '18 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 '18 at 18:52
Thanks, @KamilDrakari. Updated.
– Shaggy
Nov 20 '18 at 19:15
Thanks, @KamilDrakari. Updated.
– Shaggy
Nov 20 '18 at 19:15
add a comment |
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.
answered Nov 21 '18 at 8:46
Olivier Grégoire
8,77711843
You can golf 3 bytes by changingif(r.size()==n&s==0)toif(r.size()+s==n).
– Kevin Cruijssen
Nov 22 '18 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 '18 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.nis a constant, but unfortunately bothsandr.size()are variables that can be both below or above0andnrespectively.
– Kevin Cruijssen
Nov 23 '18 at 11:53
add a comment |
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.
answered Nov 21 '18 at 8:46
Olivier Grégoire
8,77711843
You can golf 3 bytes by changingif(r.size()==n&s==0)toif(r.size()+s==n).
– Kevin Cruijssen
Nov 22 '18 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 '18 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.nis a constant, but unfortunately bothsandr.size()are variables that can be both below or above0andnrespectively.
– Kevin Cruijssen
Nov 23 '18 at 11:53
add a comment |
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.
answered Nov 21 '18 at 8:46
Olivier Grégoire
8,77711843
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.
answered Nov 21 '18 at 8:46
Olivier Grégoire
8,77711843
edited Nov 21 '18 at 9:30
answered Nov 21 '18 at 8:46
Olivier Grégoire
8,77711843
answered Nov 21 '18 at 8:46
Olivier Grégoire
8,77711843
answered Nov 21 '18 at 8:46
Olivier Grégoire
8,77711843
8,77711843
You can golf 3 bytes by changingif(r.size()==n&s==0)toif(r.size()+s==n).
– Kevin Cruijssen
Nov 22 '18 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 '18 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.nis a constant, but unfortunately bothsandr.size()are variables that can be both below or above0andnrespectively.
– Kevin Cruijssen
Nov 23 '18 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 '18 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 '18 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.nis a constant, but unfortunately bothsandr.size()are variables that can be both below or above0andnrespectively.
– Kevin Cruijssen
Nov 23 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 at 11:53
add a comment |
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.
answered Nov 23 '18 at 0:14
Neil
79.4k744177
add a comment |
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.
answered Nov 23 '18 at 0:14
Neil
79.4k744177
add a comment |
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.
answered Nov 23 '18 at 0:14
Neil
79.4k744177
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.
answered Nov 23 '18 at 0:14
Neil
79.4k744177
edited Nov 23 '18 at 1:16
answered Nov 23 '18 at 0:14
Neil
79.4k744177
answered Nov 23 '18 at 0:14
Neil
79.4k744177
answered Nov 23 '18 at 0:14
Neil
79.4k744177
79.4k744177
add a comment |
add a comment |
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.
answered Nov 22 '18 at 22:43
guest271314
317211
1
637 bytes by pulling z.join into a variable, andk++
– Veskah
Nov 22 '18 at 23:51
@Veskah The twowhileloops could probably also be reduced to the body of a single function which accepts parameters; and could substitute conditional operators (ternary) for theif..elsestatements; among other portions of the code that could more than likely be adjusted for golf; i.e.g., removingletstatements.
– guest271314
Nov 23 '18 at 0:00
@Veskah 601 bytes without substituting ternary forif..else
– guest271314
Nov 23 '18 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 '18 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^2output 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 '18 at 0:22
|
show 1 more comment
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.
answered Nov 22 '18 at 22:43
guest271314
317211
1
637 bytes by pulling z.join into a variable, andk++
– Veskah
Nov 22 '18 at 23:51
@Veskah The twowhileloops could probably also be reduced to the body of a single function which accepts parameters; and could substitute conditional operators (ternary) for theif..elsestatements; among other portions of the code that could more than likely be adjusted for golf; i.e.g., removingletstatements.
– guest271314
Nov 23 '18 at 0:00
@Veskah 601 bytes without substituting ternary forif..else
– guest271314
Nov 23 '18 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 '18 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^2output 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 '18 at 0:22
|
show 1 more comment
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.
answered Nov 22 '18 at 22:43
guest271314
317211
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.
answered Nov 22 '18 at 22:43
guest271314
317211
edited Nov 26 '18 at 10:40
answered Nov 22 '18 at 22:43
guest271314
317211
answered Nov 22 '18 at 22:43
guest271314
317211
answered Nov 22 '18 at 22:43
guest271314
317211
317211
1
637 bytes by pulling z.join into a variable, andk++
– Veskah
Nov 22 '18 at 23:51
@Veskah The twowhileloops could probably also be reduced to the body of a single function which accepts parameters; and could substitute conditional operators (ternary) for theif..elsestatements; among other portions of the code that could more than likely be adjusted for golf; i.e.g., removingletstatements.
– guest271314
Nov 23 '18 at 0:00
@Veskah 601 bytes without substituting ternary forif..else
– guest271314
Nov 23 '18 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 '18 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^2output 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 '18 at 0:22
|
show 1 more comment
1
637 bytes by pulling z.join into a variable, andk++
– Veskah
Nov 22 '18 at 23:51
@Veskah The twowhileloops could probably also be reduced to the body of a single function which accepts parameters; and could substitute conditional operators (ternary) for theif..elsestatements; among other portions of the code that could more than likely be adjusted for golf; i.e.g., removingletstatements.
– guest271314
Nov 23 '18 at 0:00
@Veskah 601 bytes without substituting ternary forif..else
– guest271314
Nov 23 '18 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 '18 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^2output 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 '18 at 0:22
1
1
637 bytes by pulling z.join into a variable, and
k++– Veskah
Nov 22 '18 at 23:51
637 bytes by pulling z.join into a variable, and
k++– Veskah
Nov 22 '18 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 '18 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 '18 at 0:00
@Veskah 601 bytes without substituting ternary for
if..else– guest271314
Nov 23 '18 at 0:06
@Veskah 601 bytes without substituting ternary for
if..else– guest271314
Nov 23 '18 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 '18 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 '18 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 '18 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 '18 at 0:22
|
show 1 more comment
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 '18 at 18:48
Kamil Drakari
2,971416
add a comment |
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 '18 at 18:48
Kamil Drakari
2,971416
add a comment |
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 '18 at 18:48
Kamil Drakari
2,971416
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 '18 at 18:48
Kamil Drakari
2,971416
answered Nov 20 '18 at 18:48
Kamil Drakari
2,971416
answered Nov 20 '18 at 18:48
Kamil Drakari
2,971416
answered Nov 20 '18 at 18:48
Kamil Drakari
2,971416
2,971416
add a comment |
add a comment |
Ruby, 46 bytes
->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}
Try it online!
answered Nov 21 '18 at 9:13
G B
7,6861328
add a comment |
Ruby, 46 bytes
->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}
Try it online!
answered Nov 21 '18 at 9:13
G B
7,6861328
add a comment |
Ruby, 46 bytes
->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}
Try it online!
answered Nov 21 '18 at 9:13
G B
7,6861328
Ruby, 46 bytes
->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}
Try it online!
answered Nov 21 '18 at 9:13
G B
7,6861328
answered Nov 21 '18 at 9:13
G B
7,6861328
answered Nov 21 '18 at 9:13
G B
7,6861328
answered Nov 21 '18 at 9:13
G B
7,6861328
7,6861328
add a comment |
add a comment |
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.
answered Nov 20 '18 at 22:36
LambdaBeta
2,109418
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 '18 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 '18 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 '18 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 '18 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 '18 at 18:30
add a comment |
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.
answered Nov 20 '18 at 22:36
LambdaBeta
2,109418
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 '18 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 '18 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 '18 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 '18 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 '18 at 18:30
add a comment |
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.
answered Nov 20 '18 at 22:36
LambdaBeta
2,109418
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.
answered Nov 20 '18 at 22:36
LambdaBeta
2,109418
edited Nov 21 '18 at 15:44
answered Nov 20 '18 at 22:36
LambdaBeta
2,109418
answered Nov 20 '18 at 22:36
LambdaBeta
2,109418
answered Nov 20 '18 at 22:36
LambdaBeta
2,109418
2,109418
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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 at 18:30
add a comment |
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!
answered Nov 21 '18 at 21:02
Οurous
6,45311033
add a comment |
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!
answered Nov 21 '18 at 21:02
Οurous
6,45311033
add a comment |
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!
answered Nov 21 '18 at 21:02
Οurous
6,45311033
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!
answered Nov 21 '18 at 21:02
Οurous
6,45311033
edited Nov 21 '18 at 21:12
answered Nov 21 '18 at 21:02
Οurous
6,45311033
answered Nov 21 '18 at 21:02
Οurous
6,45311033
answered Nov 21 '18 at 21:02
Οurous
6,45311033
6,45311033
add a comment |
add a comment |
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 '18 at 22:01
ArBo
214
add a comment |
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 '18 at 22:01
ArBo
214
add a comment |
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 '18 at 22:01
ArBo
214
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 '18 at 22:01
ArBo
214
answered Nov 21 '18 at 22:01
ArBo
214
answered Nov 21 '18 at 22:01
ArBo
214
answered Nov 21 '18 at 22:01
ArBo
214
214
add a comment |
add a comment |
Kotlin, 32 bytes
{(1..it*it).shuffled().take(it)}
Try it online!
answered Nov 24 '18 at 6:52
snail_
1,557415
1
The sum needs to be n^2
– 12Me21
Nov 24 '18 at 14:12
add a comment |
Kotlin, 32 bytes
{(1..it*it).shuffled().take(it)}
Try it online!
answered Nov 24 '18 at 6:52
snail_
1,557415
1
The sum needs to be n^2
– 12Me21
Nov 24 '18 at 14:12
add a comment |
Kotlin, 32 bytes
{(1..it*it).shuffled().take(it)}
Try it online!
answered Nov 24 '18 at 6:52
snail_
1,557415
Kotlin, 32 bytes
{(1..it*it).shuffled().take(it)}
Try it online!
answered Nov 24 '18 at 6:52
snail_
1,557415
answered Nov 24 '18 at 6:52
snail_
1,557415
answered Nov 24 '18 at 6:52
snail_
1,557415
answered Nov 24 '18 at 6:52
snail_
1,557415
1,557415
1
The sum needs to be n^2
– 12Me21
Nov 24 '18 at 14:12
add a comment |
1
The sum needs to be n^2
– 12Me21
Nov 24 '18 at 14:12
1
1
The sum needs to be n^2
– 12Me21
Nov 24 '18 at 14:12
The sum needs to be n^2
– 12Me21
Nov 24 '18 at 14:12
add a comment |
Mathematica 40 bytes
RandomChoice[IntegerPartitions[n^2, {n}]]
answered Nov 22 '18 at 8:03
David G. Stork
20318
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 '18 at 11:04
1
Also the result must be (unordered, unique) but this function fails in both
– J42161217
Nov 25 '18 at 11:21
add a comment |
Mathematica 40 bytes
RandomChoice[IntegerPartitions[n^2, {n}]]
answered Nov 22 '18 at 8:03
David G. Stork
20318
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 '18 at 11:04
1
Also the result must be (unordered, unique) but this function fails in both
– J42161217
Nov 25 '18 at 11:21
add a comment |
Mathematica 40 bytes
RandomChoice[IntegerPartitions[n^2, {n}]]
answered Nov 22 '18 at 8:03
David G. Stork
20318
Mathematica 40 bytes
RandomChoice[IntegerPartitions[n^2, {n}]]
answered Nov 22 '18 at 8:03
David G. Stork
20318
edited Nov 25 '18 at 20:01
answered Nov 22 '18 at 8:03
David G. Stork
20318
answered Nov 22 '18 at 8:03
David G. Stork
20318
answered Nov 22 '18 at 8:03
David G. Stork
20318
20318
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 '18 at 11:04
1
Also the result must be (unordered, unique) but this function fails in both
– J42161217
Nov 25 '18 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 '18 at 11:04
1
Also the result must be (unordered, unique) but this function fails in both
– J42161217
Nov 25 '18 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 '18 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 '18 at 11:04
1
1
Also the result must be (unordered, unique) but this function fails in both
– J42161217
Nov 25 '18 at 11:21
Also the result must be (unordered, unique) but this function fails in both
– J42161217
Nov 25 '18 at 11:21
add a comment |
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!
answered Nov 25 '18 at 6:04
Bubbler
6,282759
This is code golf.. 49 bytes(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
– J42161217
Nov 25 '18 at 11:38
add a comment |
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!
answered Nov 25 '18 at 6:04
Bubbler
6,282759
This is code golf.. 49 bytes(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
– J42161217
Nov 25 '18 at 11:38
add a comment |
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!
answered Nov 25 '18 at 6:04
Bubbler
6,282759
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!
answered Nov 25 '18 at 6:04
Bubbler
6,282759
edited Nov 26 '18 at 0:21
answered Nov 25 '18 at 6:04
Bubbler
6,282759
answered Nov 25 '18 at 6:04
Bubbler
6,282759
answered Nov 25 '18 at 6:04
Bubbler
6,282759
6,282759
This is code golf.. 49 bytes(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
– J42161217
Nov 25 '18 at 11:38
add a comment |
This is code golf.. 49 bytes(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
– J42161217
Nov 25 '18 at 11:38
This is code golf.. 49 bytes
(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&– J42161217
Nov 25 '18 at 11:38
This is code golf.. 49 bytes
(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&– J42161217
Nov 25 '18 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 '18 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 '18 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 '18 at 15:08
2
The number of sets is OEIS A107379.
– nwellnhof
Nov 20 '18 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 '18 at 3:31