11
\$\begingroup\$

Given integer n, calculate a set of n random unique integers in range 1..n^2 (inclusive) such that the sum of the set is equal to n^2

Random, in this case, means uniformly random between valid outputs. Each valid output for a given n must have a uniform chance of being generated.

For example, n=3 should have a 1/3 chance each of outputting 6, 1, 2, 3, 5, 1, or 4, 3, 2. As this is a set, order is irrelevant, 4, 3, 2 is identical to 3, 2, 4

Scoring

The winner is the program that can compute the highest n in under 60 seconds.
Note: To prevent possible partial hardcoding, all entries must be under 4000 bytes

Testing

All code will be run on my local Windows 10 machine (Razer Blade 15, 16GB RAM, Intel i7-8750H 6 cores, 4.1GHz, GTX 1060 in case you want to abuse the GPU) so please provide detailed instructions to run your code on my machine.
At request, entries can be run either via Debian on WSL, or on a Xubuntu Virtual Machine (both on the same machine as above)

Submissions will be run 50 times in succession, final score will be an average of all 50 results.

\$\endgroup\$
8
  • \$\begingroup\$ Related \$\endgroup\$
    – Mayube
    Nov 20, 2018 at 18:23
  • \$\begingroup\$ Is hardcoding a bit allowed, if it’s under 4000 bytes? \$\endgroup\$
    – Quintec
    Nov 20, 2018 at 20:27
  • \$\begingroup\$ @Quintec No, hardcoding is a standard loophole, therefore forbidden by default. The tricky thing is hardcoding is also considered an unobservable criterion, so I can't officially say "No hardcoding" beyond what the loophole disallows. Hence the byte limit. In other words: Please don't hardcode \$\endgroup\$
    – Mayube
    Nov 20, 2018 at 20:44
  • 1
    \$\begingroup\$ Most submissions will use a rejection method and thus running time will be random and have large variability. That makes timing difficult \$\endgroup\$
    – Luis Mendo
    Nov 20, 2018 at 21:55
  • 2
    \$\begingroup\$ Oh, I forgot -- because some solutions may decide to use low-quality RNG to be fast, it might be necessary to provide a black box routine that takes n and produces a random number in (1..n), and forces all solutions to use it. \$\endgroup\$
    – DELETE_ME
    Nov 21, 2018 at 16:30

5 Answers 5

6
\$\begingroup\$

Rust, n ≈ 1400

How to run

Build with cargo build --release, and run with target/release/arbitrary-randomness n.

This program runs fastest with lots of memory (as long as it’s not swapping, of course). You can adjust its memory usage by editing the MAX_BYTES constant, currently set at 8 GiB.

How it works

The set is constructed by a sequence of binary decisions (each number is either inside or outside the set), each of whose probabilities are computed combinatorially by counting the number of possible sets constructible after each choice using dynamic programming.

Memory usage for large n is reduced by using a version of this binomial partitioning strategy.

Cargo.toml

[package]
name = "arbitrary-randomness"
version = "0.1.0"
authors = ["Anders Kaseorg <[email protected]>"]

[dependencies]
rand = "0.6"

src/main.rs

extern crate rand;

use rand::prelude::*;
use std::env;
use std::f64;
use std::mem;

const MAX_BYTES: usize = 8 << 30; // 8 gibibytes

fn ln_add_exp(a: f64, b: f64) -> f64 {
    if a > b {
        (b - a).exp().ln_1p() + a
    } else {
        (a - b).exp().ln_1p() + b
    }
}

fn split(steps: usize, memory: usize) -> usize {
    if steps == 1 {
        return 0;
    }
    let mut u0 = 0;
    let mut n0 = f64::INFINITY;
    let mut u1 = steps;
    let mut n1 = -f64::INFINITY;
    while u1 - u0 > 1 {
        let u = (u0 + u1) / 2;
        let k = (memory * steps) as f64 / u as f64;
        let n = (0..memory)
            .map(|i| (k - i as f64) / (i as f64 + 1.))
            .product();
        if n > steps as f64 {
            u0 = u;
            n0 = n;
        } else {
            u1 = u;
            n1 = n;
        }
    }
    if n0 - (steps as f64) <= steps as f64 - n1 {
        u0
    } else {
        u1
    }
}

