В исходном двумерном массиве хранится n элементов. Массив выглядит примерно так:
var all = [ ["value", 1], ["value2", 0.9], ["value3", 2.2] ];
Нам нужно сгенерировать новый массив, длинна которого = k. При условии, что n >= k.
- Новый массив должен состоять из элементов исходного массива (без повторений).
- Длинна нового массива меньше либо равна длине исходного.
- Элементы в новом массиве не сохраняют порядок исходного массива (перемешаны между собой).
По-хорошему нам нужно просто перемешать исходный массив и отрезать от него k элементов. Но это не все условия. Обратим внимание на вторые значения каждого элемента массива: 1, 0.9, 2.2 ... Это - коэффициенты, которые определяют вероятность попадания этого элемента в новый массив. Это - любое неотрицательное число, включая 0. Если 0 - элемент не должен попасть в новый массив, только если у нас не будет "нехватки" элементов. Допустим, в исходном массиве у нас 100 элементов, а в новом массиве должно быть всего 50 элементов. Получается, что каждый конкретный элемент попадет в новый массив с вероятностью 0.5. Это дефолтная вероятность, которую мы должны учитывать. Более того, скажем, коэффициент этого конкретного элемента = 2.3, а это должно означать, что этот элемент должен попасть в новый массив в 2.3 раза вероятнее, чем, скажем, элемент, у которого этот коэффициент равнялся бы единице.
Если бы у всех элементов коэффициенты равнялись бы единице, они все были бы равноправные и одинаково часто попадали бы в новый массив.
Соответственно, если коэффициент < 1, то элемент будет попадать в новый массив с меньшей вероятностью. Стоит подчеркнуть, что если рядом стоят 2 элемента, у которых коэффициенты равны соответственно 0.001 и 1000, то оба эти элемента могут попасть в новый массив. У нас нет предвзятости, только случайность.
Я набросал код. Он также может помочь понять требования к алгоритму. Однако сложность моего алгоритма чрезвычайно высока. Алгоритм нерационален. Прошу помочь с идеями по оптимизации.