Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #11 (permalink)  
Старый 10.11.2017, 08:53
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,064

Сообщение от ruslan_mart
рони, если вдруг передашь сначала max, а потом - min.
getUniqueRandomInt(18,2) ???
для чисел нужна функция в сортировке!!!
Ответить с цитированием
  #12 (permalink)  
Старый 10.11.2017, 09:21
Аватар для ruslan_mart
Профессор
Отправить личное сообщение для ruslan_mart Посмотреть профиль Найти все сообщения от ruslan_mart
 
Регистрация: 30.04.2012
Сообщений: 3,018

рони, блин, да, точно, упустил этот момент.
Ответить с цитированием
  #13 (permalink)  
Старый 10.11.2017, 10:17
Аватар для ruslan_mart
Профессор
Отправить личное сообщение для ruslan_mart Посмотреть профиль Найти все сообщения от ruslan_mart
 
Регистрация: 30.04.2012
Сообщений: 3,018

var UniqueNumber = (function() {
	'use strict';

	var DEFAULT_MAX = Number.MAX_VALUE;
	var DEFAULT_MIN = 0;

	function getRandomInt(min, max) {
		return Math.floor(Math.random() * (max - min + 1)) + min;
	}

	function sortCallback(a, b) {
		return a - b;
	}

	function UniqueNumber() {
		var range = Array.prototype.slice.call(arguments).sort(sortCallback);

		if(range.length < 2) {
			range.unshift(DEFAULT_MIN);

			if(range.length < 2) {
				range.push(DEFAULT_MAX);
			}
		}

		this._cache = [];
		this._range = range;
	}

	UniqueNumber.prototype = {
		get: function() {
			var cache = this._cache,
				range = this._range,
				length = range[1] - range[0] + 1,
				value;

			while(cache.length !== length) {
				value = getRandomInt.apply(null, range);

				if(cache.indexOf(value) === -1) {
					cache.push(value);
					return value;
				}
			}

			return NaN;
		}
	};

	return UniqueNumber;
})();


var uniqInt = new UniqueNumber(1, 5);

console.log(uniqInt.get());
console.log(uniqInt.get());
console.log(uniqInt.get());
console.log(uniqInt.get());
console.log(uniqInt.get());
console.log(uniqInt.get()); //NaN

Последний раз редактировалось ruslan_mart, 10.11.2017 в 11:43.
Ответить с цитированием
  #14 (permalink)  
Старый 10.11.2017, 11:10
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,064

Сообщение от ruslan_mart
return a > b;
почему не a - b ?
Ответить с цитированием
  #15 (permalink)  
Старый 10.11.2017, 11:24
Профессор
Отправить личное сообщение для Dilettante_Pro Посмотреть профиль Найти все сообщения от Dilettante_Pro
 
Регистрация: 27.11.2015
Сообщений: 2,899

Еще есть WebCryptoAPI/

var random = new Uint16Array(20);
window.crypto.getRandomValues(random);
alert(JSON.stringify(random));
Ответить с цитированием
  #16 (permalink)  
Старый 10.11.2017, 11:44
Аватар для ruslan_mart
Профессор
Отправить личное сообщение для ruslan_mart Посмотреть профиль Найти все сообщения от ruslan_mart
 
Регистрация: 30.04.2012
Сообщений: 3,018

рони, зануда
Ответить с цитированием
  #17 (permalink)  
Старый 10.11.2017, 12:46
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 1,004

допилил скрипт, чтобы рандом всегда только один раз вызывался
https://jsfiddle.net/yzj5omfz/

нафига? да просто из любопытства
Ответить с цитированием
  #18 (permalink)  
Старый 10.11.2017, 16:44
Аватар для Malleys
Профессор
Отправить личное сообщение для Malleys Посмотреть профиль Найти все сообщения от Malleys
 
Регистрация: 20.12.2009
Сообщений: 1,714

