ФорумПрограммированиеPHP для идиотов → Контролируемый рандом

Контролируемый рандом

  • md5

    Сообщения: 11960 Репутация: N Группа: в ухо

    Spritz 18 апреля 2012 г. 18:22

    салют

    есть 10 человек, у каждого свой скилл
    необходимо их не просто рандомно поделить на 2 команды, но и чтобы суммарный скилл команды был примерно одинаковый
    т.е. как-то уравновесить силы

    подкиньте, пожалуйста, ссылок или алгоритмов, как это делается, чтобы я приобщился
    Спустя 17 сек.
    ps. найс раздел переименовали
    все умрут, а я изумруд
  • phpdude

    Сообщения: 26646 Репутация: N Группа: в ухо

    Spritz 18 апреля 2012 г. 18:24, спустя 2 минуты 7 секунд

    md5, в две корзины скидываешь по минималке и в принципе этого должно хватить.
    Сапожник без сапог
  • AlexB

    Сообщения: 4306 Репутация: N Группа: в ухо

    Spritz 18 апреля 2012 г. 18:31, спустя 6 минут 37 секунд

    отсортировать по скилу а дальше "шеренга, на первый-второй рассчитайсь!!!!"
  • vasa_c

    Сообщения: 3131 Репутация: N Группа: в ухо

    Spritz 18 апреля 2012 г. 18:32, спустя 1 минуту 41 секунду

    1-го по крутости в первую, второго во вторую, третьего в первую, не?
  • kostyl

    Сообщения: 5210 Репутация: N Группа: Джедаи

    Spritz 18 апреля 2012 г. 18:49, спустя 16 минут 11 секунд

    1-го по крутости в первую, второго во вторую, третьего в первую, не?

    отсортировать по скилу а дальше "шеренга, на первый-второй рассчитайсь!!!!"

    так скилы в первой могут быть больше в первой команде сравнимо больше…
    md5, можно же не поровну делить?
    Спустя 45 сек.
    даже нужно (имеется в виду количество)
  • technobulka

    Сообщения: 4540 Репутация: N Группа: Джедаи

    Spritz 18 апреля 2012 г. 19:49, спустя 1 час 45 секунд

    Контролируемый рандом

    отсортировать по скилу а дальше "шеренга, на первый-второй рассчитайсь!!!!"

    отсортировали и попарно раскидываем: первый рандомно в первую или вторую, второй в противоположную))
    Высокоуровневое абстрактное говно
  • Ivan

    Сообщения: 1316 Репутация: N Группа: Адекваты

    Spritz 18 апреля 2012 г. 20:08, спустя 19 минут 2 секунды

    Это из разряда примитивных задач по комбинаторике
  • artoodetoo

    Сообщения: 5147 Репутация: N Группа: в ухо

    Spritz 18 апреля 2012 г. 20:26, спустя 17 минут 50 секунд

    брутфорсом: раскидывать рандомно и оценивать разницу между командами. лучший вариант сохранять

    или:
    1. ты можешь вычислить пол-суммы всей толпы — это то, к чему надо стремиться.
    2. выбираешь первую команду и закидываешь в нее самого жирного игрока из тех кто меньше нужной суммы
    3. считаешь сколько осталось этой команде до нужного порога - это твоя следующая цель
    4. go to 2
    оставшиеся попадут во вторую команду
    Спустя 68 сек.
    отсортировали и попарно раскидываем: первый рандомно в первую или вторую, второй в противоположную))

    вторая получится гарантированно слабее
    ιιlllιlllι унц-унц
  • artoodetoo

    Сообщения: 5147 Репутация: N Группа: в ухо

    Spritz 18 апреля 2012 г. 20:34, спустя 7 минут 44 секунды

    вот лучший вариант:
    0. отсортировали игроков по скиллам
    1. считаем суммы в командах
    2. самого жирного из нераспределенных бросаем в слабую команду
    3. go to 1
    ιιlllιlllι унц-унц
  • technobulka

    Сообщения: 4540 Репутация: N Группа: Джедаи

    Spritz 18 апреля 2012 г. 20:53, спустя 19 минут 36 секунд

    вторая получится гарантированно слабее

    схуяли?
    Высокоуровневое абстрактное говно
  • artoodetoo

    Сообщения: 5147 Репутация: N Группа: в ухо

    Spritz 18 апреля 2012 г. 21:01, спустя 7 минут 27 секунд

    схуяли?

    6 5 4 3 2 1

    при первый/второй будет
    6,4,2 == 12
    5,3,1 == 9

    при справедливом распределении будет
    6,3,2 == 11
    5,4,1 == 10
    Спустя 84 сек.
    притом чем длиннее цепочка, тем у тебя разница будет увеличиваться, а у меня будет оставаться ничтожной
    ιιlllιlllι унц-унц
  • AlexB

    Сообщения: 4306 Репутация: N Группа: в ухо

    Spritz 18 апреля 2012 г. 21:08, спустя 6 минут 43 секунды

    Значит сортируем по скилам, бьем на пары, и раскидываем по двум командам, но не тупо первый-второй, а каждый раз более сильного из пары в более слабую команду. Это при условии, что игроков должно быть одинаково в командах. Ну или алгоритм artoodetoo, если численно одинаковые команды не требуются.
  • technobulka

    Сообщения: 4540 Репутация: N Группа: Джедаи

    Spritz 18 апреля 2012 г. 21:12, спустя 4 минуты 41 секунду

    при справедливом распределении будет

    так рандом надо или справедливо?

    a = [0,1,2,3,4,5,6,7,8,9], l=a.length/2, b=[], c=[];
    while (l–) {
       x = Math.random()*2>>0;
       b.push(a[x+l*2]);
       c.push(a[x^1+l*2]);
    }
    console.log(b, c);
    // [8, 7, 5, 2, 0] [9, 6, 4, 3, 1]
    // [8, 7, 4, 2, 1] [9, 6, 5, 3, 0]
    // [8, 7, 4, 2, 0] [9, 6, 5, 3, 1]
    // [9, 6, 5, 3, 1] [8, 7, 4, 2, 0]
    // [9, 6, 5, 2, 0] [8, 7, 4, 3, 1]


    и вторая слабее таким же шансом, как и первая
    Спустя 163 сек.
    console.log(eval(b.join('+')), eval(c.join('+')));
    // 23 22
    // 22 23
    // 23 22
    // 22 23
    // 23 22

    чем тебе не рандом?
    Спустя 54 сек.
    а у вас всегда будет 22 23 и команды никогда не будут меняться
    Спустя 16 сек.
    и у вас всегда одна команда слабее
    Высокоуровневое абстрактное говно
  • kostyl

    Сообщения: 5210 Репутация: N Группа: Джедаи

    Spritz 18 апреля 2012 г. 21:19, спустя 6 минут 28 секунд

    нужно еще бы задавать соотношение "боллее рандомно" vs "более честно по скилам"
  • artoodetoo

    Сообщения: 5147 Репутация: N Группа: в ухо

    Spritz 18 апреля 2012 г. 21:37, спустя 18 минут 8 секунд

    чето я не догоняю арифметику твою. при действительно рандомном распределении ты можешь одинаково вероятно получить четные против нечетных
    9,7,5,3,1 против 8,6,4,2,0
    25 - 20
    но каким-то счастливым образом твой рандом тауих случаев избегает и делает справедливо )))
    Спустя 77 сек.
    а у вас всегда будет 22 23 и команды никогда не будут меняться

    да, на этом наборе нельзя сделать одинаковые суммы. 22-23 это наилучший возможный результат
    Спустя 58 сек.
    45 пополам
    ιιlllιlllι унц-унц

Пожалуйста, авторизуйтесь, чтобы написать комментарий!