Bilangan bulat yang diberikan n, hitung satu set nbilangan bulat unik acak dalam rentang 1..n^2(inklusif) sehingga jumlah himpunan sama dengann^2

Acak, dalam hal ini, berarti acak seragam antara keluaran yang valid. Setiap output yang valid untuk suatu yang diberikan nharus memiliki peluang seragam untuk dihasilkan.

Misalnya, n=3harus memiliki kesempatan 1/3 masing-masing keluaran 6, 1, 2, 3, 5, 1atau 4, 3, 2. Karena ini adalah himpunan, urutan tidak relevan, 4, 3, 2identik dengan3, 2, 4

Mencetak gol

Pemenangnya adalah program yang dapat menghitung tertinggi ndalam waktu kurang dari 60 detik.
Catatan: Untuk mencegah kemungkinan hardcoding parsial, semua entri harus kurang dari 4000 byte

Pengujian

Semua kode akan dijalankan pada mesin Windows 10 lokal saya (Razer Blade 15, RAM 16GB, Intel i7-8750H 6 core, 4.1GHz, GTX 1060 jika Anda ingin menyalahgunakan GPU) jadi harap berikan instruksi terperinci untuk menjalankan kode Anda di mesin saya.
Atas permintaan, entri dapat dijalankan melalui Debian di WSL, atau di Mesin Virtual Xubuntu (keduanya di mesin yang sama seperti di atas)

Pengajuan akan dijalankan 50 kali berturut-turut, skor akhir akan menjadi rata-rata dari semua 50 hasil.

Karat , n ≈ 1400

Bagaimana cara menjalankannya

Bangun dengan cargo build --release, dan jalankan bersama target/release/arbitrary-randomness n.

Program ini berjalan tercepat dengan banyak memori (asalkan tidak bertukar, tentu saja). Anda dapat menyesuaikan penggunaan memorinya dengan mengedit MAX_BYTESkonstanta, yang saat ini ditetapkan pada 8 GiB.

Bagaimana itu bekerja

Himpunan dibangun oleh urutan keputusan biner (masing-masing angka baik di dalam atau di luar himpunan), masing-masing yang probabilitas dihitung secara kombinatorial dengan menghitung jumlah set yang mungkin dibangun setelah setiap pilihan menggunakan pemrograman dinamis.

Penggunaan memori untuk besar n dikurangi dengan menggunakan versi strategi partisi binomial ini .

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

Cobalah online!

(Catatan: versi TIO memiliki beberapa modifikasi. Pertama, batas memori dikurangi menjadi 1 GiB. Kedua, karena TIO tidak membiarkan Anda menulis Cargo.tomldan bergantung pada peti eksternal seperti rand, saya malah menarik drand48dari perpustakaan C menggunakan FFI. Saya tidak repot-repot me-seed-kannya, jadi versi TIO akan menghasilkan hasil yang sama setiap kali dijalankan. Jangan gunakan versi TIO untuk pembandingan resmi.)

Java 7+, n = 50 dalam ~ 30 dtk di 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;
      }
    }
  }
}

Versi jawaban saya yang tidak digabungkan untuk versi kode-golf dari tantangan ini untuk saat ini, dengan hanya satu perubahan kecil: java.util.Random#nextInt(limit)digunakan sebagai ganti(int)(Math.random()*limit) untuk bilangan bulat dalam kisaran [0, n), karena ini sekitar dua kali lebih cepat .

Cobalah online.

Penjelasan:

Pendekatan yang digunakan:

Kode ini dibagi menjadi dua bagian:

1. Buat daftar n jumlah bilangan bulat acak yang dijumlahkan n squared.
2. Kemudian ia memeriksa apakah semua nilai unik dan tidak ada yang nol, dan jika salah adalah falsey, ia akan mencoba langkah 1 lagi, membilas dan mengulangi sampai kita mendapatkan hasil.

Langkah 1 dilakukan dengan sub-langkah berikut:

1) Hasilkan array n-1jumlah integer acak dalam rentang [0, n squared). Dan tambahkan 0dan n squaredke daftar ini. Ini dilakukan dalam O(n+1)kinerja.
2) Kemudian akan mengurutkan array dengan builtin java.util.Arrays.sort(int[]), ini dilakukan dalam O(n*log(n))kinerja, seperti yang dinyatakan dalam dokumen:

Mengurutkan array int tertentu ke dalam urutan numerik. Algoritma pengurutan adalah quicksort yang disetel, diadaptasi dari Jon L. Bentley dan M. Douglas McIlroy "Engineering a Sort Function", Praktek-Perangkat Lunak dan Pengalaman, Vol. 23 (11) P. 1249-1265 (November 1993). Algoritma ini menawarkan kinerja n * log (n) pada banyak set data yang menyebabkan quicksort lain menurun ke kinerja kuadratik.