Допустим такое целое число находится в диапазоне [1, n]. Основной проблемой тут является проверка — поиск, было ли число уже сгенерировано — сложность алгоритма O(n), его конечно можно уменьшить до O(1), используя вместо массивов объект или множество, однако решение ресурсоёмкое по памяти при больших n.

В качестве решения предлагаю рассмотреть последовательность чисел, которая имеет минимальную длину n до начала её повторения. Идея заключается в том, чтобы получить все числа диапазона [1, n] в псевдо-случайном порядке, начиная с любого числа из того же диапазона.

Получается при помощи регистра сдвига с линейной обратной связью(LFSR). Побайтовые операции в JavaScript позволяют работать с числами до 2^31 - 1. Давайте попробуем написать алгоритм LFSR (конфигурация Фиббоначи, коеффиценты взяты отсюда http://courses.cse.tamu.edu/walker/c...lfsr_table.pdf ) для чисел не больше 2^31 - 1 — например для диапазона [1, 2^25 - 1]

<!doctype html>
<html>
<head>
	<meta charset="utf-8">
	<style>
		button {
			--theme: #f06;
			background-color: white;
			color: var(--theme);
			border: 2px solid var(--theme);
			padding: 1em;
			border-radius: 0.25em;
			font: bold 1.25em Helvetica, sans-serif;
			transition: 400ms;
		}
		button:hover {
			box-shadow: inset 0 0 0 3em var(--theme);
			color: white;
		}
		#list {
			display: flex;
			font: 1em Helvetica, sans-serif;
			flex-direction: column-reverse;
			counter-reset: generated-number 0;
		}

		#list span {
			display: flex;
			counter-increment: generated-number 1;
			padding: 1em;
			border: 1px solid #eee;
			border-radius: 5px;
			margin: 0.5em 0;
			word-break: break-all;
		}

		span::before {
			content: counter(generated-number) ". ";
			padding: 0 1em;
			word-break: normal;
		}
	</style>
</head>
<body>
	<button>Сгенерировать следующее число</button>
	<div id="list"></div>
	<script>

		function getNonRepeatingNumberIterator() {
			const INITIAL_NUMBER = 1 + (Math.pow(2, 25) - 1) * Math.random() | 0;
			console.log(INITIAL_NUMBER);
			let s = getNextNumber(INITIAL_NUMBER);

			function getNextNumber(s) {
				// x^25 + x^22 + 1 = 0
				return ((((s >> 0) ^ (s >> 3)) & 1) << 24) | (s >> 1);
			}

			return {
				next: function() {
					// когда дойдём до первого числа, то мы перебрали все числа
					if(s === INITIAL_NUMBER) return {
						value: null,
						done: true
					};

					s = getNextNumber(s);

					return {
						value: s,
						done: false
					};
				}
			};
		}

		// использование
		let iterator = getNonRepeatingNumberIterator();
		let iteratorStep;
		let list = document.getElementById("list");

		document.querySelector("button").addEventListener("click", event => {
			iteratorStep = iterator.next();
			if(iteratorStep.done) return;

			let span = document.createElement("span");
			span.textContent = iteratorStep.value;

			list.appendChild(span);
		});
		
	</script>
</body>
</html>


Функции объекта Math позволяют работать с целыми числами до 2^53 - 1 (этому числу равна константа Number.MAX_SAFE_INTEGER, например Number.MAX_SAFE_INTEGER / 3 вычисляется с точностью до двух десятых). Тот же самый алгоритм для чисел не больше 2^50 - 1 — например для диапазона [1, 2^41 - 1]

