Задачу по комбинаторики загнать в комп

post2225441

Есть массив с нкоторым числом наборов (от 8 до 20 штук). Набор - это пара чисел, каждое из которых от 0 до 7 (34,55,00,77,71...). Надо расставить на эти наборы значения от 0 до 7, чтобы
1) ВСЕ значения встречались хотя бы раз и
2) соблюдалась монотонность в таком плане: 0<1, 0<2, 1<3, 1<4, 2<3, 2<4, 3<5, 3<6, 4<5, 4<6,
5<7, 6<7 и 1,2 - несравнимы, 3,4 - несравнимы, 5,6 - несравнимы.
Нужен алгоритм для реализации на компе. Я пока сделал прямой перебор для 8 наборов. Получилось, но очень долго. То есть для > 8 не потянет способ такой.

post2225441

Ну что, задачу хоть кто-нибудь понял?
Распишу ещё немного.
Каждому набору в масиве сопоставляем какое-то число в пределах от 0 до 7. Надо найти количество комбинаций таких, чтобы выполнялись два условия.
1)Каждое из чисел 0,1,2,3,4,5,6,7 было сопоставлено хотя бы одному набору из масива.
2)Соблюдалась монотонность, то есть если один набор < или = другому, то сопоставленные им значения также были бы < или равны. На несравнимых наборах значения могут быть любыми.(см. 1-й пост в треде).
Эту задачу надо реализовать на компе, так как вручную не получиться. Соответственно нужен алгоритм, так как прямой перебор не покатит.

vital_m

Как сравнивать наборы? Не числа от 0 до 7, а наборы из двух чисел?

galka1

Что-то я не догоняю - каждый набор считать двузначным числом и просто их сравнивать ? почему бы сразу не сказать что это массив двухзначных чисел (записаных в восьмеричной системе, если уж не нужны "8" и "9")? Или эти наборы как-то по хитрому нужно сравнивать ?

natunchik

Если ты мне по аське внятно объяснишь условия задачи и поставишь пару пива, то я, наверное, за полчасика наваяю прогу.

post2225441

Объясняю как сравниваются наборы.
(a1,b1) u (a2,b2) - два набора.
(a1,b1) < или = (a2,b2) тогда и только тогда, когда a1 < = a2 u b1 < = b2 ! Если же либо а1 а2,
либо b1 b2, либо a1 > a2 , либо b1 > b2, ТО наборы (a1,b1) (a2,b2 считаются несравнимы!
- обозначание несравнимости. Несравнимыми считаются числа 1 2 , 3 4 , 5 6. Приведу ряд примеров.
12<34, 01<66, 45<47, 17<37, 66< 76, 20<21, 73<77 (77 - больше любого набора, 0 - меньше любого НО(!) 34 61, 55 17, 07 11, 61 70, 45 46, 37 47, 01 02, 73 74.
Если вы поняли все примеры, то считайте что со сравнением разобрались.
Повторю второе условие в задаче:
2) Должна выполняться монотонность, то есть если один набор <= второго, то сопоставленные им значения также должны быть первое <= второго. Вот так-то.

post2225441

Условие вроде объяснил уже. Прога мне не нужна ! Я и сам могу запрограмировать, если есть алгоритм. Именно нужен алгоритм, кроме полного перебора. Как-то надо уменьшить кол-во перебираемых чисел, так как большинство из них не удовлетворяет условию 1 и ещё меньшее удовлетворяет условию 2).

filippov2005

14, 23, 24, 31, 41, 32, 42
Никакие два набора несравнимы. Тут никакой алгоритм не поможет
А не, ступил. На несравнимых значения любые могут быть.

filippov2005

А вот наоборот:
00, 01, 03, 05, 07, 17, 37, 57, 77
-набор, где любые два набора сравнимы.
Т.е. программа должна выдать на таком наборе, что нужного сопоставления нет?
Ага, я кажется понял. Задачу можно переформулировать так.
Надо разбить множество наборов на ровно 5 непересекающихся подмножеств, в каждом подмножестве наборы должны быть попарно несравнимы.
Или еще лучше так: имеется граф. Разбить его на пять подграфов так, что каждый будет полным графом.
Ребром будем соединять несравнимые наборы.

elektronik

Нужно ведь найти количество таких сопоставлений!
В данном случае их просто 0.

filippov2005

А как тебе переформулировка задачи? См. измененный пост выше. ИМХО в постановке с графом ее решить легче
Про количество таких комбинаций не заметил - это только во втором посте написано было.

natunchik

Короче. Линейно упорядочиваешь наборы. Это очень просто - находишь тот, который меньше/не сравним со всеми остальными, ставишь его на первое место, ищешь дальше среди оставшихся.
Потом рекурсивно перебираешь идя от минимального к максимальному. Получается перебор, конечно, но не полный.
Ты уверен, что ты правильно сказал условие? Зачем она (задачка) вообще тебе нужна? Потому что я, наверное, могу придумать алгоритм, который ее решит реально быстро. Часик подумать - . Или три часика, не знаю. Короче, это я к тому, что у меня создается легкое ощущение, что кто-то разводит кого-то на курсовую нахаляву =)

post2225441

ДА, нужно имено числа комбинаций.
А переформулировать задачу можешь как тебе удобно.
Тока вот мне надо не формулировки, а алгоритм решения.
Еще небольшое дополнение: в заданном массиве наборов обязательно присутствует хотя бы пара сравнимх наборов и хотя бы пара несравнимых.

