Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #21 (permalink)  
Старый 29.07.2012, 01:28
Аватар для Aetae
Тлен
Отправить личное сообщение для Aetae Посмотреть профиль Найти все сообщения от Aetae
 
Регистрация: 02.01.2010
Сообщений: 6,480

Сообщение от oneguy Посмотреть сообщение
SplitNum(1, 3, 0) выдаёт [0, 1, 0] в 2 раза чаще, чем каждую из остальных 2 возможностей.
Вы запутались со смыслом функции. Нигде не оговорено, что порядок выходных значений тоже должен быть рандомизирован. В данном случае всегда получается 0,0,1 и не важно в каклм порядке.)
__________________
29375, 35
Ответить с цитированием
  #22 (permalink)  
Старый 29.07.2012, 02:30
Аватар для Дзен-трансгуманист
√₋̅₁̅
Отправить личное сообщение для Дзен-трансгуманист Посмотреть профиль Найти все сообщения от Дзен-трансгуманист
 
Регистрация: 18.06.2012
Сообщений: 385

oneguy,
Я понял, у меня вся фигня в том, что:

points[0, 0] приводит к result[0, 0, 1] (вероятность 25%)
points[1, 1] приводит к result[1, 0, 0] (вероятность 25%)
points[0, 1] и points[1, 0] одинаково приводят к result[0, 1, 0] (вероятность 50%)

function SplitNum (sum, summands, min) {

  if (summands < 1 || summands * min > sum) { return []; }
  var i, range = sum - summands * min, points = [], result = [];
  for (i=0; i<summands-1; i++) { points[i] = Math.floor(Math.random() * (range + 1)); }
  points.push(0, range);
  points.sort(function (a, b) { return a - b; });
  for (i=0; i<summands; i++) { result[i] = points[i+1] - points[i] + min; }
  return result;
}

function testDistribution (range, iterations) {

  var i, counter = [];
  for (i=0; i<range; i++) { counter[i] = 0; }
  for (i=0; i<iterations; i++) { counter[SplitNum(1, range, 0).indexOf(1)]++; }
  return counter;
}

alert(testDistribution(10, 10000));
В идеале распределение должно быть линейным, то есть все числа должны быть близки к 1000, но здесь явно имеем отклонение, близкое к среднеквадратическому.

Тогда просто перемешаем результат перед возвратом:
function SplitNum (sum, summands, min) {

  if (summands < 1 || summands * min > sum) { return []; }
  var i, range = sum - summands * min, points = [], result = [];
  for (i=0; i<summands-1; i++) { points[i] = Math.floor(Math.random() * (range + 1)); }
  points.push(0, range);
  points.sort(function (a, b) { return a - b; });
  for (i=0; i<summands; i++) { result[i] = points[i+1] - points[i] + min; }

  for (i=0; i<summands-1; i++) { // перемешиваем порядок слагаемых
    var j = Math.floor(Math.random() * (summands - i)) + i; // генерируем j в диапазоне [i; summands-1]
    var swap = result[i]; result[i] = result[j]; result[j] = swap; // меняем местами значения по индексам i и j
  }
  return result;
}

function testDistribution (range, iterations) {

  var i, counter = [];
  for (i=0; i<range; i++) { counter[i] = 0; }
  for (i=0; i<iterations; i++) { counter[SplitNum(1, range, 0).indexOf(1)]++; }
  return counter;
}

alert(testDistribution(10, 10000));
Теперь всё в порядке.

Aetae,
Думаю, что oneguy все-таки прав, потому что если при значительном количестве генераций будет наблюдаться нарушение закона больших чисел, то в зависимости от прикладной задачи это может быть не очень-то и хорошо.
__________________

Гейзенберг, возможно, читал этот тред.
Ответить с цитированием
  #23 (permalink)  
Старый 29.07.2012, 03:05
Профессор
Отправить личное сообщение для oneguy Посмотреть профиль Найти все сообщения от oneguy
 
Регистрация: 31.05.2012
Сообщений: 396

Сообщение от Aetae
Нигде не оговорено, что порядок выходных значений тоже должен быть рандомизирован
Если я правильно понял задачу, то случайно выбирается упорядоченный набор чисел. Автор вналаче ведь привёл пример, где выходной массив не был упорядочен по возрастанию или убыванию.
Сообщение от Дзен-трансгуманист
Теперь всё в порядке.
Не в порядке. Возьмите SplitNum(2, 3, 0):
function SplitNum (sum, summands, min) {
 
  if (summands < 1 || summands * min > sum) { return []; }
  var i, range = sum - summands * min, points = [], result = [];
  for (i=0; i<summands-1; i++) { points[i] = Math.floor(Math.random() * (range + 1)); }
  points.push(0, range);
  points.sort(function (a, b) { return a - b; });
  for (i=0; i<summands; i++) { result[i] = points[i+1] - points[i] + min; }
 
  for (i=0; i<summands-1; i++) { // перемешиваем порядок слагаемых
    var j = Math.floor(Math.random() * (summands - i)) + i; // генерируем j в диапазоне [i; summands-1]
    var swap = result[i]; result[i] = result[j]; result[j] = swap; // меняем местами значения по индексам i и j
  }
  return result;
}
 
