nBerechnen Sie bei gegebener Ganzzahl eine Menge nzufälliger eindeutiger Ganzzahlen im Bereich 1..n^2(einschließlich) so, dass die Summe der Menge gleich istn^2

Zufällig bedeutet in diesem Fall gleichmäßig zufällig zwischen gültigen Ausgaben. Jede gültige Ausgabe für eine bestimmte Ausgabe nmuss eine einheitliche Chance haben, generiert zu werden.

Zum Beispiel n=3sollte eine 1/3 Chance jeweils Ausgeben hat 6, 1, 2, 3, 5, 1oder 4, 3, 2. Da es sich um eine Menge handelt, ist die Reihenfolge irrelevant und 4, 3, 2identisch mit3, 2, 4

Wertung

Der Gewinner ist das Programm, das in weniger als n60 Sekunden den höchsten Wert berechnen kann .
Hinweis: Um eine mögliche teilweise Hardcodierung zu verhindern, müssen alle Einträge unter 4000 Byte liegen

Testen

Der gesamte Code wird auf meinem lokalen Windows 10-Computer ausgeführt (Razer Blade 15, 16 GB RAM, Intel i7-8750H 6-Kerne, 4,1 GHz, GTX 1060, falls Sie die GPU missbrauchen möchten). Geben Sie daher bitte detaillierte Anweisungen zum Ausführen Ihres Codes an meine Maschine.
Auf Anfrage können Einträge entweder über Debian in der WSL oder auf einer virtuellen Xubuntu-Maschine ausgeführt werden (beide auf derselben Maschine wie oben).

Die Einreichungen werden 50 Mal hintereinander durchgeführt. Das Endergebnis ist ein Durchschnitt aller 50 Ergebnisse.

Rust , n ≈ 1400

Wie man läuft

Bauen mit cargo build --releaseund laufen mit target/release/arbitrary-randomness n.

Dieses Programm läuft am schnellsten mit viel Speicher (solange es natürlich nicht ausgetauscht wird). Sie können die Speichernutzung anpassen, indem Sie die MAX_BYTESKonstante bearbeiten , die derzeit auf 8 GiB eingestellt ist.

Wie es funktioniert

Die Menge wird durch eine Folge von binären Entscheidungen konstruiert (jede Zahl befindet sich entweder innerhalb oder außerhalb der Menge), deren Wahrscheinlichkeiten kombinatorisch berechnet werden, indem die Anzahl möglicher Mengen gezählt wird, die nach jeder Auswahl unter Verwendung dynamischer Programmierung konstruierbar sind.

Die Speichernutzung für große n wird durch die Verwendung einer Version dieser Binomialpartitionierungsstrategie reduziert .

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

Probieren Sie es online aus!

(Hinweis: Die TIO-Version enthält einige Änderungen. Erstens ist das Speicherlimit auf 1 GiB reduziert. Zweitens habe ich, da Sie mit TIO keine schreiben können Cargo.tomlund von externen Kisten abhängig sind rand, stattdessen mit der drand48aus der C-Bibliothek gezogen FFI. Ich habe mich nicht darum gekümmert, es zu setzen, daher wird die TIO-Version bei jedem Lauf das gleiche Ergebnis erzielen. Verwenden Sie die TIO-Version nicht für offizielles Benchmarking.)

Java 7+, n = 50 in ~ 30 Sekunden auf 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 meiner Antwort für die Code-Golf-Version dieser Herausforderung mit nur einer geringfügigen Änderung: Wird java.util.Random#nextInt(limit)anstelle (int)(Math.random()*limit)einer Ganzzahl im Bereich verwendet [0, n), da sie ungefähr doppelt so schnell ist .

Probieren Sie es online aus.

Erläuterung:

Verwendeter Ansatz:

Der Code ist in zwei Teile unterteilt:

1. Generieren Sie eine Liste mit nzufälligen Ganzzahlen, die sich summieren n squared.
2. Dann wird geprüft, ob alle Werte eindeutig und keiner Null sind. Wenn einer der beiden Werte falsch ist, wird Schritt 1 erneut versucht, wobei gespült und wiederholt wird, bis ein Ergebnis vorliegt.

Schritt 1 wird mit den folgenden Unterschritten ausgeführt:

1) Generieren Sie ein Array n-1mit zufälligen Ganzzahlen im Bereich [0, n squared). Und füge 0und n squaredzu dieser Liste hinzu. Dies geschieht in der O(n+1)Leistung.
2) Dann wird das Array mit dem eingebauten Array sortiert java.util.Arrays.sort(int[]). Dies erfolgt in der O(n*log(n))Leistung, wie in den Dokumenten angegeben:

Sortiert das angegebene Ints-Array in aufsteigender numerischer Reihenfolge. Der Sortieralgorithmus ist ein abgestimmter Quicksort, adaptiert von Jon L. Bentley und M. Douglas McIlroys "Engineering a Sort Function", Software-Practice and Experience, Vol. 3, No. 23 (11) S. 1249-1265 (November 1993). Dieser Algorithmus bietet eine n * log (n) -Leistung für viele Datensätze, die dazu führen, dass andere Quicksorts auf eine quadratische Leistung abfallen.

