Не ново, конечно. Но я вот узнала совсем недавно)
http://newtimes.ru/articles/detail/58388/

В 1962 году Дэвид Гейл из Университета Брауна и Ллойд Шепли, работавший в знаменитой корпорации RAND, доказали красивую абстрактную теорему, формулировка и идея доказательства которой так просты, что их можно изложить на пальцах. Есть N юношей и N девушек, и у каждого есть какие-то предпочтения относительно возможного партнера. Каждая девушка может сказать, «в каком порядке» ей нравятся юноши: этот — на первом месте, этот — на втором и так далее, до самого конца. В конце списка стоит тот, кто нравится меньше всех. И у каждого юноши есть свой рейтинг девушек. Теорема Гейла-Шепли говорит, что можно разбить юношей и девушек на пары так, чтобы получившаяся комбинация была стабильной, то есть не было бы такого юноши и девушки, которые хотели бы бросить свои пары и стать новой парой. Конечно, то, что разбивка получилась стабильной, не означает, что все абсолютно счастливы. Кому-то мог достаться партнер, стоящий далеко не на первом месте в рейтинге. И тем не менее это уже кое-что: участникам невыгодно покидать пары, созданные для них алгоритмом.


Собственно, алгоритм Гейла–Шепли несложен. Можно сделать так. Сначала каждый юноша делает предложение «девушке своей мечты» — той, которая стоит в его рейтинге первой. Каждая девушка выбирает самое привлекательное из сделанных ей предложений (если, конечно, они вообще есть), но не торопится принимать его. После этого те юноши, чье предложение было отклонено в первом раунде, снова делают предложения. Может оказаться, что какая-то девушка предпочтет новое предложение тому, которое она выбрала (но не приняла!) раньше, что ж, тогда автор предложения, которое теперь отвергнуто, будет иметь возможность сделать кому-то предложение в следующем раунде. Работа алгоритма прекращается в тот момент, когда оказывается, что все разбились на пары (в том, что в итоге так и получится, состоит теорема Гейла–Шепли),— и теперь предложения окончательно принимаются.


Такой способ разбивать юношей и девушек на пары не единственный. Конкретно этот алгоритм максимально хорош (из числа тех алгоритмов, которые приводят к успеху) для юношей и совсем плох для девушек. Если бы девушки делали предложения, было бы наоборот.


Мне кажется, это так по-одинэсовски :) И главное, о чем думал автор, когда создавал алгоритм.

Саша любит Машу и ненавидит Таню
Паша любит Машу и ненавидит Таню
Маша любит Сашу и ненавидит Пашу
Таня любит Сашу и ненавидит Пашу

что делать?

Не учтён вариант, когда парню/девушке не нравится никто из представленного списка.

(1) Так появились геи и лесбиянки

(1) Делов-то. Говоришь им всем - если через 5 минут не разобьетесь на устойчивые пары и не образуете стабильную комбинацию из 4-х пар, всех расстреляем за сараем.

(2) ну люди, между прочим, за это нобелевскую премию получили. И даже преминили на практике, ну естественно не на Машах и Сашах)

(0) Геи и лесби негодуэ

(3) и шведские семьи

(1) Сашу и Машу поженить.
Паше выдать люлей от Саши.
Таню и Пашу изгнать из племени, они подружатся как неудачники.

(2) это не отменяет возможности сортировки

(1)(2) в условиях вроде четко прописано - нет понятия "не нравится", "ненавидит", а только градация лучше / хуже

Ира, ты же не такая!

(10) измени на 0 и 1

(10) точно, надо рассказать Тане про биологические часы)

(10) Значит, в сортировку нужно добавить вариант "Против всех" в качестве виртуальной девушки/парня.

(0) Автор думал о математике. А вы о чем подумали?

Нэш придумал другой алгоритм. Как развести самую красивую девушку.

(2) У каждого есть рейтинг. Т.е., по крайней мере, парню/девушке кто-то противен меньше остальных

(15) о_О, чего только не узнаешь о математиках :)

(15) выкладывай алгоритм, прямо даже интересно на это посмотреть

(0) Чего хотят женщины ещё не выяснили, не забивай себе голову всякой мутью

(19) в пятницу точно можно :)

(18) а что тут думать? берёшь двух самых красивых девушек и разводишь их в нескольких итерациях. со временем выведутся идеальные красавицы, по Дарвину

(20) Эта тема должна была быть вчера, а вчерашняя сегодня.

не прописан алгоритм принятия решения девушками
они мониторят кто остался свободен и на основании этого принимают решение?

(23) строго ГСЧ

(0) Опыт ДомДва показывает, что в наших реалиях данный алгоритм не работает.

У меня свой алгоритм был, офигенно эффективный!

(24) тогда не будет соблюдено условие нераспадения пар

(22) Ну уж извини, как получилось :)

(21) хмм, разводиться-то будут почкованием?

(27) зато будет жизненно

