Перемешать массив JS с вероятностью

Question

Скажем, у меня есть такой массив:

const alphabet = ['a', 'b', 'c', 'd'];

Это представляет 4 политических кандидата и голосование по рангу, где кандидат a - первый выбор, b - второй выбор и т. Д.

Я хочу перемешать это в кучу случайных порядков, но в этом случае я хочу, чтобы a появлялся первым с вероятностью 60%, b вторым с вероятностью 20% и c третьим с вероятностью10%, а все остальные заказы с вероятностью 10%.Есть ли какая-нибудь функциональность lodash и ramda, которая может выполнить это или?

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

У меня есть довольно ужасная процедура, которая генерирует один случайный массив:

const getValues = function () {

  const results = [];
  const remaining = new Set(alphabet);
  const probabilities = [0.6, 0.2, 0.1, 0.1];

  for(let i = 0; i < alphabet.length; i++){

    const r  = Math.random();
    const letter = alphabet[i];

    if(r < probabilities[i] && remaining.has(letter)){
      results.push(letter);
      remaining.delete(letter);
    }
    else{
      const rand = Math.floor(Math.random()*remaining.size);
      const x = Array.from(remaining)[rand];
      remaining.delete(x);
      results.push(x);
    }

  }

   return results;
};

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

Вот пример выходных данных, которые я ищу:

[ [ 'd', 'b', 'a', 'c' ],
  [ 'a', 'b', 'c', 'd' ],
  [ 'a', 'd', 'b', 'c' ],
  [ 'd', 'b', 'a', 'c' ],
  [ 'b', 'c', 'a', 'd' ],
  [ 'a', 'b', 'c', 'd' ],
  [ 'd', 'b', 'c', 'a' ],
  [ 'c', 'd', 'a', 'b' ],
  [ 'd', 'b', 'a', 'c' ],
  [ 'a', 'b', 'c', 'd' ] ]

, если вы сгенерировалидостаточно данных, которые не соответствуют желаемому заказу / распределению.

Answer 1

Я думаю, что проблема плохо сформулирована.

Как написано, A должно быть на месте 1 с 60% вероятностью , B на месте 2 с 20%, C и Dна местах 3 или 4 с 10% каждый.Нет распределения, которое удовлетворяло бы этим вероятностям критериям, поэтому ни один алгоритм не может его создать: если в 60% случаев A находится на месте 1, то C или D должны быть на местах 3 или 4 в этих 60%, так что это намного выше требуемой 10% вероятности .

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

Полагаю, 60% для A и 20% для B следует понимать не как вероятность , а как разновидность популярности .Но это не может быть просто кворум для каждого кандидата, потому что в процессе голосования A завершится на месте 1 в 100% случаев.

Итак, давайте предположим, что процесс голосования с некоторой случайностью включал, что позволяет A закончитьна месте 1 с вероятностью 60% , B на месте 1 (!) с вероятностью 20% и т. д. Затем мы можем реализовать это, используя взвешенный случайный выбор для места 1.

Как продолжить с мест 2..n?Мы просто сохраняем вес и удаляем кандидата, который уже был выбран.Если один из других кандидатов выбрал 1-е место, это приведет к концу с высокой вероятностью на 2-м месте, что, я думаю, имеет смысл.

Answer 2

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

В результате вы получите почти требуемый результат, как вы видите в counts элементов и их окончательном индексе.

const
    getIndex = (prob) => prob.findIndex((r => p => r < p || (r -= p, false))(Math.random())),
    normalized = array => {
        var sum = array.reduce((a, b) => a + b, 0);
        return array.map(v => v / sum);
    };

var items = ['a', 'b', 'c', 'd'],
    probabilities = [0.6, 0.2, 0.1, 0.1],
    counts = { a: { 0: 0, 1: 0, 2: 0, 3: 0 }, b: { 0: 0, 1: 0, 2: 0, 3: 0 }, c: { 0: 0, 1: 0, 2: 0, 3: 0 }, d: { 0: 0, 1: 0, 2: 0, 3: 0 } },
    l = 100,
    index,
    result = [], 
    subP,
    subI,
    temp;

while (l--) {
    temp = [];
    subP = probabilities.slice();
    subI = items.slice();
    while (subP.length) {
        sum = subP.reduce
        index = getIndex(normalized(subP));
        temp.push(subI[index]);
        subI.splice(index, 1);
        subP.splice(index, 1);
    }
    result.push(temp);
}

console.log(result.map(a => a.join()));

result.forEach(a => a.forEach((v, i) => counts[v][i]++));

console.log(counts);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 3

Вы можете отсортировать их, используя функцию перемешивания следующим образом:

const candidates = [
  { name: "a", weight: 6 },
  { name: "b", weight: 2 },
  { name: "c", weight: 1 },
  { name: "d", weight: 1 }
];

const randomShuffleFn = () => Math.random() - .5;

const shuffleFn = (candidateA, candidateB) =>
  Math.random() * (candidateB.weight + candidateA.weight) - candidateA.weight;

console.log([...candidates].sort(randomShuffleFn).sort(shuffleFn));

ОК, это не совсем то же самое, но я думаю, что с помощью настройки весов вы можете получить требуемое распределение (как есть, Aвыигрывает более 60% раз).

Answer 4

Это может помочь вам, например, пример для вашей ситуации из https://github.com/substack/node-deck

Пример

 const normalize = function (weights) {
	if (typeof weights !== 'object' || Array.isArray(weights)) {
		throw 'Not an object'
	}

	let keys = Object.keys(weights);
	if (keys.length === 0) return undefined;

	let total = keys.reduce(function (sum, key) {
		let x = weights[key];
		if (x < 0) {
			throw new Error('Negative weight encountered at key ' + key);
		}
		else if (typeof x !== 'number') {
			throw new TypeError('Number expected, got ' + typeof x);
		}
		else {
			return sum + x;
		}
	}, 0);

	return total === 1
		? weights
		: keys.reduce(function (acc, key) {
			acc[key] = weights[key] / total;
			return acc;
		}, {})
		;
};

const pick = function (xs) {
	if (Array.isArray(xs)) {
		return xs[Math.floor(Math.random() * xs.length)];
	}
	else if (typeof xs === 'object') {
		// Weighted Sample
		let weights = normalize(xs);
		if (!weights) return undefined;

		var n = Math.random();
		var threshold = 0;
		var keys = Object.keys(weights);

		for (let i = 0; i < keys.length; i++) {
			threshold += weights[keys[i]];
			if (n < threshold) return keys[i];
		}
		throw new Error('Exceeded threshold. Something is very wrong.');
	}
	else {
		throw new TypeError('Must be an Array or an object');
	}
};

const shuffle = function (xs) {
	if (Array.isArray(xs)) {
		let res = xs.slice();
		for (var i = res.length - 1; i >= 0; i--) {
			var n = Math.floor(Math.random() * i);
			var t = res[i];
			res[i] = res[n];
			res[n] = t;
		}
		return res;
	}
	else if (typeof xs === 'object') {
		// Weighted
		let weights = Object.keys(xs).reduce(function (acc, key) {
			acc[key] = xs[key];
			return acc;
		}, {});

		let ret = [];

		while (Object.keys(weights).length > 0) {
			let key = pick(weights);
			delete weights[key];
			ret.push(key);
		}

		return ret;
	}
	else {
		throw new TypeError('Must be an Array or an object');
	}
};


let results = [];
for (let i = 0; i < 100; i++) {
	let weighted = shuffle({
		a : 60, 
		b : 20, 
		c : 10, 
		d : 10, // or .1, 100, 1000
	});
	results.push(weighted);
}
console.log(results);