3) Berechnen Sie die Differenz zwischen jedem Paar. Diese resultierende Liste von Unterschieden enthält nGanzzahlen, die sich zu summieren n squared. Dies geschieht in der O(n)Leistung.

Hier ein Beispiel:

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

Diese drei obigen Schritte sind also ziemlich gut für die Leistung, im Gegensatz zu Schritt 2 und der Schleife um das Ganze, die eine grundlegende Brute-Force ist. Schritt 2 ist in folgende Unterschritte unterteilt:

1) Die Differenzliste ist bereits in a gespeichert java.util.Set. Es wird geprüft, ob die Größe dieses Sets gleich ist n. Wenn dies der Fall ist, bedeutet dies, dass alle von uns generierten Zufallswerte eindeutig sind.
2) Und es wird auch prüfen, ob es nicht enthält 0im Set, da die Herausforderung für Zufallswerte im Bereich fragt [1, X], wo Xist n squaredabzüglich der Summe der [1, ..., n-1], wie angegeben @Skidsdev unten im Kommentar.

Wenn eine der beiden oben genannten Optionen (nicht alle Werte sind eindeutig oder eine Null vorhanden) vorhanden ist, wird ein neues Array generiert und durch Zurücksetzen auf Schritt 1 erneut festgelegt. Dies wird fortgesetzt, bis ein Ergebnis vorliegt. Aus diesem Grund kann die Zeit sehr unterschiedlich sein. Ich habe gesehen, dass es in 3 Sekunden einmal auf TIO beendet wurde n=50, aber auch einmal in 55 Sekunden n=50.

Beweis der Einheitlichkeit:

Ich bin mir nicht ganz sicher, wie ich das beweisen soll, um ganz ehrlich zu sein. Das java.util.Random#nextIntist sicher einheitlich, wie in den Dokumenten beschrieben:

Gibt den nächsten pseudozufälligen, gleichmäßig verteilten intWert aus der Sequenz dieses Zufallszahlengenerators zurück. Der allgemeine Vertrag von nextIntist, dass ein intWert pseudozufällig generiert und zurückgegeben wird. Alle 2 ³² möglichen intWerte werden mit (ungefähr) gleicher Wahrscheinlichkeit erzeugt.

Die Unterschiede zwischen diesen (sortierten) Zufallswerten selbst sind natürlich nicht einheitlich, aber die Mengen als Ganzes sind einheitlich. Auch hier bin ich mir nicht sicher, wie ich das mathematisch beweisen soll, aber hier ist ein Skript, das 10,000generierte Mengen (für n=10) in eine Karte mit einem Zähler einfügt , wobei die meisten Mengen eindeutig sind. einige wiederholten sich zweimal; und das maximale wiederholte Auftreten liegt gewöhnlich im Bereich [4,8].

Installationsanleitung:

Da Java eine ziemlich bekannte Sprache mit vielen verfügbaren Informationen zum Erstellen und Ausführen von Java-Code ist, werde ich mich kurz fassen.
Alle in meinem Code verwendeten Tools sind in Java 7 verfügbar (vielleicht sogar bereits in Java 5 oder 6, aber verwenden wir 7 nur für den Fall). Ich bin mir ziemlich sicher, dass Java 7 bereits archiviert ist, daher würde ich empfehlen, Java 8 herunterzuladen, um meinen Code auszuführen.

Gedanken zu Verbesserungen:

Ich möchte eine Verbesserung für die Prüfung auf Nullen finden und prüfen, ob alle Werte eindeutig sind. Ich könnte 0vorher ArrayListnachsehen , indem ich sicherstelle, dass der Zufallswert, den wir dem Array hinzufügen, nicht bereits darin enthalten ist, aber es würde ein paar Dinge bedeuten: Das Array sollte ein sein, damit wir die eingebaute Methode verwenden können .contains; Eine while-Schleife sollte hinzugefügt werden, bis wir einen zufälligen Wert gefunden haben, der noch nicht in der Liste enthalten ist. Da die Überprüfung auf Null jetzt mit .contains(0)dem Set durchgeführt wird (das nur einmal überprüft wird), ist es für die Leistung höchstwahrscheinlich besser, sie an diesem Punkt zu überprüfen, als die Schleife mit .containsin der Liste hinzuzufügen , die mindestens einmal überprüft nwird , aber höchstwahrscheinlich mehr.

Bei der Eindeutigkeitsprüfung haben wir nur die nAnzahl der zufälligen Ganzzahlen, die sich n squarednach Schritt 1 des Programms summieren. Erst dann können wir prüfen, ob alle eindeutig sind oder nicht. Es könnte möglich sein, eine sortierbare Liste anstelle eines Arrays zu führen und die Unterschiede dazwischen zu überprüfen, aber ich bezweifle ernsthaft, dass dies die Leistung verbessern wird, als sie nur in eine Liste zu setzen Setund zu überprüfen, ob die Größe dieses Sets neinmal ist.

Mathematica n = 11

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