Нужна помощь в реализации алгоритма

[alexchipliev]

Нужно создать приложение (браузерное, или десктопное, c использованием Node.js - некритично), для генерации комбинаций 6 пар чисел, от 1 до 36, за вычетом исключений (заранее введенных, и сохраненных в базе), с выводом всех теоретически возможных вариантов, и так же с сохранением их в базе, для последующего выбора одного, или нескольких их них рандомным способом. Какую реализацию алгоритма вы бы посоветовали? Вариант на javascript с веб интерфейсом, не подвесит ли браузер во время вычислений?

[рони]

alexchipliev,
какая мелочь база на

alert(36*35*34*33*32*31)

вариантов

[Nodeveloper]

В базе достаточно хранить список игнорируемых исключений, и пользоваться функцией 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;
}