Как выбрать 4 уникальных предмета из взвешенного списка? - PullRequest
Новая
       27

Как выбрать 4 уникальных предмета из взвешенного списка?

4 голосов
/ 23 июня 2011

Итак, у меня есть список взвешенных предметов, и я хотел бы выбрать 4 неповторяющихся предмета из этого списка.

Item     Weight
Apple     5
Banana    7
Cherry    12
...
Orange    8
Pineapple 50

Какой самый эффективный способ сделать это?Моя первоначальная попытка заключалась в том, чтобы просто перебраться на последующие пики, если появился уже выбранный предмет ... но для небольшого списка это может привести к тонне рероллов.

Редактировать для пояснения: для приведенного выше примера:и игнорируя фрукты от D до N, общий вес составляет 82. Таким образом, шансы быть выбранными первыми: A ~ 6% B ~ 8,5% C ~ 14,6% O ~ 9,8% P ~ 61% После того, как предмет выбранвероятности будут (должны!) измениться.

Ответы [ 4 ]

6 голосов
/ 23 июня 2011

В своем комментарии вы говорите, что уникальные средства:

Я не хочу выбирать один и тот же предмет дважды.

..и весы определяют вероятность того, что их выберут.

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

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

Я использовал здесь JavaScript, просто чтобы было легко увидеть вывод в браузере без сервера. Это должно быть тривиально портировать на PHP, поскольку он не делает ничего сложного.

Константы 

var FRUITS = [
    {name : "Apple", weight: 8 },
    {name : "Orange", weight: 4 },
    {name : "Banana", weight: 4 },
    {name : "Nectarine", weight: 3 },
    {name : "Kiwi", weight: 1 }
];

var PICKS = 3;

function getNewFruitsAvailable(fruits, removeFruit) {
    var newFruits = [];
    for (var idx in fruits) {
        if (fruits[idx].name != removeFruit) {
            newFruits.push(fruits[idx]);
        }
    }
    return newFruits;
}

Сценарий 

var results = [];
var candidateFruits = FRUITS;

for (var i=0; i < PICKS; i++) {
    // CALCULATE TOTAL WEIGHT OF AVAILABLE FRUITS
    var totalweight = 0;
    for (var idx in candidateFruits) {
        totalweight += candidateFruits[idx].weight;
    }
    console.log("Total weight: " + totalweight);

    var rand = Math.random();

    console.log("Random: " + rand);

    // ITERATE THROUGH FRUITS AND PICK THE ONE THAT MATCHES THE RANDOM
    var weightinc = 0;
    for (idx in candidateFruits) {
        // INCREMENT THE WEIGHT BY THE NEXT FRUIT'S WEIGHT
        var candidate = candidateFruits[idx];
        weightinc += candidate.weight;

        // IF rand IS BETWEEN LAST WEIGHT AND NEXT WEIGHT, PICK THIS FRUIT
        if (rand < weightinc/totalweight) {
            results.push(candidate.name);
            console.log("Pick: " + candidate.name);

            // GET NEXT SET OF FRUITS (REMOVING PICKED FRUIT)
            candidateFruits = getNewFruitsAvailable(candidateFruits, candidate.name);
            break;
        }
    }
    console.log("CandidateFruits: " + candidateFruits.length);
};

выход 

for (var i=0; i < results.length; i++) {
    document.write(results[i] + "<br/>");
}

Основная стратегия состоит в том, чтобы выделить каждому фрукту часть общего диапазона [0,1). В первом цикле у вас будет это:

  • Apple & mdash; 8/20 = 0,0 до 0,4
  • Оранжевый & mdash; 4/20 = 0,4 до 0,6
  • Банан & mdash; 4/20 = 0,6 до 0,8
  • Нектарин & mdash; 3/20 = 0,8 до 0,95
  • Киви & mdash; 8/20 = 0,95 до 1,0

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

1 голос
/ 23 июня 2011

Здесь я нашел идею для следующих шагов:

  1. Построить сумму весов -> СУММА
  2. Построить случайное число от 0 до SUM -> RAND_NUMBER
  3. Итерация по списку и вычитание веса каждого элемента из RAND_NUMBER. Если RAND_NUMBER становится отрицательным, у вас есть ваш первый элемент.
  4. Удалите найденный элемент из списка и вернитесь к шагу 1, пока у вас не будет 4 элемента.
1 голос
/ 23 июня 2011

Обновление 

function array_rand2($ary,$n = 1)
{
  // make sure we don't get in to an infinite loop
  // check we have enough options to select from
  $unique = count(array_unique(array_keys($ary)));
  if ($n > $unique) $n = count($unique);

  // First, explode the array and expand out all the weights
  // this means something with a weight of 5 will appear in
  // in the array 5 times
  $_ary = array();
  foreach ($ary as $item => $weight)
  {
    $_ary = array_merge($_ary, array_fill(0, $weight, $item));
  }

  // now look for $n unique entries
  $matches = array();
  while (count($matches) < $n)
  {
    $r = $_ary[array_rand($_ary)];
    if (!in_array($r,$matches))
    {
      $matches[] = $r;
    }
  }

  // and now grab those $n entries and return them
  $result = array();
  foreach ($matches as $match){
    $result[] = $match;
  }
  return $result;
}

Посмотрите, будет ли это лучше.

0 голосов
/ 23 июня 2011

Возможно, вместо "rerolls" вы можете просто увеличить индекс элемента списка, который вы случайно сгенерировали: list.elementAt(rand_index++ % size(list)) (что-то в этом роде). Я думаю, вы нашли бы следующий случайный уникальный предмет довольно быстро с такой логикой.

Я уверен, что есть даже лучшие решения, конечно, обычно есть.

Редактировать: похоже, что Брэд уже предоставил один ..:)

...