Допустим такое целое число находится в диапазоне [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/
