23.12.2020, 01:49
|
Новичок на форуме
|
|
Регистрация: 04.12.2020
Сообщений: 8
|
|
Случайное разбиение множества
Здравствуйте, форумчане! Второй день бьюсь с одной проблемой, облазил половину форумов: как реализовать на 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} }; //.....
! Перестановка элементов внутри подмножества не будет разбиением !
Нужно, чтобы написанная функция случайным образом разбивала множество, полученное как аргумент этой функции.
Спасибо, большое!
|
|
23.12.2020, 07:48
|
|
Профессор
|
|
Регистрация: 03.02.2020
Сообщений: 2,745
|
|
<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>
Последний раз редактировалось voraa, 23.12.2020 в 09:49.
|
|
23.12.2020, 09:34
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,109
|
|
<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>
Последний раз редактировалось рони, 23.12.2020 в 10:12.
Причина: добавил sort
|
|
23.12.2020, 09:44
|
|
Профессор
|
|
Регистрация: 03.02.2020
Сообщений: 2,745
|
|
рони,
Чего то не то.
У меня получился такой результат
[[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
Сообщение от vsco89
|
! Перестановка элементов внутри подмножества не будет разбиением !
|
|
|
23.12.2020, 10:11
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,109
|
|
voraa,
это никак не противоречит условию задания.
(+добавил сортировку)
|
|
23.12.2020, 10:35
|
Новичок на форуме
|
|
Регистрация: 04.12.2020
Сообщений: 8
|
|
Спасибо огромное!
|
|
23.12.2020, 11:22
|
|
Профессор
|
|
Регистрация: 03.02.2020
Сообщений: 2,745
|
|
рони,
В таких задачах (на случайность, на вероятность) меня всегда смущает вопрос, а на сколько будет сохраняться случайность распределения и плотность вероятности.
В этой задаче существует 126 способов разбиения.
А случаев попадания 1 элемента в первое множество - 7.
Т.е вероятность такого исхода всего 7/126 = 5.5%
В твоем решении ты сразу определяешь, что в первое множество 1 элемент попадет с вероятностью 1/6 = 16.7 %
По мне такой результат нельзя назвать достаточно случайным
|
|
23.12.2020, 14:10
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,109
|
|
voraa,
расчёты сомнительны, не вижу условий для перекоса, вероятность одинакова для всех комбинаций,
и нет череды бесполезных циклов.
|
|
23.12.2020, 15:00
|
|
Профессор
|
|
Регистрация: 03.02.2020
Сообщений: 2,745
|
|
Сообщение от рони
|
не вижу условий для перекоса, вероятность одинакова для всех комбинаций,
|
Совсем не так!
На большом количестве тестов варианты, например,
[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, 23.12.2020 в 15:13.
|
|
23.12.2020, 15:35
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,109
|
|
voraa,
хорошо, но я не понимаю где ошибка, ваши объяснения(#7) ,я увы, не осилил.
|
|
|
|