(18)
http://ucmok-peku.livejournal.com/160387.html

В фильме открытие Нэша было проиллюстрировано эпизодом с пятью симпатичными девушками. Если бы все приятели Нэша бросились к самой красивой из них (то есть стали играть каждый за себя), то они бы, во-первых, оттесняя друг друга, не добились ее, а во-вторых – повернувшись к ее подругам спинами, были бы отвергнутыми и ими, поскольку никто не хочет стать «утешительным призом». «Равновесие Нэша» предложило им другой вариант – начать ухаживать за каждой девушкой в отдельности, в результате чего, практически все получили желаемое.

(26) поведай всем

(28) ну.. медицина сейчас на всякие шалости способна

а ведь это решение задачи планирования задачь по критериям срочность/важность... Или я ошибаюсь?

(0) Срочно замуж (С) :))))))))))))))))))

(34) ну или хотя бы секса регулярного :)

(34) ну так вот я и изучаю возможные схемы :)

(36) давай свою таблицу предпочтений, с моей скрещивать будем

(36) Схемы секса?

кстати почему этому математику, шепли, не сказали "Срочно замуж, ну или хотя бы секса" ?

(36) Умница! :)))))))))))))

(39) Интересно эти математики женаты или нет были?

(39) Математик - мужчина. Дальше - все догадались?

(37) вот это мы как раз вчера выясняли, оказалось что важно, чтобы жаб целовать любил и готов был тащить диван на Эверест

(5) Насчет Нобелевской премии математику - ложь.

(43) И сколько таких идиотов на миллион мужского населения?

"Каждая девушка может сказать, «в каком порядке» ей нравятся юноши" - по моему это какие-то уникалные девушки...

(44) Это мелочи

(46) девушки самые обычные. просто у них это в периодическом РС с периодом секунда

(44) а она не по математике, а по экономике

(48) И ГенераторСлучайныхЧисел, который помогает этот регистр заполнять...

Я бы экономистам тоже не давал, они ещё не придумали ничего полезного.

(8) 1. Подружатся, но не поженятся.
2. За что Паше люлей?

(43) диаметрально противоположно. мне не нравятся девушки-грузчики с зоофильскими наклонностями

(51) так ты и не девушка, чтобы экономистам давать)

(49) и не математику :)

(53) не судьба, но у нас же теперь есть ТЕОРИЯ :)

(54) Симпатичной молодой экономистке я бы отдался, и, возможно, даже бесплатно.

(57) Вопрос: а она бы тебя взяла? Пусть даже бесплатно :))))))

PS Пятница - удалась!!!!!!

(58) экономистка да на такую скидку? конечно клюнет

более точный алгоритм из wiki:

1. мужчины делают предложение наиболее предпочитаемой женщине;
2. каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть», на все остальные отвечает «нет»;
3. мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;
4. если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;
шаги повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.

Для алгоритма требуется порядка n? шагов, где n — число мужчин и женщин.

(56) согласно теории мы составляем идеальную пару, т.к. разбегаться просто не к кому - таковы исходные таблицы предпочтений

(58) не правильная постановка :) правильно: каким по счету он был бы в очереди )

(59) "Верочка, вы сапоги купили?"
"Да вот, думаю.... А Вам как?"
"На мой взгляд - слишком вызывающе"
"Значит - надо брать" (С)

(61) в этой схеме не хватает только билетов на необитаемый остров :) И моих документов на имя Пятница)

(60) весьма жизненно, только мужчины почему-то не понимают, когда женщины так делают :)

(62) Тут самое главное не показывать виду, что готов стать в очередь. Как на рыбалке, сорвалась, да и рен с ней. я лучше другую поймаю, чем об упущенной буду сожалеть.

Опять Морковке моркови не досталось?

(67) ну да, вчера же все мистяне слились :) А сегодня вообще пятница

(67) Ты поаккуратнее. Морковка - не вегетарианка. Она мужчин кушает на завтрак, ланч, обед, файфоклок и ужин.

(69) Вроде по фоткам не толстая, или она их только надкусывает?

(66) анек есть замечательный :)
"... лучше полчаса подождать, чем два уговарвать !"(с)

(70) угу, высасываю мозг через уши :)

(68) на то есть причины же ;)

(72) мозг ли?

(72) Не, через уши - это не к нам. Нам бы несколько другим способом...

(74) не, ну моих талантов хватит только на мозг :)

Резвятся гусары, уже все перепробовали, все надоело! Ржевский:
- Господа! У меня идея! Дамы стоят по одну сторону комнаты у стенки, гусары - по
другую. Кто попадет с разбега, тот целует даме ручку!

(76) вот видишь, надо совершенствовать навыки, глядишь все и наладится

(75) (78) это не оригинально, про не через уши любая дура знает :)

(69) Я не боюсь. Меня слопает - отравится насмерть

(79) знает <> умеет ;)

(77) из дневника гусара
... пятница - пили все что горит, трахали все что шевелится
... суббота - приехал Ржевский, начался разврат и пьянство.

— Я на диету села! Сегодня на обед съела два яйца и одну морковку,  а на ужин два киви и банан!
— А завтра два помидора и огурец?
— Да! А как ты догадался?

(80) сильно ядовитый жаб?

(4) :))))
100% будет правильное и стабильное деление.

(84) Не жаб, но ядовитый.

(0) Надо же, прикрылась математикой, а продолжению по сути вчерашнего

(87) а вас что-то не устраивает?) Вот честно, случайно наткнулась на эту статью, не могла не поделиться в пятницу)

(87) Так кому что а шелудивому в баню

(89) предлагала вчера, сами отказались диван в баню переть)

(90) Это ты отказалась на Эверест...

(88) А разве выводы не сделаны в предыдущей ветке?)

(90) Так нам в баню ни к чему. У нас это так сильно на место не завязано. Да и диван тоже не самое необходимое в этом деле.

(91) все, устала уже флудерастить :) Ну тема-то правда забавная, когда ученый придумывает как математически всех так поженить, чтобы все были счастливы.

(94) Блажен кто верует. Если бы устала давно бы в бане на диване была а не на мисте.

(94) Зачем ученый? Всё происходит на интуитивном уровне и выборка точней, чем в алгоритмичном варианте

(94) Ошибка в самой постановке - для счастья совершенно необязательно жениться.

(97) Точнее - обязательно не жениться :-)

(98) а на замуж это распостраняется?

(98)Также, НЕ обязательно НЕ Женится для счастья)

(99) Не знаю, ни разу замуж не ходил.

(99) монопенисуально
Счасьте не в гениталиях находится, и даже не в голове.

(102) неужели в .опе?

Получается, чисто математически, если у Морковки было 20 мужчин, она вполне могла бы уже выбарть пару и быть счастлива, да?

(103) Там судя по поговоркам не счастье, а правда.

(104) Этого даже с избытком, можно было осчастливить 20 человек, а пока огорчает только себя.

(104)
<<2. каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть», на все остальные отвечает «нет»;>>

Тут уже прерывается цикл, поскольку чтобы ответить «может быть», надо знать предпочтения. А чтобы их знать, недостаточно со стороны наблюдать

(107) если предположить что они были, можно сделать вывод что им не сказали нет.

(102) Увы, в голове. Точнее в психике.

(106) Всех сразу?

(108) А «может быть» ещё не было?)

(111)вопрос Морковке

(104) Да мне как бы и пару многовато, одного вполне достаточно :) И откуда цифра 20?

(113) n- любое число.

(114) ну раз любое, может я хочу скажем 666. Красиво же,а ?

(115) 666? а ты не сдохнешь как та корова? (с)

(113) выбрать пару!= выбрать двоих, выбрать пару= выбрать партнера для жизни.

(52) а это хороший вопрос :)

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

(116) это у вас слишком пошлые мысли, мне чисто посмотреть и сказать "нет" :)

(120)Как только "за посмотреть" можно понять что оно тебе не надо?

(120) Почему "нет" и почему "может быть"

(121)+ даже на машину и то тест-драй предоставляют.

(123) Она на тест-драйв не соглашается...

(124) хотя бы "может быть" говорит?

(124) Боится что понравится?

(126) Или просто боится :_)
(125) Не знаю, не я предлагал ...

(123) А зачем ей тест - драйв, если ездить всё равно не буде

(128) может она не программист а тестировщик?

(128) чтобы понять от чего отказывается.

(130) нет ответа

Да бес проблем, можно и тест-драйв устроить, диван имеется, даже на Эверест тащить не придется, моего третьего этажа вполне достаточно будет :)

(132) Ну вот... А как романтично все начиналось.

(133) ну могу свечи зажечь, вроде тоже имеются. Так романтичнее будет диван таскать?

(134) Романтика - она не в свечах, она в душе.

(135) Свечи можно и в душ отнести

А что... Диван под душем таскать... И ещё свечку при этом держать...

(136) +
(137) Это уже какие-то акробатические этюды. Так и до травмы недалеко.

(136) а диван при этом кто таскать будет?

У морковки обострение?

(140) это не у меня, не я же про тест-драйв начала :) Я всего на всего выложила статью про работу на нобелевку )

(141) но продолжила)))

А почему ветка не закрыта :)

АМ. Еще раз всех причастных с днем ВДВ!!! Нормальные мужики на эту тему не парятся, а берут в жены/любовницы/ девушки тех кто на первом месте в списке.

(132) упала с дивана? Какой тест-драйв? На диване, на третьм этаже???? С таким подходом замуж будешь выходить еще лет сорок. Если тест-драйв ктото захотел, то минимуму кровать 2на 2 метра и минимум этаж так семьдесят восьмой. Или я чегото не понял?

Бабы завсегда сами не знают чего хотят! Логика - это не для них