Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 22
Здесь мы рассмотрим более сложную задачу, решения которой в рунете я не нашелБез обид, но плохо искали, вот, например: ссылка. И ещё куча есть, это очень известная, классическая задача.
Было бы интересно получить справочник по комбинаторным алгоритмам для всех комбинаторных объектов, включая, перестановки, сочетания, размещения, разбиения на подмножества, сочетания с повторениями, размещения с повторениями.Для различных комбинаторных объектов немножко отличается только первая задача (сгенерировать все объекты по порядку), вторая задача сводится к комбинации третьей и четвертой, а они в свою очередь абсолютно идентично делаются для всех типов комбинаторных объектов, изменяется только формулы количества объектов с заданным префиксом.
Должен отметить статью Тимошевской Н. Е., на которую я поначалу не обратил внимания: cyberleninka.ru/article/n/o-numeratsii-perestanovok-i-sochetaniy-dlya-organizatsii-parallelnyh-vychisleniy-v-zadachah-proektirovaniya-upravlyayuschih-sistem
Статья коротая, но формула индекса сочетания там приводится (без пояснений).
Статья коротая, но формула индекса сочетания там приводится (без пояснений).
Также должен обратить внимание на временнУю сложность наших алгоритмов: они имеют линейную сложность при условии, что C вы считаете за константное время.
Но на самом деле для фиксированной размерности базового множества (в нашем случае 52) ничего не мешает свести алгоритм к константной сложности.Факт в том, что если алгоритм работает за O(n), а n равно константе, то этот алгоритм будет работать за константное время (очевидным образом, это верно для любой сложности, зависящей только от n, хоть O(nn)).
Из названия поста неясно, что разбивается число или множество. В математике и комбинаторике терминология сложилась и не нам ее менять, если Вы не вводите новый объект. Разбиения делаются на блоки или на части, но не на множества. Посмотрите определения у Эндрюса Г. Теория разбиений, или у Холла М. Комбинаторика. Липский Комбинаторика для программистов. В множестве даже двух одинаковых элементов не бывает, а разбиения чисел бывают на равные части.
Задачи, о которых Вы пишете давно решены, причем прямые и обратные: прямые по заданному объекту — найти его лексикографический номер (а не просто какой-то номер); обратные — по лексикографическому номеру — найти сам объект. Их выдают в качестве домашних заданий или курсовых работ студентам и курсантам.
Для множества всех возможных сочетаний(множества всех подмножеств) номер сочетания можно получить пронумеровав объекты и сложив соответствующие степени двойки. А обратная задача выбора объектов по номеру сочетания: взять номер перевести в бинарную форму и выбрать объекты, соответствующие позициям с единицами.
Алгоритм в студию
Пример для консоли хрома(не образец правильного написания программ на js):
З.Ы.Иногда удобнее использовать упорядоченный подмассив фиксированного размера [, 2, 3]. Тогда вместо поиска:
function getIndex(arr, subarr){
arr.sort()
index = 0
for(i=0,p=1;i<arr.length;i++,p*=2){
isElemInSubarr = subarr.indexOf(arr[i])>=0
if(isElemInSubarr) index += p
}
return index
}
//must: index<2^arr.length
function selectByIndex(arr, index){
arr.sort()
subarr = []
for(i=0;i<arr.length;i++){
isSelected = (index>>i)%2 == 1
if(isSelected) subarr.push(arr[i])
}
return subarr
}
selectByIndex([1,2,3],6).toString() == [2,3].toString()
getIndex([1,2,3], [2,3]) == 6
З.Ы.Иногда удобнее использовать упорядоченный подмассив фиксированного размера [, 2, 3]. Тогда вместо поиска:
isElemInSubarr = subarr.indexOf(arr[i])>=0isElemInSubarr = arr[i] == subarr[i]Тут речь не идет о множестве всех подмножеств.
> индекс разбиения на подмножества
Вы можете сказать, что у вас разбивается число или множество?
Еще лучше, если приведете пример списка разбиений и их лексикографических номеров для числа: 115 от 20-го до 30-го разбиений;
аналогично для множества из 115 элементов (пусть элементами множества будут первые 115 чисел )
Вы можете сказать, что у вас разбивается число или множество?
Еще лучше, если приведете пример списка разбиений и их лексикографических номеров для числа: 115 от 20-го до 30-го разбиений;
аналогично для множества из 115 элементов (пусть элементами множества будут первые 115 чисел )
В требованиях к научному исследованию (к эксперименту) указывается условие повторяемости его результатов другими исследователями. Для повторяемости необходимы идентичные с Вашими исходные данные. Я не могу повторить, проверить правильность и поверить в результат, полученный Вами, так как нет ясности по ряду положений.
Предлагаю привести терминологию к принятой в научной практике. Термин индекс используется в роли логарифма в теоретико-числовых задачах и практически не используется в комбинаторном анализе (см Aйгнер). Если хотите, чтобы Вас правильно понимали, следует придерживаться классики.
Считаю замечательным то, что Вы пришли к этим задачам самостоятельно, но нужна полная математическая ясность.
Предлагаю привести терминологию к принятой в научной практике. Термин индекс используется в роли логарифма в теоретико-числовых задачах и практически не используется в комбинаторном анализе (см Aйгнер). Если хотите, чтобы Вас правильно понимали, следует придерживаться классики.
Считаю замечательным то, что Вы пришли к этим задачам самостоятельно, но нужна полная математическая ясность.
Цитирую себя.
«В комбинаторике есть и более сложный объект — разбиение на подмножества. К примеру, разбиение 52-элементного множества на три подмножества, состоящие соответственно, скажем, из 2, 3 и 47 элементов»
По-моему, вполне ясно, о чем речь.
Поскольку статья размещена с тегами «Программирование, алгоритмы», а не «Математика», то смысл термина «индекс» также считаю вполне ясным; кроме того, его смысл был пояснен в статье: «Каждому сочетанию, перестановке, размещению и другим комбинаторным объектам можно сопоставить индекс — это номер, в котором он появляется при переборе данным алгоритмом».
Так что мне в свою очередь совершенно не ясны ваши претензии. Мне кажется, вы невнимательно и не полностью прочитали статью.
«В комбинаторике есть и более сложный объект — разбиение на подмножества. К примеру, разбиение 52-элементного множества на три подмножества, состоящие соответственно, скажем, из 2, 3 и 47 элементов»
По-моему, вполне ясно, о чем речь.
Поскольку статья размещена с тегами «Программирование, алгоритмы», а не «Математика», то смысл термина «индекс» также считаю вполне ясным; кроме того, его смысл был пояснен в статье: «Каждому сочетанию, перестановке, размещению и другим комбинаторным объектам можно сопоставить индекс — это номер, в котором он появляется при переборе данным алгоритмом».
Так что мне в свою очередь совершенно не ясны ваши претензии. Мне кажется, вы невнимательно и не полностью прочитали статью.
Судя по посту, разбивается множество на заданное число подмножеств заданного размера. Если 115 разбивать как 3+112, то разбиениями с 20-го по 30-е будут
{1,2,22}+..., {1,2,23}+..., ..., {1,2,32}+…
А вот если разбивать 6 как 2+2+2 (порядок существенен, т.е. {1,2}+{3,4}+{5,6} и {3,4}+{1,2}+{5,6} это разные разбиения), то с 20 по 30 будут
19: {1,4}+{2,3}+{5,6}
20: {1,4}+{2,5}+{3,6}
21: {1,4}+{2,6}+{3,5}
22: {1,4}+{3,5}+{2,6}
23: {1,4}+{3,6}+{2,5}
24: {1,4}+{5,6}+{2,3}
25: {2,3}+{1,4}+{5,6}
26: {2,3}+{1,5}+{4,6}
27: {2,3}+{1,6}+{4,5}
28: {2,3}+{4,5}+{1,6}
29: {2,3}+{4,6}+{1,5}
30: {2,3}+{5,6}+{1,4}
{1,2,22}+..., {1,2,23}+..., ..., {1,2,32}+…
А вот если разбивать 6 как 2+2+2 (порядок существенен, т.е. {1,2}+{3,4}+{5,6} и {3,4}+{1,2}+{5,6} это разные разбиения), то с 20 по 30 будут
19: {1,4}+{2,3}+{5,6}
20: {1,4}+{2,5}+{3,6}
21: {1,4}+{2,6}+{3,5}
22: {1,4}+{3,5}+{2,6}
23: {1,4}+{3,6}+{2,5}
24: {1,4}+{5,6}+{2,3}
25: {2,3}+{1,4}+{5,6}
26: {2,3}+{1,5}+{4,6}
27: {2,3}+{1,6}+{4,5}
28: {2,3}+{4,5}+{1,6}
29: {2,3}+{4,6}+{1,5}
30: {2,3}+{5,6}+{1,4}
Лучше перейти на 3-х дневку. Или 2.5 дневку. Можно трудоустроить 2 людей на одно место. Смена. То есть трудоустроить больше людей. Сократить ЗП. Но и сократить плату за ЖКУ и налоги. Вырастет спрос. У людей будет больше времени, они будут ходить в театры, кино, музеи, библиотеки, курсы и тратить там деньги.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Комбинаторные алгоритмы: индекс сочетания, индекс разбиения на подмножества