fn gen(n: usize, rng: &mut impl Rng) -> Vec<usize> {
    let s = n * n.wrapping_sub(1) / 2;
    let width = n.min(MAX_BYTES / ((s + 1) * mem::size_of::<f64>()));
    let ix = |m: usize, k: usize| m + k * (s + 1);
    let mut ln_count = vec![-f64::INFINITY; ix(0, width)];
    let mut checkpoints = Vec::with_capacity(width);
    let mut a = Vec::with_capacity(n);
    let mut m = s;
    let mut x = 1;

    for k in (1..=n).rev() {
        let i = loop {
            let i = checkpoints.len();
            let k0 = *checkpoints.last().unwrap_or(&0);
            if k0 == k {
                checkpoints.pop();
                break i - 1;
            }
            if i == 0 {
                ln_count[ix(0, i)] = 0.;
                for m in 1..=s {
                    ln_count[ix(m, i)] = -f64::INFINITY;
                }
            } else {
                for m in 0..=s {
                    ln_count[ix(m, i)] = ln_count[ix(m, i - 1)];
                }
            }
            let k1 = k - split(k - k0, width - 1 - i);
            for step in k0 + 1..=k1 {
                for m in step..=s {
                    ln_count[ix(m, i)] = ln_add_exp(ln_count[ix(m - step, i)], ln_count[ix(m, i)]);
                }
            }
            if k1 == k {
                break i;
            }
            checkpoints.push(k1);
        };

        while m >= k && rng.gen_bool((ln_count[ix(m - k, i)] - ln_count[ix(m, i)]).exp()) {
            m -= k;
            x += 1;
        }
        a.push(x);
        x += 1;
    }
    a
}

fn main() {
    if let [_, n] = &env::args().collect::<Vec<_>>()[..] {
        let n = n.parse().unwrap();
        let mut rng = StdRng::from_entropy();
        println!("{:?}", gen(n, &mut rng));
    } else {
        panic!("expected one argument");
    }
}

Try it online!

(Note: the TIO version has a few modifications. First, the memory limit is reduced to 1 GiB. Second, since TIO doesn’t let you write a Cargo.toml and depend on external crates like rand, I instead pulled in drand48 from the C library using the FFI. I didn’t bother to seed it, so the TIO version will produce the same result on every run. Don’t use the TIO version for official benchmarking.)

\$\endgroup\$
2
  • \$\begingroup\$ Because floating point format is finite, it's possible to optimize ln_add_exp by checking if the absolute difference is larger than ~15 or so, which may be faster if there are a lot of such addition. \$\endgroup\$
    – DELETE_ME
    Nov 21, 2018 at 16:46
  • \$\begingroup\$ @user202729 Nope, nearly all ln_add_exp calls involve comparable inputs. \$\endgroup\$ Nov 21, 2018 at 21:29
3
\$\begingroup\$

Java 7+, n=50 in ~30 sec on TIO

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.Random;
class Main{
  public static void main(String[] a){

    int n=50;

    Random randomGenerator = new Random();
    int i = n+1;
    int squaredN = n*n;
    int[]randomIntegers = new int[i];
    randomIntegers[n] = squaredN;
    while(true){
      for(i=n; i-->1; ){
        randomIntegers[i] = randomGenerator.nextInt(squaredN);
      }
      Set<Integer> result = new HashSet<>();
      Arrays.sort(randomIntegers);
      for(i=n; i-->0; ){
        result.add(randomIntegers[i+1] - randomIntegers[i]);
      }
      if(!result.contains(0) && result.size()==n){
        System.out.println(result);
        return;
      }
    }
  }
}

Ungolfed version of my answer for the code-golf version of this challenge for now, with only one minor change: java.util.Random#nextInt(limit) is used instead of (int)(Math.random()*limit) for an integer in the range [0, n), since it's about twice as fast.

Try it online.

Explanation:

Approach used:

The code is split into two parts:

  1. Generate a list of n amount of random integers that sum to n squared.
  2. Then it checks if all values are unique and none are zero, and if either is falsey, it will try step 1 again, rinsing and repeating until we have a result.

Step 1 is done with the following sub-steps:

1) Generate an array of n-1 amount of random integers in the range [0, n squared). And add 0 and n squared to this list. This is done in O(n+1) performance.
2) Then it will sort the array with the builtin java.util.Arrays.sort(int[]), This is done in O(n*log(n)) performance, as is stated in the docs:

Sorts the specified array of ints into ascending numerical order. The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

3) Calculate the difference between each pair. This resulting list of differences will contain n integers that sum to n squared. This is done in O(n) performance.

Here an example:

// n = 4, nSquared = 16

// n-1 amount of random integers in the range [0, nSquared):
[11, 2, 5]

// Add 0 and nSquared to it, and sort:
[0, 2, 5, 11, 16]

// Calculate differences:
[2, 3, 6, 5]

// The sum of these differences will always be equal to nSquared
sum([2, 3, 6, 5]) = 16

So these three steps above are pretty good for performance, unlike step 2 and the loop around the whole thing, which is a basic brute-force. Step 2 is split in these sub-steps:

1) The differences list is already saved in a java.util.Set. It will check if the size of this Set is equal to n. If it is, it means all random values we generated are unique.
2) And it will also check that it contains no 0 in the Set, since the challenge asks for random values in the range [1, X], where X is n squared minus the sum of [1, ..., n-1], as stated by @Skidsdev in the comment below.

If either of the two options above (not all values are unique, or a zero is present), it will generate a new array and Set again by resetting to step 1. This continues until we have a result. Because of this, the time can vary quite a bit. I've seen it finish in 3 seconds once on TIO for n=50, but also in 55 seconds once for n=50.

Prove of uniformity:

I'm not entirely sure how to prove this to be completely honest. The java.util.Random#nextInt is uniform for sure, as is described in the docs:

Returns the next pseudorandom, uniformly distributed int value from this random number generator's sequence. The general contract of nextInt is that one int value is pseudorandomly generated and returned. All 232 possible int values are produced with (approximately) equal probability.

The differences between these (sorted) random values themselves are of course not uniform, but the sets as a whole are uniform. Again, I'm not sure how to prove this mathematically, but here is a script that will put 10,000 generated sets (for n=10) in a Map with a counter, where most sets are unique; some repeated twice; and the maximum repeated occurrence is usually in the range [4,8].

Installation instructions:

Since Java is a pretty well-known language with plenty of information available on how to create and run Java code, I will keep this short.
All the tools used in my code are available in Java 7 (perhaps even already in Java 5 or 6, but let's use 7 just in case). I'm pretty sure Java 7 is already archived though, so I would suggest downloading Java 8 to run my code.

Thoughts regarding improvements:

I'd like to find an improvement for the check for zeros and check all values are unique. I could check for 0 before, by making sure the random value we add to the array isn't already in it, but it would mean a couple of things: the array should be an ArrayList so we can use the builtin method .contains; a while-loop should be added until we've found a random value that isn't in the List yet. Since checking for zero is now done with .contains(0) on the Set (which is only checked once), it's most likely better for performance to check it at that point, in comparison to adding the loop with .contains on the List, which will be checked at least n times, but most likely more.

As for the uniqueness check, we only have our n amount of random integers that sum to n squared after step 1 of the program, so only then we can check whether all are unique or not. It might be possible to keep a sortable List instead of array, and check the differences in between, but I seriously doubt it will improve the performance than just putting them in a Set and check if the size of that Set is n once.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ if it helps the speed, no number in the set can be greater than n^2 - sum(1..n-1) for example for n=5 the largest valid number is 5^2 - sum(1, 2, 3, 4) == 25 - 10 == 15 \$\endgroup\$
    – Mayube
    Nov 20, 2018 at 20:43
  • \$\begingroup\$ @Skidsdev Thanks, hadn't thought about that. Although with my current approach I can't utilize it, since I get the differences between random-pairs, instead of the random values directly. But it might be useful for other answers perhaps. \$\endgroup\$ Nov 20, 2018 at 22:33
  • 1
    \$\begingroup\$ The size of the resulting set can never be more than n, can it? In that case, you can add 0 to the set, and then check that the size is (now) more than n. This can only happen if the differences are all nonzero and distinct. \$\endgroup\$
    – Neil
    Nov 22, 2018 at 19:51
  • \$\begingroup\$ @Neil Oh, that's pretty smart, and I will definitely use that in my code-golf answer to golf a few bytes off. I'm not sure if it will improve the performance here, though. HashSet.contains is in most cases close to O(1), and in the worst case it's O(n) in Java 7, and O(log n) in Java 8+ (it has been improved after they've replaced chaining with collision detection). If I'm allowed to return the Set with the added 0 for the check, then it's indeed slightly better for performance, but if I have to call set.remove(0); inside the if, I'm pretty sure performance is somewhat the same. \$\endgroup\$ Nov 22, 2018 at 21:23
  • \$\begingroup\$ Oh, I forgot you need to return the set as well... never mind. \$\endgroup\$
    – Neil
    Nov 22, 2018 at 23:44
