Étant donné un entier n, calculez un ensemble d' nentiers uniques aléatoires dans la plage 1..n^2(incluse) de telle sorte que la somme de l'ensemble soit égale àn^2

Aléatoire, dans ce cas, signifie uniformément aléatoire entre des sorties valides. Chaque sortie valide pour une donnée ndoit avoir une chance uniforme d'être générée.

Par exemple, n=3devrait avoir une chance de chacun de 1/3 sortie 6, 1, 2, 3, 5, 1ou 4, 3, 2. Comme il s'agit d'un ensemble, l'ordre n'est pas pertinent, 4, 3, 2est identique à3, 2, 4

Notation

Le gagnant est le programme qui peut calculer le plus élevé nen moins de 60 secondes.
Remarque: Pour éviter un éventuel codage partiel, toutes les entrées doivent être inférieures à 4000 octets

Essai

Tout le code sera exécuté sur ma machine Windows 10 locale (Razer Blade 15, 16 Go de RAM, Intel i7-8750H 6 cœurs, 4,1 GHz, GTX 1060 au cas où vous voudriez abuser du GPU), veuillez donc fournir des instructions détaillées pour exécuter votre code sur ma machine.
Sur demande, les entrées peuvent être exécutées soit via Debian sur WSL, soit sur une machine virtuelle Xubuntu (les deux sur la même machine que ci-dessus)

Les soumissions seront exécutées 50 fois de suite, le score final sera une moyenne des 50 résultats.

Rouille , n ≈ 1400

Comment courir

Construisez avec cargo build --releaseet exécutez avec target/release/arbitrary-randomness n.

Ce programme s'exécute le plus rapidement avec beaucoup de mémoire (tant qu'il ne change pas, bien sûr). Vous pouvez ajuster son utilisation de la mémoire en modifiant la MAX_BYTESconstante, actuellement fixée à 8 Gio.

Comment ça fonctionne

L'ensemble est construit par une séquence de décisions binaires (chaque nombre est à l'intérieur ou à l'extérieur de l'ensemble), dont chacune des probabilités est calculée de manière combinatoire en comptant le nombre d'ensembles possibles constructibles après chaque choix en utilisant la programmation dynamique.

L'utilisation de la mémoire pour les grands n est réduite en utilisant une version de cette stratégie de partitionnement 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");
    }
}

Essayez-le en ligne!

(Remarque: la version TIO a quelques modifications. Premièrement, la limite de mémoire est réduite à 1 Gio. Deuxièmement, puisque TIO ne vous permet pas d'écrire un Cargo.tomlet de dépendre de caisses externes comme rand, j'ai plutôt tiré drand48de la bibliothèque C en utilisant le FFI. Je n'ai pas pris la peine de le semer, donc la version TIO produira le même résultat à chaque exécution. N'utilisez pas la version TIO pour le benchmarking officiel.)

Java 7+, n = 50 dans ~ 30 sec sur 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;
      }
    }
  }
}

Version non golfée de ma réponse pour la version code-golf de ce défi pour l'instant, avec un seul changement mineur: java.util.Random#nextInt(limit)est utilisé à la place d' (int)(Math.random()*limit)un entier dans la plage [0, n), car il est environ deux fois plus rapide .

Essayez-le en ligne.

Explication:

Approche utilisée:

Le code est divisé en deux parties:

1. Générez une liste de nnombres entiers aléatoires qui totalisent n squared.
2. Ensuite, il vérifie si toutes les valeurs sont uniques et aucune n'est nulle, et s'il s'agit de falsey, il réessayera l'étape 1, en rinçant et en répétant jusqu'à ce que nous ayons un résultat.

L'étape 1 se fait avec les sous-étapes suivantes:

1) Générez un tableau de n-1nombres entiers aléatoires dans la plage [0, n squared). Et ajoutez 0et n squaredà cette liste. Cela se fait dans les O(n+1)performances.
2) Ensuite, il triera le tableau avec le code intégré java.util.Arrays.sort(int[]), cela se fait en O(n*log(n))termes de performances, comme indiqué dans les documents:

Trie le tableau spécifié d'entiers dans l'ordre numérique croissant. L'algorithme de tri est un tri rapide ajusté, adapté de "Engineering a Sort Function" de Jon L. Bentley et M. Douglas McIlroy, Software-Practice and Experience, Vol. 23 (11) P. 1249-1265 (novembre 1993). Cet algorithme offre des performances n * log (n) sur de nombreux ensembles de données, ce qui entraîne la dégradation d'autres performances rapides en performances quadratiques.