post2225441

Твой способ ниасилил . То есть я понял как упорядочить их, но что потом делать?
Условие абсолютно правильно(если собрать мои посты вместе). Данная задача является заключительной подзадачей(примерно 1\4 часть) моей производ. практики. Я никого не заставляю её решать. Может просто кому-то делать нечего, желает помочь.

natunchik

Неа. На самом деле все гораздо хуже. Насколько я понял, у него там отношение порядка "меньше или равно". Так что для набора
00, 01, 03, 05, 07, 17, 37, 57, 77
ставим
0 0 0 0 1 3 5 7 7

А если учесть что считать нужно _количество_ вариантов, а число 20 подозрительно близко к тому месту где перестают считаться факториальные переборы (13 или 14, если прибавить 7 то как раз то вырисовывается жопа какая-то. В том смысле что надо прикручивать какое-нить динамическое программирование.
У меня в голове бродят всякие мысли про построение графа сравнимости наборов, выделения компонент связности, а потом для каждой компоненты строить крайне специфическую многомерную табличку для динамического программирования. Но это пиздец прогать надо. Там же всякие шняжки типа наборов вида
00 10 20 30 50 60 70 ,
у которых граф выглядит вот так


*
/ \
* *
\ /
*
/ \
* *
\ /
*


то есть утешает мысль, что таких вот мест где таблички должны как бы сливаццо в экстазе не очень много может быть. Типа самая длинная сравнимая цепочка вроде как длины 9. Если не учитывать одинаковые наборы, которые типа не очень мешают.
Но ваще по-моему что-то тут нечисто =)

filippov2005

- это к чему? Если ты хочешь чего-то требовать, то назначай цену - и в маркет Ты плохо сформулировал задачу, поэтому я не сразу понял, что к чему.
По существу. [написанное ниже в корне не верно Надо думать дальше]Следуя совету Fj (в общих чертах):
Первый этап:
0 - всем наборам, меньших которых нет.
Исключаем все наборы, которым сопоставлен 0
...
k - всем наборам, меньших которых нет среди оставшихся
Исключаем все наборы, которым сопоставлен k
...
Пусть максимальный встретившийся номер - n
Если n > 4, то ничего не выйдет
Если n = 4, то 0 сопоставляем 0
1 - 1 или 2
2 - 3 или 4
3 - 5 или 6
4 - 7
Ну и т.д и т.п

filippov2005

А, понял. Тогда в моей наметке решения n может быть и больше 4 и вообще все неправильно я написал Да, сложная задачка.
Автору: Если не секрет, для чего нужна задача? Похоже ее решение требует времени.

sashachist

Данная задача является заключительной подзадачей(примерно 1\4 часть) моей производ. практики. Я никого не заставляю её решать. Может просто кому-то делать нечего, желает помочь.

Sanych

Насколько я понял, резко сократить перебор можно таким образом:
разбивать последовательно
всё на 012+34567;(цикл по возможным кускам 012!>34567)
012 на 0+12 посчитать сколько, и есть ли на самом деле
34567 на 34+567; посчитать для 34
567 на 56+7; посчитать и перемножить
при этом число вариантов для групп типа 12 это видимо кол-во способов разделения на несравнимые компоненты и считается через кол-во таких компонент, если число наборов не 1/2/?3

post2225441

ниасилил твой способ
можно поподробнее?
2ALL: если так ламаит напрягаться за просто так, то с меня пиво\сок тому человеку, кто первый предложит алгоритм данной задачи, который будет работать для количества наборов от 8 до 20 штук(можно больше 20-ти).

Sanych

Можно.
Во внешнем цикле мы перебираем все подмножества наборов, которые могут оказаться множеством цифр 0,1,2.
(те такие множества, которые вместе с набором содержат и все меньшие наборы.)
Для каждого такого подмножества вычисляем
а) число способов попавшим в него наборам присвоить номера 0,1,2
б)[если в а) не получился 0] число способов не попавшим в подмножество наборам присвоить номера от 3 до 7
в) произведение результатов пунктов а) и б)
г)сложить результаты по всем подмножествам
схема программы как я её вижу (наибольшая тяжесть в самом глубоком цикле 34567->567->56, так что на скорость работы unj_divis_amt может быть придётся обратить внимание).
main{
res=split({множество наборов},f0,f1)
}
f0(a)
{
return split(a,notempty,unj_divis_amt)
}
f1(a)
{
return split(a,unj_divis_amt,f2);
}
f2(a)
{
return split(a,unj_divis_amt,notempty)
}
notempty(a)
{
if (a пустое множество) return 0 else return 1;
}
unj_divis_amt(a)
{
return (количество способов разбить наборы множества a на 2 попарно несравнимых подмножества)
}
split(X,f1,f2)
{
res=0;
цикл по всем A подмножествам в X
{
if(нет элементов A больших, чем элементы X\A)
if(f1(A) не равно 0)
res+=f1(A)*f2(X\A);
}
return res;
}
//я очевидно переборщил с параметрами в предыдущем варианте

post2225441

Народ! Помогите всё-таки решить задачу(указана в начале треда плз! Нужна не прога, а всего лишь алгоритм в двух словах, чтобы мне было понятно. Даю за это три сока\пива или в денежном эквиваленте(100р.)! Актуально до вечера воскресенья.
PS: вышеуказанный способ вроде не прокатит.
Оставить комментарий
Имя или ник:
Комментарий: