Случайное разбиение множества
Здравствуйте, форумчане! Второй день бьюсь с одной проблемой, облазил половину форумов: как реализовать на JS случайное разбиение множества (p.s. разбиение R(A) - непустые непересекающиеся подмножества множества А, в объединении дающие А)
Пример: A = {1,2,3,4} -> Вариант 1: R1(A) = { {1},{2,3,4} }; Вариант 2: R2(A) = { {1,2},{3,4} }; Вариант 3: R3(A) = { {1,3},{2,4} }; Вариант 4: R4(A) = { {1,2,3},{4} }; Вариант 5: R5(A) = { {2},{1,3,4} }; Вариант 6: R6(A) = { {3},{1,2,4} }; //..... ! Перестановка элементов внутри подмножества не будет разбиением ! Нужно, чтобы написанная функция случайным образом разбивала множество, полученное как аргумент этой функции. Спасибо, большое! |
<pre>
<script>
function splitSet (set) {
let sub1, sub2;
do {
sub1 = [];
sub2 = [];
for(let i = 0; i < set.length; i++) {
(Math.random()<0.5? sub1 : sub2).push(set[i]);
}
} while (sub1.length == 0 || sub2.length == 0);
return [sub1, sub2];
}
for (let i = 0; i < 25; i++) {
let [s1, s2] = splitSet([1,2,3,4,5,6,7])
document.write(`[[${s1}],[${s2}]]<br>`)
}
</script>
</pre>
|
:) :write:
<pre>
<script>
function splitSet (set) {
const random = a => Math.trunc(Math.random() * a),
sort = (a, b) => a - b;
let {length} = set = set.slice(0), ar = [], n = 1 + random(length - 1);
for (let i = 0; i < n; i++) {
let k = random(length - i);
ar.push(...set.splice(k, 1))
}
return [set, ar.sort(sort)];
}
for (let i = 0; i < 25; i++) {
let [s1, s2] = splitSet([1,2,3,4,5,6,7])
document.write(`[[${s1}],[${s2}]]<br>`)
}
</script>
</pre>
|
рони,
Чего то не то. У меня получился такой результат [[1,3],[6,7,2,5,4]] [[7],[6,1,4,3,2,5]] [[2,3,4,7],[6,5,1]] [[3,5,6],[4,7,1,2]] [[1,3,6,7],[2,4,5]] [[4,5,6,7],[1,3,2]] [[2],[6,7,5,3,4,1]] [[1,2,5,7],[4,3,6]] [[6],[4,2,1,7,3,5]] [[2,3,4,6,7],[1,5]] [[1,3],[4,6,7,5,2]] [[5,7],[1,2,4,6,3]] [[1,3,4,5,6,7],[2]] [[2,3,6],[4,5,1,7]] [[1,2,3,5,7],[4,6]] [[1,6],[3,2,5,4,7]] [[1,2],[4,6,5,7,3]] [[7],[1,4,6,5,2,3]] [[4,5],[7,2,6,1,3]] [[1,3,4,5,6,7],[2]] [[4],[1,2,3,5,7,6]] [[4,7],[1,3,6,5,2]] [[3,5],[6,7,4,1,2]] [[1,5],[6,7,3,4,2]] [[1,4,7],[6,2,3,5]] Строки 2 и 18 Цитата:
|
voraa,
это никак не противоречит условию задания. (+добавил сортировку) |
Спасибо огромное!
|
рони,
В таких задачах (на случайность, на вероятность) меня всегда смущает вопрос, а на сколько будет сохраняться случайность распределения и плотность вероятности. В этой задаче существует 126 способов разбиения. А случаев попадания 1 элемента в первое множество - 7. Т.е вероятность такого исхода всего 7/126 = 5.5% В твоем решении ты сразу определяешь, что в первое множество 1 элемент попадет с вероятностью 1/6 = 16.7 % По мне такой результат нельзя назвать достаточно случайным |
voraa,
расчёты сомнительны, не вижу условий для перекоса, вероятность одинакова для всех комбинаций, и нет череды бесполезных циклов. |
Цитата:
На большом количестве тестов варианты, например, [1] [2,3,4,5,6,7] и [1,2] [3,4,5,6,7] Должны встречаться примерно одинаковое количество раз Теперь смотрим
<pre>
<script>
function splitSet (set) {
const random = a => Math.trunc(Math.random() * a);
let {length} = set = set.slice(0), ar = [], n = 1 + random(length - 1);
for (let i = 0; i < n; i++) {
let k = random(length - i);
ar.push(...set.splice(k, 1))
}
return [set, ar];
}
let v1 =0;
let v2=0;
for (let i = 0; i < 100_000; i++) {
let [s1, s2] = splitSet([1,2,3,4,5,6,7])
//document.write(`[[${s1}],[${s2}]], ${s1.length}, ${s2.length}<br>`)
if (s1.length == 1 && s1[0] ==1) v1++
if (s1.length == 2 && s1[0] ==1 && s1[1] == 2) v2++
}
document.write(`[1] - ${v1} [1,2] - ${v2}`)
</script>
</pre>
Цитата:
Кроме случаев что все элементы оказались в одном множестве. Для 7 элементов - вероятность 1/64. |
voraa,
хорошо, но я не понимаю где ошибка, ваши объяснения(#7) ,я увы, не осилил. |
| Часовой пояс GMT +3, время: 09:57. |