Математически идеальный способ получения равномерной выборки «цепочки» элементов

Скажем, я хочу создать список чисел рекурсивно, случайно выбрав число от 0 до 9, а затем (необязательно) произвольно выбрать другое число между x + 1 и 9, где x - последнее число, которое было выбрано, и, необязательно, повторение этого процесса. Таким образом, вы можете получить списки, такие как 1,3,6, 3,4,8,9, 2,7 и так далее. Это упрощение того, что я действительно пытаюсь сделать.Математически идеальный способ получения равномерной выборки «цепочки» элементов

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

Это JavaScript с помощью случайной целого числа функции от Lo-Dash:

function randomlist(index) { 
    if (index > 8) return; 
    var range = _.random(9 - index); 
    var randex = [_.random(index, index + range)]; 
    if (_.random(10) < 6) randex = randex.concat(randomlist(randex[0] + 1)); 
    return randex 
} 

tally = [0,0,0,0,0,0,0,0,0,0] 
for (i=0;i<1000;i++) { 
    var list = randomlist(0); 
    list.forEach(function(x){tally[x]+=1}); 
}

Здесь, а не просто выбирать случайное число между й и 9 и первым выбрать случайный меньший диапазон, а затем выбрать случайное число внутри этого. Я думал, что это может сделать трюк, но когда я запускаю вышеуказанный код, tally заканчивается тем, что выглядит как [278, 262, 224, 189, 217, 180, 185, 179, 156, 61], явно предпочитая меньшие числа. И если я отрегулирую вероятность рекурсии, тогда баланс немного изменится. Я надеюсь, что может быть какая-то формула, которая позволяет настраивать вероятность рекурсии и позволяет создавать списки, которые равномерно проецируют все числа.

источник

2014-09-27 Moss

Вам не хватает того, что есть более крупные числа, чем маленькие, и поэтому функция случайного числа чаще всего выбирает большие? Возможно, вам стоит подумать обо всех ваших диапазонах чисел, имеющих одинаковое количество цифр - маленькие просто начинаются с 0, например 053 и 008. – vernonner3voltazim

Почему бы не выбрать расстояние между цифрами, а затем вычислить числа с помощью сканирования? По сканированию я имею в виду, что [2,4,1,5,2] становится [2,6,7,12,14]. –

Какое качество вы используете? Вы просто хотите получить однородное выборочное выборочное подмножество первых 10 чисел? Затем на каждом рекурсивном шаге либо берете конкретный элемент, либо нет. – osa

Из вашего описания есть только ограниченное количество «списков», которые соответствуют этому описанию. Итак, предположим, вы создаете массив, содержащий все из них, а затем просто произвольно выбираете что-то из массива? Здесь:

<!DOCTYPE html> 
<html> 
<head> 
    <meta charset="UTF-8" /> 
    <title>test-page</title> 
<script type="text/javascript"> 
//<!-- 

var lists, und, tmp, dv, pkd, i, q,r,s,t,u,v,w,x,y,z; 

function begin() 
{ lists=[]; 
    for(i=0,q=0; q<10; q++) 
    for(r=q+1;r<10;r++) 
    { lists[i++]=[q,r]; 
     for(s=r+1;s<10;s++) 
     { lists[i++]=[q,r,s]; 
     for(t=s+1;t<10;t++) 
     { lists[i++]=[q,r,s,t]; 
      for(u=t+1;u<10;u++) 
      { lists[i++]=[q,r,s,t,u]; 
      for(v=u+1;v<10;v++) 
      { lists[i++]=[q,r,s,t,u,v]; 
       for(w=v+1;w<10;w++) 
       { lists[i++]=[q,r,s,t,u,v,w]; 
       for(x=w+1;x<10;x++) 
       { lists[i++]=[q,r,s,t,u,v,w,x]; 
        for(y=x+1;y<10;y++) 
        { lists[i++]=[q,r,s,t,u,v,w,x,y]; 
        for(z=y+1;z<10;z++) 
         lists[i++]=[q,r,s,t,u,v,w,x,y,z]; 
    } } } } } } } } 
    for(j=0; j<i; j++) 
    { tmp=document.createElement("span"); 
    tmp.innerHTML=lists[j]+"<br />"; 
    document.body.appendChild(tmp); 
    } 
    tmp=document.createElement("span"); 
    tmp.innerHTML="<br />Total: " + i + " lists. <br />"; //1013 
    document.body.appendChild(tmp); 
    pkd=[]; 
    i=0; 
    dv=document.getElementById("pks"); 
    return; 
} 

function Pick() 
{ if(lists==und) 
    return; 
    q=Math.floor(Math.random()*1013); 
    for(r=0; r<i; r++) 
    if(pkd[r]==q) //check this array for previously-picked list 
     break; 
    if(r==i)   //not previously picked? 
    { pkd[i++]=q; //add to array 
    tmp=document.createElement("span"); 
    tmp.innerHTML=lists[q]+"<br />"; 
    dv.appendChild(tmp); //display this list 
    } 
    else 
    Pick(); //try again to pick an unpicked list 
    //DON'T click the button more than 1013 times! 
    return; 
} 

// --> 
</script> 
</head> 
<body> 
<input type="button" value="create lists" onclick="begin();" />&nbsp; &nbsp; 
<input type="button" value="random pick" onclick="Pick();" /><br /> 
<br /> 
<div id="pks"> 
</div> 
<br /> 
</body> 
</html>

источник

2014-09-27 12:20:58 vernonner3voltazim

Умный, и, конечно же, он производит совершенно четкую выборку. Единственная проблема заключается в том, что она имеет тенденцию создавать слишком много длинных списков. В моем описании я упомянул, что есть (регулируемый) процентный шанс для каждого нового номера, который будет добавлен в список, когда он будет повторяться. Поэтому, если вероятность равна 50%, тогда вы получите половину числа списков с двумя номерами, как 1-число и одну четверть, так и количество 3-х списков и так далее. – Moss

Но на самом деле я понял решение, похожее на то, с чем вы столкнулись. То есть, я могу создать отсортированный список в начале рекурсивного процесса, а затем поместить элементы из списка при каждой рекурсии. Потому что мне нужна рекурсия, но на самом деле эти цифры не должны генерироваться в середине рекурсии. Но я не осознавал этого, когда задавал вопрос. – Moss

Математически идеальный способ получения равномерной выборки «цепочки» элементов

ответ

Смежные вопросы