3) Hitung perbedaan antara masing-masing pasangan. Daftar perbedaan yang dihasilkan ini akan berisi nbilangan bulat yang dijumlahkan n squared. Ini dilakukan diO(n) kinerja.

Berikut sebuah contoh:

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

Jadi tiga langkah di atas cukup baik untuk kinerja, tidak seperti langkah 2 dan lingkaran di sekitar semuanya, yang merupakan kekuatan kasar dasar. Langkah 2 dibagi dalam sub-langkah ini:

1) Daftar perbedaan sudah disimpan dalam a java.util.Set. Ini akan memeriksa apakah ukuran Set ini sama dengan n. Jika ya, itu berarti semua nilai acak yang kami hasilkan adalah unik.
2) Dan itu juga akan memeriksa bahwa itu tidak mengandung 0dalam Set, karena tantangan meminta nilai acak dalam kisaran [1, X], di mana Xadalah n squareddikurangi jumlah [1, ..., n-1], seperti yang dinyatakan oleh @Skidsdev dalam komentar di bawah ini.

Jika salah satu dari dua opsi di atas (tidak semua nilai unik, atau nol ada), itu akan menghasilkan array baru dan Atur lagi dengan mengatur ulang ke langkah 1. Ini berlanjut sampai kita mendapatkan hasil. Karena itu, waktunya dapat sedikit berbeda. Saya telah melihatnya selesai dalam 3 detik sekali pada TIO untuk n=50, tetapi juga dalam 55 detik sekali untuk n=50.

Buktikan keseragaman:

Saya tidak sepenuhnya yakin bagaimana membuktikan ini sepenuhnya jujur. Yang pasti java.util.Random#nextIntseragam, seperti yang dijelaskan dalam dokumen:

Mengembalikan pseudorandom berikutnya, intnilai terdistribusi seragam dari urutan generator nomor acak ini. Kontrak umum nextIntadalah bahwa satu intnilai dihasilkan dan dikembalikan secara acak. Semua 2 ³²int nilai yang mungkin dihasilkan dengan (kurang lebih) probabilitas yang sama.

Perbedaan antara nilai-nilai acak ini (diurutkan) sendiri tentu saja tidak seragam, tetapi set secara keseluruhan seragam. Sekali lagi, saya tidak yakin bagaimana membuktikan ini secara matematis, tetapi di sini ada skrip yang akan meletakkan 10,000set yang dihasilkan (untuk n=10) di Peta dengan penghitung , di mana sebagian besar set unik; beberapa diulang dua kali; dan kejadian berulang maksimum biasanya dalam kisaran [4,8].

Instruksi instalasi:

Karena Java adalah bahasa yang cukup terkenal dengan banyak informasi yang tersedia tentang cara membuat dan menjalankan kode Java, saya akan membuat ini singkat.
Semua alat yang digunakan dalam kode saya tersedia di Java 7 (mungkin bahkan sudah ada di Java 5 atau 6, tapi mari kita gunakan 7 untuk berjaga-jaga). Saya cukup yakin Java 7 sudah diarsipkan, jadi saya sarankan mengunduh Java 8 untuk menjalankan kode saya.

Pikiran tentang perbaikan:

Saya ingin mencari peningkatan untuk memeriksa nol dan memeriksa semua nilai unik. Saya dapat memeriksa 0sebelumnya, dengan memastikan nilai acak yang kita tambahkan ke array belum ada di dalamnya, tetapi itu akan berarti beberapa hal: array harus ArrayListjadi kita dapat menggunakan metode builtin .contains; loop sementara harus ditambahkan hingga kami menemukan nilai acak yang belum ada dalam Daftar. Karena memeriksa nol sekarang dilakukan .contains(0)pada Set (yang hanya diperiksa sekali), kemungkinan besar lebih baik untuk memeriksanya pada saat itu, dibandingkan dengan menambahkan loop dengan .containspada Daftar, yang akan diperiksa setidaknya nkali , tetapi kemungkinan besar lebih.

Adapun pemeriksaan keunikan, kami hanya memiliki njumlah bilangan bulat acak kami yang berjumlah n squaredsetelah langkah 1 program, jadi hanya dengan demikian kami dapat memeriksa apakah semuanya unik atau tidak. Dimungkinkan untuk menyimpan Daftar yang dapat diurutkan alih-alih array, dan memeriksa perbedaan di antara keduanya, tetapi saya benar-benar ragu itu akan meningkatkan kinerja daripada hanya memasukkannya ke dalam Setdan memeriksa apakah ukuran Set itu nsatu kali.

Mathematica n = 11

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