function testDistribution (iterations) {
 
  var i, counter = [];
  for (i=0; i<6; i++) { counter[i] = 0; }
  for (i=0; i<iterations; i++) {
    var r=SplitNum(2, 3, 0);
    counter[r.indexOf(2)==-1?r.indexOf(0)+3:r.indexOf(2)]++;
  }
  return counter;
}
 
alert(testDistribution(27000));

Есть 6 вариантов: [0, 0, 2], [0, 2, 0], [2, 0, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0]. Первые 3 выпадают с вероятностью 4/27, остальные - 5/27.

Последний раз редактировалось oneguy, 29.07.2012 в 03:10.
Ответить с цитированием
  #24 (permalink)  
Старый 29.07.2012, 04:16
Профессор
Отправить личное сообщение для oneguy Посмотреть профиль Найти все сообщения от oneguy
 
Регистрация: 31.05.2012
Сообщений: 396

Сообщение от Maxmaxmахimus
А числа целые нужны или дробные)?
Целые.
Ответить с цитированием
  #25 (permalink)  
Старый 29.07.2012, 05:03
Аватар для Дзен-трансгуманист
√₋̅₁̅
Отправить личное сообщение для Дзен-трансгуманист Посмотреть профиль Найти все сообщения от Дзен-трансгуманист
 
Регистрация: 18.06.2012
Сообщений: 385

Сообщение от oneguy
Есть 6 вариантов: [0, 0, 2], [0, 2, 0], [2, 0, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0]. Первые 3 выпадают с вероятностью 4/27, остальные - 5/27.

0002 x1 : 002
0012 x2 : 011
0022 x2 : 002
0112 x1 : 011
0122 x2 : 011
0222 x1 : 002

002 : 1+2+1 = 4x
011 : 2+1+2 = 5x

Да, всё верно. Это естественное распределение, так и должно быть.

function divide(a, n, m) {
  if (n*m>a)
    return;
  var b=[], d=[], p=a-(m-1)*n-1;
  for (var i=0; i<p; i++)
    b[i]=i;
  for (; i>a-m*n; i--) {
    var c=Math.floor(Math.random()*i);
    d.push(b[c]);
    b[c]=b[i-1];
  }
  d.sort(function (x, y) {
    return x-y;
  });
  d.push(p);
  b.length=0;
  b[0]=d[0]+m;
  for (i=0; i<n-1; i++)
    b.push(d[i+1]-d[i]+m-1);
  return b;
}

var time1 = (new Date()).getTime();
divide(10000000, 3, 0);
var time2 = (new Date()).getTime();
alert(((time2-time1)/1000).toFixed(3) + " sec.");
Ой, даааа... Не завидую тому, кто миллиард туда влепит... Так что ваше решение тоже пока не идеально.
__________________

Гейзенберг, возможно, читал этот тред.

Последний раз редактировалось Дзен-трансгуманист, 29.07.2012 в 05:45.
Ответить с цитированием
  #26 (permalink)  
Старый 29.07.2012, 08:53
Аватар для Aetae
Тлен
Отправить личное сообщение для Aetae Посмотреть профиль Найти все сообщения от Aetae
 
Регистрация: 02.01.2010
Сообщений: 6,480

Длинноник, не вижу рандома вообще.
function RandomSplit( A, parts, min ) {
    var numbers = [];
 
    for ( var i = 0; i < parts; i++ ) {
        var part = ( A / (parts - i) - min) * Math.random() + min;
        part = Math.round( part );
        numbers[i] = part;
        A = A - part;
    }
 
    for ( var i = 0; i < numbers.length; i++ )
        numbers[i] += A / parts;
 
    return numbers;
}
      
var counter = [0, 0, 0];

for (var i=0; i<10000; i++) {
  counter[RandomSplit(1, 3, 0).indexOf(1)]++;
}
 
alert(counter);
__________________
29375, 35
Ответить с цитированием
  #27 (permalink)  
Старый 29.07.2012, 10:16
sinistral
Посмотреть профиль Найти все сообщения от melky
 
Регистрация: 28.03.2011
Сообщений: 5,418

Сообщение от Maxmaxmахimus
false
таки да, рандом там был, но он находился в функции проверки числа на простоту.
Ответить с цитированием
  #28 (permalink)  
Старый 29.07.2012, 11:06
Аватар для Dim@
Профессор
Отправить личное сообщение для Dim@ Посмотреть профиль Найти все сообщения от Dim@
 
Регистрация: 21.04.2012
Сообщений: 951

oneguy,
Сообщение от oneguy
Вообще-то я не очень хороший комментатор кода, но я добавил один комментарий комментарии, так более понятно?
Да.
melky,
Сообщение от melky
что ?)
Цитирую
Сообщение от melky
как ни создашь тему - она начинает надрываться от вариантов решения проблемы, причём каждая тема, как и каждый ответ в ней, уникальны по причине уникальности человеческого мышления (идей).
Ответить с цитированием
  #29 (permalink)  
Старый 29.07.2012, 12:45
Профессор
Отправить личное сообщение для oneguy Посмотреть профиль Найти все сообщения от oneguy
 
Регистрация: 31.05.2012
Сообщений: 396

Сообщение от Дзен-трансгуманист
Да, всё верно. Это естественное распределение, так и должно быть.
Не нужно подгонять распределение под ваше решение В задаче нужно сделать, чтоб каждая возможность выпадала с одинаковой вероятностью, в данном случае 1/6. Результат [0, 0, 1] является одной возможностью, это в вашем решении он получается 2-мя способами.
Рассуджая таким же образом, можно было оправдать в SplitNum(1, 3, 0) распределение (1/4, 1/2, 1/4), хотя должно быть (1/3, 1/3, 1/3).

Последний раз редактировалось oneguy, 29.07.2012 в 12:47.
Ответить с цитированием
  #30 (permalink)  
Старый 29.07.2012, 14:00
Профессор
Отправить личное сообщение для oneguy Посмотреть профиль Найти все сообщения от oneguy
 
Регистрация: 31.05.2012
Сообщений: 396

Я написал ещё один алгоритм для первой части функции - составления массива d. Первый алгоритм больше подходит для больших n/p, второй - для маленьких. В функцию добавился 4-ый необязательный параметр - номер алгоритма. Если он отсутствует - алгоритм выбирается автоматически.
function divide(a, n, m, alg) {
  if (n*m>a)
    return;
  var b=[], d=[], p=a-(m-1)*n-1;
  if (alg==1||alg!=2&&20*n>p) {
// алгоритм 1
    for (var i=0; i<p; i++)
      b[i]=i; // делаем массив b из чисел 0, 1, ..., p-1
    while (i>p-n+1) {
      var c=Math.floor(Math.random()*i); // выбираем случайный элемент из b
      d.push(b[c]);
      b[c]=b[--i]; // удаляем его, считаем, что длина массива b теперь i
    }
    d.sort(function (x, y) {
      return x-y;
    });
  } else {
// алгоритм 2
    for (i=0; i<n-1; i++) {
      c=Math.floor(Math.random()*(p-i));
      var x=0, y=i;
      while (x<y) {
        var t=Math.floor((x+y)/2);
        if (d[t]-t>c)
          y=t;
        else x=t+1;
      }
      d.splice(x, 0, c+x);
    }  
  }
// конец алгоритма
  d.push(p); // после этой инструкции массив d будет содержать n различных неотрицательных чисел, отсортированных по возрастанию, последнее из которых p. С помощью этого массива формируется выходной массив, для которого будем использовать переменную b заново
  b.length=0;
  b[0]=d[0]+m;
  for (i=0; i<n-1; i++)
    b.push(d[i+1]-d[i]+m-1);
  return b;
}
//тесты
alert(divide(130, 3, 20)+"\n"+
  divide(100, 4, 25)+"\n"+
  //divide(2000, 1000, 0)+"\n"+
  //divide(100500, 100000, 0)+"\n"+
  divide(1000000000, 3, 0)+"\n");

Последний раз редактировалось oneguy, 29.07.2012 в 21:00.
Ответить с цитированием
Ответ



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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите написать JavaScript ! Alamogoro Общие вопросы Javascript 4 24.05.2012 19:11
Помогите написать скрипт !!! Zander Элементы интерфейса 10 19.01.2012 14:40
Помогите плисс написать скрипт Gnusmus Events/DOM/Window 6 17.08.2011 15:51
Генератор случайных чисел. Помогите написать. Teenager Я не знаю javascript 5 05.01.2011 19:15
помогите написать аналог строки include("index.php?open=1") на js bushstas Общие вопросы Javascript 1 19.07.2009 02:48