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:
- Wygeneruj listę
nlosowych liczb całkowitych, które sumują się n squared.
- 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 32 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.