Для nзаданного целого числа вычислить набор nслучайных уникальных целых чисел в диапазоне 1..n^2(включительно) так, чтобы сумма набора была равнаn^2

Случайный, в этом случае, означает равномерно случайный между действительными выходами. Каждый действительный выход для данного nдолжен иметь единый шанс быть сгенерированным.

Например, n=3должны иметь 1/3 шансу каждый из вывода 6, 1, 2, 3, 5, 1или 4, 3, 2. Поскольку это набор, порядок не имеет значения, 4, 3, 2идентичен3, 2, 4

счет

Победителем является программа, которая может вычислить максимум nза 60 секунд.
Примечание. Для предотвращения возможного частичного жесткого кодирования все записи должны быть не более 4000 байтов.

тестирование

Весь код будет выполняться на моем локальном компьютере с Windows 10 (Razer Blade 15, 16 ГБ ОЗУ, 6-ядерный процессор Intel i7-8750H, 4,1 ГГц, GTX 1060 на случай злоупотребления графическим процессором), поэтому предоставьте подробные инструкции по запуску кода на моя машина.
По запросу записи могут быть запущены либо через Debian на WSL, либо на виртуальной машине Xubuntu (обе на той же машине, что и выше)

Работы будут проходить 50 раз подряд, итоговый результат будет в среднем из всех 50 результатов.

Ржавчина , n ≈ 1400

Как бегать

Сборка cargo build --releaseи запуск с target/release/arbitrary-randomness n.

Эта программа работает быстрее всего с большим количеством памяти (конечно, если она не обменивается). Вы можете настроить использование памяти, отредактировав MAX_BYTESконстанту, в настоящее время установленную на 8 ГиБ.

Как это работает

Множество строится с помощью последовательности двоичных решений (каждое число либо внутри, либо за пределами множества), каждая из вероятностей которых вычисляется комбинаторно путем подсчета числа возможных множеств, которые можно построить после каждого выбора с использованием динамического программирования.

Использование памяти для больших n уменьшается с помощью версии этой стратегии биномиального разбиения .

Cargo.toml

[package]
name = "arbitrary-randomness"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]

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

Попробуйте онлайн!

(Примечание: версия TIO имеет несколько модификаций. Во-первых, ограничение памяти сокращено до 1 ГиБ. Во-вторых, поскольку TIO не позволяет вам писать a Cargo.tomlи зависеть от внешних ящиков, например rand, я вместо этого извлек drand48из библиотеки C, используя FFI. Я не удосужился посеять его, поэтому версия TIO будет давать одинаковый результат при каждом запуске. Не используйте версию TIO для официального бенчмаркинга.)

Java 7+, n = 50 через ~ 30 секунд на 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;
      }
    }
  }
}

Версия без ответа моего ответа для кода-версии этой задачи на данный момент, только с одним незначительным изменением: java.util.Random#nextInt(limit)используется вместо (int)(Math.random()*limit)целого числа в диапазоне [0, n), поскольку это примерно в два раза быстрее .

Попробуйте онлайн.

Объяснение:

Используемый подход:

Код разбит на две части:

1. Создайте список nколичества случайных целых чисел, в которых n squared.
2. Затем он проверяет, все ли значения уникальны и не равны ли они нулю, и если любое из них ложно, он снова попытается выполнить шаг 1, промывая и повторяя, пока мы не получим результат.

Шаг 1 выполняется с помощью следующих подэтапов:

1) Создайте массив n-1количества случайных целых чисел в диапазоне [0, n squared). И добавить 0и n squaredв этот список. Это сделано в O(n+1)исполнении.
2) Затем он будет сортировать массив с помощью встроенного модуля. java.util.Arrays.sort(int[])Это будет сделано с точки зрения O(n*log(n))производительности, как указано в документации:

Сортирует указанный массив целых чисел по возрастанию. Алгоритм сортировки - это настроенная быстрая сортировка, адаптированная из работ Джона Л. Бентли и М. Дугласа Макилроя «Разработка функции сортировки», Software-Practice and Experience, Vol. 23 (11) P. 1249-1265 (November 1993). Этот алгоритм обеспечивает производительность n * log (n) для многих наборов данных, которые приводят к ухудшению других быстрых сортировок до квадратичной производительности.

3) Рассчитайте разницу между каждой парой. Этот результирующий список различий будет содержать nцелые числа, которые суммируются с n squared. Это сделано в O(n)исполнении.

Вот пример:

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

Таким образом, эти три шага выше довольно хороши для производительности, в отличие от шага 2 и цикла вокруг всего, что является основной грубой силой. Шаг 2 разделен на следующие подэтапы:

1) Список различий уже сохранен в java.util.Set. Он проверит, равен ли размер этого набора n. Если это так, это означает, что все случайные значения, которые мы сгенерировали, являются уникальными.
2) И он будет также проверить , что она не содержит 0в наборе, так как вызов просит случайные величины в диапазоне [1, X], где Xесть n squaredминус суммы [1, ..., n-1], как заявлено @Skidsdev в комментариях ниже.

Если любой из двух указанных выше вариантов (не все значения уникальны или присутствует ноль), он сгенерирует новый массив и снова установит его, сбросив на шаг 1. Это продолжается до тех пор, пока мы не получим результат. Из-за этого время может сильно отличаться. Я видел, как он закончился за 3 секунды один раз на TIO n=50, но также и за 55 секунд один раз n=50.

Доказательство единообразия:

Я не совсем уверен, как доказать это, чтобы быть полностью честным. Это java.util.Random#nextIntточно, как описано в документации:

Возвращает следующее псевдослучайное, равномерно распределенное intзначение из последовательности этого генератора случайных чисел. Общий контракт nextIntзаключается в том, что одно intзначение генерируется и возвращается псевдослучайно. Все 2 ³² возможных intзначения производятся с (приблизительно) равной вероятностью.

Различия между этими (отсортированными) случайными значениями, конечно, не являются одинаковыми, но наборы в целом являются однородными. Опять же, я не уверен, как это доказать математически, но вот сценарий, который поместит 10,000сгенерированные наборы (для n=10) в карту со счетчиком , где большинство наборов являются уникальными; некоторые повторяются дважды; и максимальное повторное вхождение обычно находится в диапазоне [4,8].

Инструкции по установке:

Поскольку Java является довольно известным языком с большим количеством информации о том, как создавать и запускать код Java, я буду кратким.
Все инструменты, используемые в моем коде, доступны в Java 7 (возможно, даже уже в Java 5 или 6, но давайте использовать 7 на всякий случай). Я почти уверен, что Java 7 уже заархивирована, поэтому я бы предложила загрузить Java 8 для запуска моего кода.

Мысли об улучшениях:

Я хотел бы найти улучшение для проверки на нули и проверить, что все значения уникальны. Я мог бы проверить это 0раньше, убедившись, что случайного значения, которое мы добавляем в массив, еще нет, но это будет означать пару вещей: массив должен быть таким, ArrayListчтобы мы могли использовать встроенный метод .contains; цикл while следует добавлять до тех пор, пока мы не найдем случайное значение, которого еще нет в списке. Поскольку проверка на ноль теперь выполняется с .contains(0)помощью набора (который проверяется только один раз), для производительности, скорее всего, лучше проверить его в этот момент, чем для добавления цикла с .containsв список, который будет проверяться как минимум nраз , но скорее всего больше.

Что касается проверки уникальности, у нас есть только nколичество случайных целых чисел, которое суммируется n squaredпосле шага 1 программы, поэтому только тогда мы можем проверить, все ли уникальны или нет. Может быть возможно сохранить сортируемый список вместо массива и проверить различия между ними, но я серьезно сомневаюсь, что это улучшит производительность, чем просто помещает их в a Setи проверяет, не равен ли размер этого набора nодин раз.

Mathematica n = 11

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