Как равномерно вставить меньшее количество в большее?

#алгоритм #математика

Как равномерно распределить меньшее количество элементов в большем их количестве?
То есть у меня есть два множества элементов:


  oooooooooo(10)
  ОООО(4)


Нужно объединить их так, чтобы они были равномерно распределены. Например вот так:


  ooОooОooОooОoo(14)


Разделение большего на меньшее даёт этот интервал. Почему это так и с чего начинается
поиск решения?
    

Ответы

Ответ 1

Алгоритм такой:  


Делим "большее" на "меньшее+1" с "остатком".  
Вставляем "частное" количество o
аккумулируем остатки, если сумма остатков переваливает единицу, добавляем лишнюю o
Вставляем O
Повторяем "меньшее" количество раз
Прицепляем хвост из "частного" количества o




let a = Math.random()*30+1;
let b = Math.random()*10+1;
[a, b] = [Math.min(a, b), Math.max(a, b)].map(x => Math.floor(x));
let [div, rem] = [Math.floor(b/(a+1)), b%(a+1)];

console.log('O'.repeat(a), a);
console.log('o'.repeat(b), b);

let res = '', acc = rem;
for (let i = 0; i < a; i++) {
  res += 'o'.repeat(div + +(acc>=a));
  res += 'O';
  acc = acc % a + rem;
}
res += 'o'.repeat(div);
console.log(res, res.length);


Ответ 2

разделить меньшее S на большее B, получится некий дробный коэффициент k < 1;
завести счётчик r, начав с 0;
вставлять B и к счётчику r добавлять дробный k;
как только в r набегает >= 1, надо уменьшить r на 1, и пора вставить элемент S;
так до тех пор, пока не вставим все положенные элементы B и S.


Интерактивная визуализация вставки:



var data=[],a,b;var svg=d3.select("body").append("div").append("svg").attr("width",160).attr("height",160);var
g=svg.append("g").attr("transform","translate(80,80)");var tr=d3.transition().duration(500).ease(d3.easeLinear);function
movescale(c){c.attr("cx",function(d){return 70*Math.cos(d.i*2*Math.PI/(a+b));}).attr("cy",function(d){return
70*Math.sin(d.i*2*Math.PI/(a+b));}).attr("r",d=>""+(d.big?9:7)+"px").attr("style",d=>"fill:"+(d.big?"#F90":"#333"));}
function getoff(e){e.attr("cx",0).attr("cy",0).attr("r",0)}
update();function update(){var i,circle,B,S;a=parseInt(document.getElementById("in-A").value);b=parseInt(document.getElementById("in-B").value);B=Math.max(a,b);S=Math.min(a,b);data=[];var
k=S/B,r=0;i=iB=iS=0;while(data.length=1){if(iSd.id);circle.exit().transition(tr).call(getoff).remove();circle.enter().append("circle").attr("r",0).transition(tr).call(movescale);circle.transition(tr).call(movescale);}
document.getElementById("in-A").addEventListener("input",update);document.getElementById("in-B").addEventListener("input",update);
circle {stroke:white}







Не минифицированный fiddle.


Ответ 3

Знаете, надо разделить большее количество на меньшее, получить некоторое число N,
а потом вставлять элементы из меньшего набора по одному в больший после каждых N элементов
этого набора. Деление проводить с округлением в меньшую сторону, т.е. в последней группе
у Вас может получиться не N, а меньше элементов. Тут уже смотрите Вашу задачу, что
сказано на этот счет. Ахах