<!doctype html>
<html>
<head>
	<meta charset="utf-8">
	<style>
		button {
			--theme: #f06;
			background-color: white;
			color: var(--theme);
			border: 2px solid var(--theme);
			padding: 1em;
			border-radius: 0.25em;
			font: bold 1.25em Helvetica, sans-serif;
			transition: 400ms;
		}
		button:hover {
			box-shadow: inset 0 0 0 3em var(--theme);
			color: white;
		}
		#list {
			display: flex;
			font: 1em Helvetica, sans-serif;
			flex-direction: column-reverse;
			counter-reset: generated-number 0;
		}

		#list span {
			display: flex;
			counter-increment: generated-number 1;
			padding: 1em;
			border: 1px solid #eee;
			border-radius: 5px;
			margin: 0.5em 0;
			word-break: break-all;
		}

		span::before {
			content: counter(generated-number) ". ";
			padding: 0 1em;
			word-break: normal;
		}
	</style>
</head>
<body>
	<button>Сгенерировать следующее число</button>
	<div id="list"></div>
	<script>

		function getNonRepeatingNumberIterator() {
			const INITIAL_NUMBER = Math.floor(1 + (Math.pow(2, 41) - 1) * Math.random());

			let s = getNextNumber(INITIAL_NUMBER);


			function getNextNumber(s) {
				// x^41 + x^38 + 1 = 0
				// может ли тут при делении на 8 получиться дробная часть 0.99999...? Да!
				// return ((s + Math.floor(s / 8)) % 2) * Math.pow(2, 40) + Math.floor(s / 2);
				return ((s + Math.round(s / 8 + .499)) % 2) * Math.pow(2, 40) + Math.round(s / 2 + 0.499);

				// Хотя прибавлять можно было бы не .499, а 0.5 - 1/16 и 0.5 - 1/4 соответственно,
				// но на диапазоне [1, 2^50 - 1] ошибки округления доходят только до тысячных

				return s;
			}

			return {
				next: function() {
					if(s === INITIAL_NUMBER) return {
						value: null,
						done: true
					};

					s = getNextNumber(s);

					return {
						value: s,
						done: false
					};
				}
			};
		}

		// использование
		let iterator = getNonRepeatingNumberIterator();
		let iteratorStep;
		let list = document.getElementById("list");

		document.querySelector("button").addEventListener("click", event => {
			iteratorStep = iterator.next();
			if(iteratorStep.done) return;

			let span = document.createElement("span");
			span.textContent = iteratorStep.value;
			list.appendChild(span);
		});
		
	</script>
</body>
</html>


Сообщение от ruslan_mart
Я тут получше решение придумал
Когда ваш скрипт генерирует числа в диапазоне по умолчанию [0, ~10^308], то он генерирует так, что во много раз больше чисел пропускает, чем выдает — он генерирует числа с шагом в ~10^291, так что вместо желанных ~10^308, мы получим только ~10^18 (или более точно — только 9218868437227405312 чисел)

Ну и напоследок немного погенерируем случайные числа без повторении в диапазоне [0, 2^1024 - 1] — JavaScript позволяет работать только с 16 значащими цифрами в числе, нам же потребуется 309 (и далее ещё для одного примера 1234) значащих цифр. Пусть каждая значащая цифра числа представленного в двоичной системе счисления (биты) будет храниться в массиве. Тот же самый алгоритм для чисел не больше 2^4096 - 1 (на самом деле можно и больше, просто не известны коеффиценты для генерации, кто знает напишите) — например для диапазона [1, 2^1024 - 1]

<!doctype html>
<html>
<head>
	<meta charset="utf-8">
	<style>
		button {
			--theme: #f06;
			background-color: white;
			color: var(--theme);
			border: 2px solid var(--theme);
			padding: 1em;
			border-radius: 0.25em;
			font: bold 1.25em Helvetica, sans-serif;
			transition: 400ms;
		}
		button:hover {
			box-shadow: inset 0 0 0 3em var(--theme);
			color: white;
		}
		#list {
			display: flex;
			font: 1em Helvetica, sans-serif;
			flex-direction: column-reverse;
			counter-reset: generated-number 0;
		}

		#list span {
			display: flex;
			counter-increment: generated-number 1;
			padding: 1em;
			border: 1px solid #eee;
			border-radius: 5px;
			margin: 0.5em 0;
			word-break: break-all;
		}

		span::before {
			content: counter(generated-number) ". ";
			padding: 0 1em;
			word-break: normal;
		}
	</style>
