Dado un entero n, calcule un conjunto de nenteros únicos aleatorios en el rango 1..n^2(inclusive) de modo que la suma del conjunto sea igual an^2

Aleatorio, en este caso, significa uniformemente aleatorio entre salidas válidas. Cada salida válida para un determinado ndebe tener una posibilidad uniforme de ser generada.

Por ejemplo, n=3deben tener la oportunidad de dar salida a un tercio cada uno 6, 1, 2, 3, 5, 1o 4, 3, 2. Como se trata de un conjunto, el orden es irrelevante, 4, 3, 2es idéntico a3, 2, 4

Puntuación

El ganador es el programa que puede calcular el más alto nen menos de 60 segundos.
Nota: para evitar una posible codificación parcial, todas las entradas deben tener menos de 4000 bytes

Pruebas

Todo el código se ejecutará en mi máquina local con Windows 10 (Razer Blade 15, 16GB RAM, Intel i7-8750H 6 núcleos, 4.1GHz, GTX 1060 en caso de que desee abusar de la GPU), así que proporcione instrucciones detalladas para ejecutar su código en mi maquina
A petición, las entradas se pueden ejecutar a través de Debian en WSL o en una máquina virtual Xubuntu (ambas en la misma máquina que la anterior)

Las presentaciones se realizarán 50 veces seguidas, el puntaje final será un promedio de los 50 resultados.

Óxido , n ≈ 1400

Como correr

Construye con cargo build --releasey corre con target/release/arbitrary-randomness n.

Este programa se ejecuta más rápido con mucha memoria (siempre y cuando no se intercambie, por supuesto). Puede ajustar su uso de memoria editando la MAX_BYTESconstante, actualmente establecida en 8 GiB.

Cómo funciona

El conjunto se construye mediante una secuencia de decisiones binarias (cada número está dentro o fuera del conjunto), cada una de cuyas probabilidades se calcula combinatoriamente contando el número de conjuntos posibles que se pueden construir después de cada elección mediante programación dinámica.

El uso de memoria para n grande se reduce mediante el uso de una versión de esta estrategia de partición binomial .

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

Pruébalo en línea!

(Nota: la versión TIO tiene algunas modificaciones. Primero, el límite de memoria se reduce a 1 GiB. Segundo, dado que TIO no le permite escribir ay Cargo.tomldepender de cajas externas como rand, en su lugar, ingresé drand48de la biblioteca C usando el FFI. No me molesté en sembrarlo, por lo que la versión TIO producirá el mismo resultado en cada ejecución. No use la versión TIO para la evaluación comparativa oficial).

Java 7+, n = 50 en ~ 30 segundos en 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;
      }
    }
  }
}

La versión sin golf de mi respuesta para la versión de código de golf de este desafío por ahora, con solo un cambio menor: java.util.Random#nextInt(limit)se usa en lugar de (int)(Math.random()*limit)un número entero en el rango [0, n), ya que es aproximadamente el doble de rápido .

Pruébalo en línea.

Explicación:

Enfoque utilizado:

El código se divide en dos partes:

1. Genere una lista de la ncantidad de enteros aleatorios que suman n squared.
2. Luego verifica si todos los valores son únicos y ninguno es cero, y si alguno es falso, intentará el paso 1 nuevamente, enjuagando y repitiendo hasta que tengamos un resultado.

El paso 1 se realiza con los siguientes subpasos:

1) Genere una matriz de n-1cantidad de enteros aleatorios en el rango [0, n squared). Y agregue 0y n squareda esta lista. Esto se hace en O(n+1)rendimiento.
2) Luego ordenará la matriz con la función incorporada java.util.Arrays.sort(int[]). Esto se hace en O(n*log(n))rendimiento, como se indica en los documentos:

Ordena la matriz especificada de entradas en orden numérico ascendente. El algoritmo de clasificación es una selección rápida ajustada, adaptada de Jon L. Bentley y M. Douglas McIlroy "Ingeniería de una función de clasificación", Software-Practice and Experience, vol. 23 (11) P. 1249-1265 (noviembre de 1993). Este algoritmo ofrece un rendimiento n * log (n) en muchos conjuntos de datos que hacen que otros clasificaciones rápidas se degraden a un rendimiento cuadrático.

