Dado inteiro n, calcule um conjunto de nnúmeros inteiros únicos aleatórios no intervalo 1..n^2(inclusive), de modo que a soma do conjunto seja igual an^2

Aleatório, nesse caso, significa uniformemente aleatório entre saídas válidas. Cada saída válida para um dado ndeve ter uma chance uniforme de ser gerada.

Por exemplo, n=3devem ter uma oportunidade 1/3 cada de saída 6, 1, 2, 3, 5, 1, ou 4, 3, 2. Como este é um conjunto, a ordem é irrelevante, 4, 3, 2é idêntica à3, 2, 4

Pontuação

O vencedor é o programa que pode calcular o mais alto nem menos de 60 segundos.
Nota: Para evitar uma possível codificação parcial parcial, todas as entradas devem ter menos de 4000 bytes

Teste

Todo o código será executado na minha máquina Windows 10 local (Razer Blade 15, 16 GB de RAM, Intel i7-8750H 6 núcleos, 4.1 GHz, GTX 1060 no caso de você querer abusar da GPU); por isso, forneça instruções detalhadas para executar seu código em minha maquina
A pedido, as entradas podem ser executadas via Debian na WSL ou em uma Máquina Virtual Xubuntu (ambas na mesma máquina que acima)

As inscrições serão realizadas 50 vezes consecutivas, a pontuação final será uma média de todos os 50 resultados.

Ferrugem , n ≈ 1400

Como executar

Construa com cargo build --releasee execute com target/release/arbitrary-randomness n.

Este programa roda mais rápido com muita memória (desde que não esteja trocando, é claro). Você pode ajustar o uso de memória editando a MAX_BYTESconstante, atualmente definida em 8 GiB.

Como funciona

O conjunto é construído por uma sequência de decisões binárias (cada número é dentro ou fora do conjunto), cujas probabilidades são calculadas combinatorialmente, contando o número de possíveis conjuntos construtíveis após cada escolha usando programação dinâmica.

O uso de memória para n grande é reduzido usando uma versão dessa estratégia de particionamento 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");
    }
}

Experimente online!

(Nota: a versão do TIO tem algumas modificações. Primeiro, o limite de memória é reduzido para 1 GiB. Segundo, como o TIO não permite que você escreva ae Cargo.tomldependa de caixas externas como rand, em vez disso, extraí drand48da biblioteca C usando o FFI. Como não me preocupei em propagar isso, a versão TIO produzirá o mesmo resultado a cada execução. Não use a versão TIO para comparações oficiais.)

Java 7+, n = 50 in ~ 30 seg no 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;
      }
    }
  }
}

A versão ungolfed da minha resposta para a versão code-golf deste desafio, por enquanto, com apenas uma pequena alteração: java.util.Random#nextInt(limit)é usada em vez de (int)(Math.random()*limit)para um número inteiro no intervalo [0, n), pois é duas vezes mais rápido .

Experimente online.

Explicação:

Abordagem utilizada:

O código é dividido em duas partes:

1. Gere uma lista da nquantidade de números inteiros aleatórios que somam n squared.
2. Em seguida, verifica se todos os valores são únicos e nenhum é zero, e se um deles é falsey, ele tentará a etapa 1 novamente, enxaguando e repetindo até obtermos um resultado.

A etapa 1 é realizada com as seguintes subetapas:

1) Gere uma matriz de n-1quantidade de números inteiros aleatórios no intervalo [0, n squared). E adicione 0e n squareda esta lista. Isso é feito no O(n+1)desempenho.
2) Em seguida, ele classificará o array com o builtin java.util.Arrays.sort(int[]). Isso é feito no O(n*log(n))desempenho, conforme declarado nos documentos:

Classifica a matriz especificada de ints em ordem numérica crescente. O algoritmo de classificação é um quicksort ajustado, adaptado de Jon L. Bentley e "Engineering a Sort Function" de M. Douglas McIlroy, Software-Practice and Experience, vol. 23 (11) P. 1249-1265 (novembro de 1993). Esse algoritmo oferece desempenho n * log (n) em muitos conjuntos de dados que fazem com que outras classificações rápidas sejam degradadas para desempenho quadrático.