</head>
<body>
	<button>Сгенерировать следующее число</button>
	<div id="list"></div>
	<script src="https://unpkg.com/bignumber.js@4.1.0/bignumber.js"></script>
	<script>

		BigNumber.config({ EXPONENTIAL_AT: [0, 1300] });

		function getNonRepeatingNumberIterator() {
			const INITIAL_NUMBER = new Uint8Array(1024);
			INITIAL_NUMBER.forEach((v, i, a) => a[i] = 2 * Math.random());

			console.log(INITIAL_NUMBER);

			let s = getNextNumber(INITIAL_NUMBER);


			function getNextNumber(s) {var base = 2;
				// x^1024 + x^1015 + x^1002 + x^1001 + 1
				let feedback = s[1024] ^ s[1015] ^ s[1002] ^ s[1001];

				s.copyWithin(1, 0);
				s[0] = feedback;

				return s;
			}

			return {
				next: function() {
					// Даже если генерировать со скоростью 10^6 в секунду,
					// потребуется около ~10^295 лет
					// т. е. во много раз больше многих миллионов и
					// миллиардов лет, прежде чем тут снова появится
					// число INITIAL_NUMBER, так что можно и не проверять.
					// Хотя это пвевдо-случайная последовательность чисел,
					// Math.random() каждое своё ~10^17 значение за тоже самое время
					// успеет выдать ~10^291 раз, так что эта
					// последовательность является более «случайной»

					// if(s.toString() === INITIAL_NUMBER.toString()) return {
					// 	value: null,
					// 	done: true
					// };

					s = getNextNumber(s);

					return {
						value: s,
						done: false
					};
				}
			};
		}

		// использование
		let iterator = getNonRepeatingNumberIterator();
		let iteratorStep;
		let list = document.getElementById("list");

		document.querySelector("button").addEventListener("click", event => {
			iteratorStep = iterator.next();
			if(iteratorStep.done) return;

			let span = document.createElement("span");
			// Здесь я использовал библиотеку bignumber.js — для генерации она не нужна
			// только для того чтобы перевести число из двоичной системы в десятичную
			span.textContent = new BigNumber(iteratorStep.value.join(""), 2).toString();
			list.appendChild(span);
		});
		
	</script>
</body>
</html>


И ещё набор неповторяемых — на протяжении многих лет — целых чисел в диапазоне [1, 2^4096 - 1] https://jsfiddle.net/xdjt8ufs/
Ответить с цитированием
  #19 (permalink)  
Старый 10.11.2017, 17:09
Профессор
Отправить личное сообщение для Nexus Посмотреть профиль Найти все сообщения от Nexus
 
Регистрация: 04.12.2012
Сообщений: 3,706

Чем плох вариант с использованием unix time + pseudo random?
Ответить с цитированием
  #20 (permalink)  
Старый 10.11.2017, 18:07
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 1,004

Nexus,
ничем не плох, возможно, именно этим автор и воспользовался он ведь свалил из топика на 5 посте, дальше тема живет сама собой
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Скрипт версии для слабовидящих yotobo Общие вопросы Javascript 0 02.04.2017 21:23
нужна помощь (есть работа) Редирект скрипт для iOS 9+ Возможно на AngularJS dimazap Мобильный JavaScript 1 20.01.2017 18:46
Где найти скрипт - Социальный Замок для html ? klimentino Общие вопросы Javascript 1 25.10.2013 06:39
скрипт для браузерки ванка Общие вопросы Javascript 11 11.10.2013 12:20
поиск классов внутри тега yozuul jQuery 24 14.06.2013 22:00