3) Calculez la différence entre chaque paire. Cette liste résultante de différences contiendra des nnombres entiers qui se résument à n squared. Cela se fait dans les O(n)performances.

Voici un exemple:

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

Ces trois étapes ci-dessus sont donc plutôt bonnes pour les performances, contrairement à l'étape 2 et à la boucle autour de l'ensemble, qui est une force brute de base. L'étape 2 est divisée en ces sous-étapes:

1) La liste des différences est déjà enregistrée dans a java.util.Set. Il vérifiera si la taille de cet ensemble est égale à n. Si c'est le cas, cela signifie que toutes les valeurs aléatoires que nous avons générées sont uniques.
2) Et il vérifiera également qu'il ne contient pas 0dans l'ensemble, car le défi demande des valeurs aléatoires dans la plage [1, X], où Xest n squaredmoins la somme de [1, ..., n-1], comme indiqué par @Skidsdev dans le commentaire ci-dessous.

Si l'une des deux options ci-dessus (toutes les valeurs ne sont pas uniques ou un zéro est présent), elle générera un nouveau tableau et se remettra à zéro en revenant à l'étape 1. Cela continue jusqu'à ce que nous ayons un résultat. Pour cette raison, le temps peut varier considérablement. Je l'ai vu finir en 3 secondes une fois sur TIO pour n=50, mais aussi en 55 secondes une fois pour n=50.

Preuve d'uniformité:

Je ne sais pas vraiment comment prouver cela pour être complètement honnête. Le java.util.Random#nextIntest uniforme à coup sûr, comme décrit dans la documentation:

Renvoie la valeur pseudo-aléatoire suivante, uniformément distribuée int, à partir de la séquence de ce générateur de nombres aléatoires. Le contrat général nextIntest qu'une intvaleur est générée et renvoyée de manière pseudo-aléatoire. Les 2 ³²int valeurs possibles sont produites avec une probabilité (approximativement) égale.

Les différences entre ces valeurs aléatoires (triées) elles-mêmes ne sont bien sûr pas uniformes, mais les ensembles dans leur ensemble sont uniformes. Encore une fois, je ne sais pas comment le prouver mathématiquement, mais voici un script qui mettra les 10,000ensembles générés (pour n=10) dans une carte avec un compteur , où la plupart des ensembles sont uniques; certains ont répété deux fois; et l'occurrence répétée maximale se situe généralement dans la plage [4,8].

Instructions d'installation:

Étant donné que Java est un langage assez bien connu avec de nombreuses informations disponibles sur la façon de créer et d'exécuter du code Java, je serai bref.
Tous les outils utilisés dans mon code sont disponibles en Java 7 (peut-être même déjà en Java 5 ou 6, mais utilisons 7 au cas où). Je suis à peu près sûr que Java 7 est déjà archivé, donc je suggère de télécharger Java 8 pour exécuter mon code.

Réflexions sur les améliorations:

Je voudrais trouver une amélioration pour la vérification des zéros et vérifier que toutes les valeurs sont uniques. Je pourrais vérifier 0avant, en m'assurant que la valeur aléatoire que nous ajoutons au tableau n'est pas déjà dedans, mais cela signifierait quelques choses: le tableau devrait être un ArrayListafin que nous puissions utiliser la méthode intégrée .contains; une boucle while devrait être ajoutée jusqu'à ce que nous trouvions une valeur aléatoire qui ne figure pas encore dans la liste. Étant donné que la vérification de zéro est désormais effectuée avec .contains(0)sur l'ensemble (qui n'est vérifié qu'une seule fois), il est probablement préférable que les performances le vérifient à ce stade, par rapport à l'ajout de la boucle avec .containssur la liste, qui sera vérifiée au moins une nfois , mais probablement plus.

En ce qui concerne la vérification de l'unicité, nous n'avons que notre nquantité d'entiers aléatoires qui résument n squaredaprès l'étape 1 du programme, donc seulement alors nous pouvons vérifier si tous sont uniques ou non. Il pourrait être possible de conserver une liste triable au lieu d'un tableau et de vérifier les différences entre les deux, mais je doute sérieusement que cela améliorera les performances que de simplement les mettre dans un Setet vérifier si la taille de cet ensemble est nune fois.

Mathematica n = 11

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