3) Calcular la diferencia entre cada par. Esta lista resultante de diferencias contendrá nenteros que suman n squared. Esto se hace en O(n)rendimiento.

Aquí un ejemplo:

// 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

Entonces, estos tres pasos anteriores son bastante buenos para el rendimiento, a diferencia del paso 2 y el ciclo alrededor de todo, que es una fuerza bruta básica. El paso 2 se divide en estos pasos secundarios:

1) La lista de diferencias ya está guardada en a java.util.Set. Verificará si el tamaño de este conjunto es igual a n. Si es así, significa que todos los valores aleatorios que generamos son únicos.
2) Y también verificará que no contiene ningún 0en el Conjunto, ya que el desafío solicita valores aleatorios en el rango [1, X], donde Xes n squaredmenos la suma de [1, ..., n-1], como lo indica @Skidsdev en el comentario a continuación.

Si alguna de las dos opciones anteriores (no todos los valores son únicos o hay un cero presente), generará una nueva matriz y se establecerá nuevamente restableciendo el paso 1. Esto continúa hasta que tengamos un resultado. Debido a esto, el tiempo puede variar bastante. Lo he visto terminar en 3 segundos una vez en TIO durante n=50, pero también en 55 segundos una vez n=50.

Prueba de uniformidad:

No estoy completamente seguro de cómo demostrar que esto es completamente honesto. El java.util.Random#nextIntuniforme es seguro, como se describe en los documentos:

Devuelve el siguiente valor pseudoaleatorio, distribuido uniformemente intde la secuencia de este generador de números aleatorios. El contrato general de nextIntes que un intvalor se genera y devuelve pseudoaleatoriamente. Los 2 ³²int valores posibles se producen con (aproximadamente) la misma probabilidad.

Por supuesto, las diferencias entre estos valores aleatorios (ordenados) no son uniformes, pero los conjuntos en su conjunto son uniformes. Nuevamente, no estoy seguro de cómo probar esto matemáticamente, pero aquí hay un script que colocará los 10,000conjuntos generados (para n=10) en un Mapa con un contador , donde la mayoría de los conjuntos son únicos; algunos repiten dos veces; y la ocurrencia repetida máxima generalmente está en el rango [4,8].

Instrucciones de instalación:

Dado que Java es un lenguaje bastante conocido con mucha información disponible sobre cómo crear y ejecutar código Java, lo mantendré breve.
Todas las herramientas utilizadas en mi código están disponibles en Java 7 (tal vez incluso en Java 5 o 6, pero usemos 7 por si acaso). Sin embargo, estoy bastante seguro de que Java 7 ya está archivado, por lo que sugeriría descargar Java 8 para ejecutar mi código.

Reflexiones sobre mejoras:

Me gustaría encontrar una mejora para la verificación de ceros y verificar que todos los valores son únicos. Podría comprobar 0antes, asegurándome de que el valor aleatorio que agreguemos a la matriz no esté ya en él, pero significaría un par de cosas: la matriz debería ser una ArrayListpara que podamos usar el método incorporado .contains; se debe agregar un ciclo while hasta que hayamos encontrado un valor aleatorio que aún no esté en la Lista. Dado que la comprobación de cero ahora se realiza con .contains(0)el Set (que solo se verifica una vez), lo más probable es que el rendimiento lo verifique en ese punto, en comparación con agregar el ciclo con .containsen la Lista, que se verificará al menos nveces , pero muy probablemente más.

En cuanto a la verificación de unicidad, solo tenemos nuestra ncantidad de enteros aleatorios que suman n squareddespués del paso 1 del programa, por lo que solo entonces podemos verificar si todos son únicos o no. Puede ser posible mantener una Lista ordenable en lugar de una matriz, y verificar las diferencias entre ellas, pero dudo seriamente que mejore el rendimiento que solo ponerlas en una Sety verificar si el tamaño de ese Conjunto es nuna vez.

Mathematica n = 11

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