3) Calcule a diferença entre cada par. Essa lista resultante de diferenças conterá nnúmeros inteiros que somam n squared. Isso é feito no O(n)desempenho.

Aqui está um exemplo:

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

Portanto, essas três etapas acima são muito boas para o desempenho, diferentemente da etapa 2 e do ciclo da coisa toda, que é uma força bruta básica. A etapa 2 é dividida nestas sub-etapas:

1) A lista de diferenças já está salva em a java.util.Set. Ele verificará se o tamanho deste conjunto é igual a n. Se for, significa que todos os valores aleatórios que geramos são únicos.
2) E também verificará se não contém nenhum 0no conjunto, pois o desafio solicita valores aleatórios no intervalo [1, X], onde Xé n squaredmenos a soma de [1, ..., n-1], conforme declarado por @Skidsdev no comentário abaixo.

Se uma das duas opções acima (nem todos os valores forem únicos ou houver zero), ela gerará uma nova matriz e definirá novamente redefinindo a etapa 1. Isso continua até que tenhamos um resultado. Por esse motivo, o tempo pode variar bastante. Eu já vi isso terminar em 3 segundos uma vez no TIO n=50, mas também em 55 segundos uma vez n=50.

Prova de uniformidade:

Não tenho muita certeza de como provar isso para ser completamente honesto. O java.util.Random#nextInté uniforme, com certeza, conforme descrito nos documentos:

Retorna o próximo valor pseudoaleatório, distribuído uniformemente, a intpartir desta sequência do gerador de números aleatórios. O contrato geral de nextInté que um intvalor seja gerado e retornado pseudo-aleatoriamente. Todos os 2 ³²int valores possíveis são produzidos com (aproximadamente) probabilidade igual.

As diferenças entre esses valores aleatórios (classificados) não são, obviamente, uniformes, mas os conjuntos como um todo são uniformes. Novamente, não tenho certeza de como provar isso matematicamente, mas aqui está um script que colocará 10,000conjuntos gerados (para n=10) em um mapa com um contador , onde a maioria dos conjuntos é única; alguns repetiram duas vezes; e a ocorrência máxima repetida geralmente está no intervalo [4,8].

Instruções de instalação:

Como o Java é uma linguagem bastante conhecida, com muitas informações disponíveis sobre como criar e executar o código Java, vou manter isso breve.
Todas as ferramentas usadas no meu código estão disponíveis no Java 7 (talvez até no Java 5 ou 6, mas vamos usar 7 apenas por precaução). Eu tenho certeza que o Java 7 já está arquivado, então eu sugiro fazer o download do Java 8 para executar meu código.

Reflexões sobre melhorias:

Gostaria de encontrar uma melhoria para a verificação de zeros e verificar se todos os valores são únicos. Eu poderia verificar 0antes, certificando-me de que o valor aleatório que adicionamos à matriz ainda não esteja nela, mas isso significaria algumas coisas: a matriz deve ser uma ArrayListpara que possamos usar o método interno .contains; um loop while deve ser adicionado até encontrarmos um valor aleatório que ainda não esteja na lista. Como a verificação de zero agora é feita .contains(0)no conjunto (que é verificado apenas uma vez), é mais provável que seja melhor verificar o desempenho nesse ponto, em comparação com adicionar o loop .containsna lista, que será verificado pelo menos nvezes , mas provavelmente mais.

Quanto à verificação de exclusividade, só temos nossa nquantidade de números inteiros aleatórios que somam n squaredapós a etapa 1 do programa; portanto, só assim podemos verificar se todos são únicos ou não. Pode ser possível manter uma lista classificável em vez de matriz e verificar as diferenças entre elas, mas duvido seriamente que melhore o desempenho do que apenas colocá-las em Sete verifique se o tamanho desse conjunto é numa vez.

Mathematica n = 11

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