1
\$\begingroup\$

Mathematica n=11

(While[Tr@(a=RandomSample[Range[#^2-#(#-1)/2],#])!=#^2];a)&     
\$\endgroup\$
1
\$\begingroup\$

Scala, n=50 in ~45 sec on TIO

Port of @Kevin Cruijssen's Java answer in Scala.

Try it online!

import scala.util.Random
import scala.collection.mutable.HashSet

object Main {
  def main(args: Array[String]): Unit = {

    val n = 50
    val randomGenerator = new Random()
    val squaredN = n * n
    var randomIntegers = new Array[Int](n + 1)
    randomIntegers(n) = squaredN

    while(true) {
      for(i <- n-1 to 0 by -1) {
        randomIntegers(i) = randomGenerator.nextInt(squaredN)
      }
      val result = HashSet[Int]()
      scala.util.Sorting.quickSort(randomIntegers)
      for(i <- n-1 to 0 by -1) {
        result.add(randomIntegers(i+1) - randomIntegers(i))
      }
      if(!result.contains(0) && result.size == n) {
        println(result)
        return
      }
    }
  }
}
\$\endgroup\$
1
\$\begingroup\$

Python, n ≈ 4500

Runs in expected \$Θ(n^{5/2})\$ time.

import numpy as np

def gen(n):
    target = n**2
    k_bounds = [1 / ((n + 1) / 2 - target / n), 1 / ((n + 1) / 4 - target / n)]
    i = np.arange(n)
    while (k := (k_bounds[0] + k_bounds[1]) / 2) not in k_bounds:
        p = -np.expm1(k * (n - i))
        k_bounds[int(((n - i) / p).sum() > target)] = k

    rng = np.random.default_rng()
    while True:
        output = rng.geometric(p=p).cumsum()
        if output.sum() == target:
            return output

Attempt This Online!

How it works

After selecting a constant \$k < 0\$ (explained below), we draw \$n\$ positive integers \$a_0, a_1, …, a_{n-1}\$ independently from the geometric distributions of probabilities \$p_i = 1 - e^{k(n - i)}\$. We build a candidate set from the prefix sums of the \$a_i\$:

$$S = \{a_0, a_0 + a_1, …, a_0 + a_1 + … + a_{n-1}\}.$$

The probability of generating any particular \$S\$ can be computed as

$$\prod_i (1 - p_i)^{a_i} p_i = \prod_i e^{k(n - i)a_i} p_i = e^{k \sum_i (n - i)a_i} \prod_i p_i = e^{k \sum S} \prod_i p_i,$$

which is proportional to \$e^{k \sum S}\$. In particular, the probability of generating each \$S\$ that sums to \$n^2\$ is the same! We accept \$S\$ if it sums to \$n^2\$, otherwise reject it and repeat the draw.

Although the constant \$k\$ has no effect on correctness, it has a huge effect on the expected running time. We select \$k\$ using a binary search such that \$E[\sum S] = \sum_i \frac{n - i}{p_i}\$ is made equal to \$n^2\$, in order to optimize the probability of acceptance to \$Θ(n^{-3/2})\$.

\$\endgroup\$

Your Answer

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

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