25
2
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
?
Sandbox – Skidsdev – 2018-11-20T14:45:55.843
2related, but quite different – Giuseppe – 2018-11-20T14:49:37.367
Are we also allowed to output all possible output-sets? – Kevin Cruijssen – 2018-11-20T15:01:20.353
@KevinCruijssen This defeats the "randomness" element of the challenge, so no. You must output a single random set. – Skidsdev – 2018-11-20T15:02:51.060
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 – 2018-11-20T15:04:29.137
Do the elements of the chosen set need to be in a random order as well? – Sok – 2018-11-20T15:07:35.407
@Sok a set is unordered, so the order of the elements is irrelevant to the challenge – Skidsdev – 2018-11-20T15:08:02.783
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 – 2018-11-20T15:08:26.967
@user202729 yeah when it comes to the really golfy languages like 05AB1E and Jelly, I can definitely see generating all possible sets and picking one at random being golfier than brute forcing as I did in C# – Skidsdev – 2018-11-20T15:09:39.043
2
The number of sets is OEIS A107379.
– nwellnhof – 2018-11-20T23:16:26.467@nwellnhof no it isn't, that's the number of ways to express n^2 as the sum of n odd numbers – Skidsdev – 2018-11-21T00:43:12.390
1It's both. See the comment "Also the number of partitions of n^2 into n distinct parts." – nwellnhof – 2018-11-21T03:31:24.623
@nwellnhof oh so it is, that's neat – Skidsdev – 2018-11-21T11:14:03.097
Could I return a set with the correct result, but an additional
0
in it that we ignore, as long as every single result my program returns consistently has that added0
? – Kevin Cruijssen – 2018-11-22T21:25:53.103@Skidsdev For clarity, "Bonus Task: Is there a formula to calculate the number of valid permutations for a given
n
?" necessarily renders generating or filtering "Arbitrary Randomness" moot, correct? Is that the intention of the bonus? – guest271314 – 2018-11-22T23:46:47.313@guest271314 the Bonus task is just a tongue in cheek extra question. It's not part of the challenge, no additional reward will be offered for solving the bonus task, I was just curious if there was a way to reliably calculate how many permutations there are for any
n
. IE a formula in which anyn
can be passed and it will return the number of valid permutations. Somebody else already answered the bonus task anyway, so my curiosity has been sated. – Skidsdev – 2018-11-25T16:05:41.607@KevinCruijssen No, because then the set would not contain exactly
n
elements – Skidsdev – 2018-11-25T16:05:58.587@Skidsdev What is the origin and meaning of the term "tongue in cheek"? Can you edit the question to include " the Bonus task is just a tongue in cheek extra question. It's not part of the challenge, no additional reward will be offered for solving the bonus task, I was just curious if there was a way to reliably calculate how many permutations there are for any
n
"? – guest271314 – 2018-11-25T21:03:18.023@guest271314 it would've taken you 5 seconds to google and find this. Also it's generally assumed on PPCG that unless a "bonus" lists a reward, it is not part of the main challenge, and as with all StackExchange sites, any answer must answer the main question/challenge of the post. If you want to answer the bonus task as well go ahead, but your posted answer must be an answer to the main challenge for it to be valid as an answer.
– Skidsdev – 2018-11-25T23:09:48.523