Нужна помощь в реализации алгоритма
Нужно создать приложение (браузерное, или десктопное, c использованием Node.js - некритично), для генерации комбинаций 6 пар чисел, от 1 до 36, за вычетом исключений (заранее введенных, и сохраненных в базе), с выводом всех теоретически возможных вариантов, и так же с сохранением их в базе, для последующего выбора одного, или нескольких их них рандомным способом. Какую реализацию алгоритма вы бы посоветовали? Вариант на javascript с веб интерфейсом, не подвесит ли браузер во время вычислений?
|
alexchipliev,
какая мелочь база на alert(36*35*34*33*32*31) вариантов |
В базе достаточно хранить список игнорируемых исключений, и пользоваться функцией getRandomRangeWithoutIgnored с передачей ей параметра ignored, который имеет следующий формат:
ignored = {};
ignored[ generate() ] = 1;
Т.е. ключ — это результат функции generate, а значение может быть любым, кроме false, null, undefined, 0, и прочих типов, которые приводятся к false. Первый аргумент функции getRandomRangeWithoutIgnored — это количество элементов в результирующем массиве (т.е. количество шестерок пар чисел от 1 до 36), которое гарантированно вернет функция. Если количество элементов настолько велико, что встает ограничение по памяти на вашем сервере, то можно использовать фильр блума для определения, входит ли генерируемая шестерка пар в список игнорируемых. Также, в текущей реализации используется не очень хороший генератор случайных чисел. В реальной обстановке следует использовать честный генератор случайных чисел.
function pair (offset) {
var a = Math.floor(offset / 36) % 36,
b = Math.floor(offset % 36);
return [a+1,b+1];
}
function generate (seed) {
var seed = typeof seed === 'number' && seed >= 0 ? seed : 0,
pairs = [];
while (pairs.length < 6) {
pairs[pairs.length] = pair(seed++);
}
return pairs;
}
function getRange (seed, count) {
var seed = typeof seed === 'number' && seed >= 0 ? seed : 0,
count = typeof count === 'number' && count > 0 ? count : 1,
ret = [];
while (count--) {
var generated = generate(seed);
ret[ret.length] = generated;
seed += generated.length;
}
return ret;
}
function getRangeRandom (count) {
var count = typeof count === 'number' && count > 0 ? count : 1,
ret = [],
seed;
while (count--) {
seed = Math.round(Math.random()*36*35*34*33*32*31); // thk @рони
ret[ret.length] = generate(seed);
}
return ret;
}
function getRandomRangeWithoutIgnored (count, ignored) {
var count = typeof count === 'number' && count > 0 ? count : 1,
ignored = typeof ignored === 'object' && Object.prototype.toString.call(ignored) !== '[object Array]' ? ignored : null,
ret = [];
if (ignored == null) {
return getRangeRandom (count);
}
while (ret.length < count) {
var range = getRangeRandom (count);
for (var i=0, l=range.length; i<l; i++) {
if (!ignored[range[i]]) {
ret[ret.length] = range[i];
}
}
}
return ret;
}
|
| Часовой пояс GMT +3, время: 04:21. |