Формируем наборы из объектов, относящихся к разным категориям
Часто бывает нужно "раскидать" объекты, относящиеся к некоторым категориям, по наборам фиксированного размера, причём число объектов в каждой категории может быть различным, а повторов разных категорий в одном наборе следует избегать.
Не очень понятно? Тогда на простом примере. Скажем, по 5 учебным темам (категориям) есть по 5,6,8,6 и 5 задач соответственно, а в билете (наборе) должно быть по 2 задачи. Мы хотим распределить темы задач по билетам, по возможности избегая повторов в одном билете задач из одной темы.
Разумеется, исходные данные должны быть "разумными", например, при наличии 99 задач по теме 1 и 1 задачи по теме 2 избежать этих повторов не удастся никак. Но скрипт должен нормально себя вести и в этом случае, не выдавая сообщений об ошибках.
Другой пример - мы имеем 8 зайцев, 5 кукол, 3 машинки, 7 шариков и мишку, которых хотим быстро "раскидать" в подарочные комплекты по 3 игрушки в каждом. Ну и т.д., принцип, надеюсь, понятен.
В принципе, для небольшого числа объектов такое распределение несложно сделать и вручную, но зачем тогда компьютер? :) Мне проще и быстрее написать скрипт.
Пользоваться скриптом легко, в поле ввода "Объектов в категориях 1,2,..." задайте список натуральных чисел, разделённых пробелом, например, для нашего первого примера это 5 6 8 6 5 - количество категорий, равное пяти, по этому списку скрипт вычислит сам. Для второго примера числа были бы 8 5 3 7 1. В поле "Распределить по" укажите, по сколько объектов разных категорий должно быть в наборе (также натуральное число, в первом примере 2, во втором 3).
Скрипт сформирует наборы чисел, показывающих, к какой категории относятся объекты в них, для первого примера выйдет:
(1,3) (1,3) (1,3) (1,3) (1,4) (2,4) (2,4) (2,4) (2,4) (2,4) (2,5) (3,5) (3,5) (3,5) (3,5) Всего объектов: 30 Распределено наборов: 15
Как видим, здесь ровно пять единиц, шесть двоек и т.д.
Если данные "некруглые", например, задач всего 29 (числа 5 6 8 6 4 в первом поле ввода), а мы хотим 15 билетов, об этом также будет сообщено:
(1,3) (1,3) (1,3) (1,3) (1,4) (2,4) (2,4) (2,4) (2,4) (2,4) (2,5) (3,5) (3,5) (3,5) (3,-) Всего объектов: 29 Распределено наборов: 15 Осталось пустых мест: 1
В первое поле можно вводить числа от 1 до 99 включительно, во второе - от 1 до 20.
Эти ограничения произвольны и вызваны только стремлением не "рвать шаблон" страницы, вы их можете поменять в коде функции calc().
Наверное, можно распределять и "случайней", но я свою задачу с помощью этого скрипта решил, вот он в работе и исходниках, может быть, кому-то ещё понадобится такой сервис:
Для работы сервиса требуется только включённый в браузере Javascript. В некоторых браузерах, при многократном использовании скрипта, страница может "закэшироваться", как и любая другая - тогда нажимайте F5 или Ctrl+F5 для её принудительного обновления. В верхнее поле числа вводятся через пробел.
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<title>Распределение объектов по категориям</title>
</head>
<body>
<script type="text/javascript">
function trim(string) { return string.replace (/\s+/g, " ").replace(/(^\s*)|(\s*)$/g, ""); }
var o = Array ();
var k = 0;
function calc2() {
var c = o.length;
var b = Array ();
var sum = 0;
var kol = 0;
for (var i=0; i<c; i++) {
sum += o[i];
for (var j=0; j<o[i]; j++) b[kol++] = i+1;
}
var n=Math.ceil(sum/k);
var v = Array (n);
for (var i=0; i<n; i++) {
v[i] = Array (k);
for (var j=0; j<k; j++) v[i][j] = '-';
}
for (var i=0; i<kol; i++) v[i%n][Math.floor(i/n)]=b[i];
var str='';
for (var i=0; i<n; i++) {
str+='(';
for (var j=0; j<k; j++) str+=v[i][j]+(j<k-1?',':'');
str+=')'+(i<n-1?' ':'');
}
str+='<br>Всего объектов: '+sum+'<br>Распределено наборов: '+n;
if (n*k!=kol) str+='<br>Осталось пустых мест: '+Math.abs(kol-n*k);
return str;
}
function calc () {
var oo=trim(document.ff.o.value).split(" ");
var msg1 = 'Введите в поле "Объектов в категориях" хотя бы 2 натуральных числа';
if (oo.length<2) return msg1;
o.splice(0, o.length);
for (var i=0; i<oo.length; i++) {
o[i]=parseInt(trim(oo[i]));
if (isNaN(o[i]) || o[i]<1) return msg1;
else if (o[i]>99) return 'Извините, в поле "Объектов в категориях" разрешены числа от 1 до 99';
}
k=parseInt(trim(document.ff.k.value));
if (isNaN(k) || k<1) return 'Введите в поле "Распределить по" натуральное число';
else if (k>20) return 'Извините, в поле "Распределить по" разрешены числа от 1 до 20';
return calc2();
}
function clearme () {
document.getElementById('ff_result').innerHTML='';
document.ff.o.value='';
document.ff.k.value='';
o.splice(0, o.length);
k = 0;
}
</script>
<noscript>
<div align="center">Извините, для работы приложения нужен включённый Javascript</div>
</noscript>
<form name="ff">
<table align="center" border="0" cellpadding="2" cellspacing="0" width="40%">
<tr>
<td>Объектов в категориях 1,2,...:</td>
<td><input type="text" size="16" maxlength="14" name="o" value=""></td>
</tr>
<tr>
<td>Распределить по:</td>
<td><input type="text" size="3" maxlength="2" name="k" value=""></td>
</tr>
<tr>
<td align="right"><input type="button" value="Вычислить"
onclick="document.getElementById('ff_result').innerHTML=calc()"></td>
<td><input type="button" value="Очистить" onclick="clearme()"></td>
</tr>
<tr>
<td colspan="2"><span id="ff_result"> </span></td>
</tr>
</table>
</form>
</body></html>
19.12.2014, 13:17 [8797 просмотров]