Biorąc pod uwagę liczbę całkowitą n, oblicz zestaw nlosowych unikatowych liczb całkowitych w zakresie 1..n^2(włącznie) tak, aby suma tego zbioru była równan^2

W tym przypadku losowy oznacza równomiernie losowy między prawidłowymi wyjściami. Każde prawidłowe wyjście dla danej nmusi mieć jednolitą szansę na wygenerowanie.

Na przykład, n=3powinien mieć szansę 1/3 każdego wyprowadzania 6, 1, 2, 3, 5, 1albo 4, 3, 2. Ponieważ jest to zestaw, kolejność jest nieistotna, 4, 3, 2jest identyczna z3, 2, 4

Punktacja

Zwycięzcą jest program, który może obliczyć najwyższy nw czasie krótszym niż 60 sekund.
Uwaga: Aby zapobiec możliwemu częściowemu kodowaniu na sztywno, wszystkie wpisy muszą mieć mniej niż 4000 bajtów

Testowanie

Cały kod będzie uruchamiany na moim lokalnym komputerze z systemem Windows 10 (Razer Blade 15, 16 GB RAM, Intel i7-8750H 6 rdzeni, 4.1GHz, GTX 1060 na wypadek, gdybyś chciał nadużyć GPU), więc podaj szczegółowe instrukcje, aby uruchomić swój kod na moja maszyna.
Na żądanie wpisy mogą być uruchamiane za pośrednictwem Debiana na WSL lub na maszynie wirtualnej Xubuntu (obie na tej samej maszynie, jak powyżej)

Zgłoszenia będą przeprowadzane 50 razy z rzędu, końcowy wynik będzie średnią z wszystkich 50 wyników.

Rdza , n ≈ 1400

Jak biegać

Kompiluj cargo build --releasei uruchamiaj z target/release/arbitrary-randomness n.

Ten program działa najszybciej z dużą ilością pamięci (o ile oczywiście nie zamienia). Możesz dostosować zużycie pamięci, edytując MAX_BYTESstałą, obecnie ustawioną na 8 GiB.

Jak to działa

Zbiór jest konstruowany na podstawie sekwencji decyzji binarnych (każda liczba znajduje się wewnątrz lub na zewnątrz zestawu), z których każde prawdopodobieństwo jest obliczane kombinatorycznie poprzez zliczenie liczby możliwych zestawów możliwych do zbudowania po każdym wyborze za pomocą programowania dynamicznego.

Wykorzystanie pamięci dla dużych n jest zmniejszone przez zastosowanie wersji tej dwumianowej strategii partycjonowania .

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

Wypróbuj online!

(Uwaga: wersja TIO ma kilka modyfikacji. Po pierwsze, limit pamięci jest zredukowany do 1 GiB. Po drugie, ponieważ TIO nie pozwala na napisanie a Cargo.tomli zależy od zewnętrznych skrzynek, na przykład rand, zamiast tego ściągnąłem drand48z biblioteki C za pomocą FFI. Nie zadałem sobie trudu, aby go zaszczepić, więc wersja TIO będzie generować taki sam wynik przy każdym uruchomieniu. Nie używaj wersji TIO do oficjalnych testów porównawczych.)

Java 7+, n = 50 w ~ 30 sekund na 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;
      }
    }
  }
}

Niegolfowana wersja mojej odpowiedzi na kodową wersję tego wyzwania na razie, z jedną drobną zmianą: java.util.Random#nextInt(limit)jest używana zamiast liczby (int)(Math.random()*limit)całkowitej w zakresie [0, n), ponieważ jest ona około dwa razy szybsza .

Wypróbuj online.

Wyjaśnienie:

Zastosowane podejście:

Kod jest podzielony na dwie części:

1. Wygeneruj listę nlosowych liczb całkowitych, które sumują się n squared.
2. Następnie sprawdza, czy wszystkie wartości są unikalne, a żadna z nich nie jest równa zero, a jeśli któraś z nich ma wartość falsey, spróbuje ponownie wykonać krok 1, płucząc i powtarzając, aż uzyskamy wynik.

Krok 1 składa się z następujących podetapów:

1) Wygeneruj tablicę n-1liczb losowych liczb całkowitych w zakresie [0, n squared). I dodaj 0i n squareddo tej listy. Odbywa się to w O(n+1)wydajności.
2) Następnie posortuje tablicę z wbudowanym java.util.Arrays.sort(int[]), Jest to wykonywane w O(n*log(n))wydajności, jak stwierdzono w dokumentach:

Sortuje określoną tablicę liczb całkowitych w rosnącym porządku numerycznym. Algorytm sortowania jest zestrojonym szybkim sortowaniem, zaadaptowanym przez Jona L. Bentleya i M. Douglasa McIlroy'a „Engineering a Sort Function”, Software-Practice and Experience, tom. 23 (11) P. 1249-1265 (listopad 1993). Algorytm ten oferuje wydajność n * log (n) w wielu zestawach danych, które powodują, że inne szybkie sortowanie obniża się do wydajności kwadratowej.

3) Oblicz różnicę między każdą parą. Ta wynikowa lista różnic będzie zawierać nliczby całkowite, które sumują się n squared. Odbywa się to w O(n)wydajności.

Oto przykład:

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

Te trzy powyższe kroki są całkiem dobre pod względem wydajności, w przeciwieństwie do kroku 2 i pętli wokół całości, która jest podstawową brutalną siłą. Krok 2 dzieli się na następujące podetapy:

1) Lista różnic jest już zapisana w pliku java.util.Set. Sprawdzi, czy rozmiar tego zestawu jest równy n. Jeśli tak, oznacza to, że wszystkie wygenerowane przez nas losowe wartości są unikalne.
2) I sprawdzi również, czy nie zawiera go 0w zestawie, ponieważ wyzwanie prosi o losowe wartości w zakresie [1, X], gdzie Xjest n squaredminus suma [1, ..., n-1], jak stwierdził @Skidsdev w komentarzu poniżej.

Jeśli jedna z dwóch powyższych opcji (nie wszystkie wartości są unikalne lub zero jest obecne), wygeneruje nową tablicę i ustawi ponownie, resetując do kroku 1. Trwa to do momentu uzyskania wyniku. Z tego powodu czas może się nieco różnić. Widziałem, jak kończy się za 3 sekundy na TIO n=50, ale także za 55 sekund n=50.

Dowód jednolitości:

Nie jestem do końca pewien, jak to udowodnić. Na java.util.Random#nextIntpewno jest jednolity, jak opisano w dokumentach:

Zwraca następny pseudolosowy, równomiernie rozłożoną intwartość z sekwencji generatora liczb losowych. Ogólna umowa nextIntjest taka, że ​​jedna intwartość jest pseudolosowo generowana i zwracana. Wszystkie 2 ³² możliwe intwartości są tworzone z (w przybliżeniu) jednakowym prawdopodobieństwem.

Różnice między tymi (posortowanymi) wartościami losowymi same w sobie oczywiście nie są jednolite, ale zestawy jako całość są jednolite. Ponownie, nie jestem pewien, jak to udowodnić matematycznie, ale tutaj jest skrypt, który umieści 10,000wygenerowane zestawy (dla n=10) na mapie z licznikiem , gdzie większość zestawów jest unikalna; niektóre powtórzyły się dwukrotnie; a maksymalne powtarzające się wystąpienie zwykle mieści się w zakresie [4,8].

Instrukcje Instalacji:

Ponieważ Java jest dość dobrze znanym językiem z dużą ilością dostępnych informacji na temat tworzenia i uruchamiania kodu Java, powiem to krótko.
Wszystkie narzędzia użyte w moim kodzie są dostępne w Javie 7 (być może nawet już w Javie 5 lub 6, ale na wszelki wypadek użyjmy 7). Jestem pewien, że Java 7 jest już zarchiwizowana, więc sugeruję pobranie Java 8, aby uruchomić mój kod.

Myśli dotyczące ulepszeń:

Chciałbym znaleźć ulepszenie w zakresie sprawdzania zer i sprawdzania, czy wszystkie wartości są unikalne. Mógłbym to sprawdzić 0wcześniej, upewniając się, że losowa wartość, którą dodajemy do tablicy, już jej nie ma, ale oznaczałoby to kilka rzeczy: tablica powinna być, ArrayListwięc możemy użyć wbudowanej metody .contains; pętla while powinna być dodawana, dopóki nie znajdziemy losowej wartości, która nie znajduje się jeszcze na liście. Ponieważ sprawdzanie zera jest teraz wykonywane .contains(0)na zestawie (który jest sprawdzany tylko raz), najprawdopodobniej lepiej jest sprawdzić wydajność w tym punkcie, w porównaniu do dodawania pętli z .containslistą, która będzie sprawdzana przynajmniej nraz , ale najprawdopodobniej więcej.

Jeśli chodzi o kontrolę unikatowości, mamy tylko nliczbę losowych liczb całkowitych, które sumują się n squaredpo kroku 1 programu, więc tylko wtedy możemy sprawdzić, czy wszystkie są unikalne. Może być możliwe utrzymanie sortowalnej listy zamiast tablicy i sprawdzenie różnic między nimi, ale poważnie wątpię, że poprawi to wydajność, niż tylko umieszczenie ich w Seti sprawdzenie, czy rozmiar tego zestawu jest njeden.

Matematyka n = 11

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