Случайное разбиение множества
Здравствуйте, форумчане! Второй день бьюсь с одной проблемой, облазил половину форумов: как реализовать на 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) ,я увы, не осилил. |
Ошибка в самом методе.
Вот это n = 1 + random(length - 1); Сразу говорит, что количество случаев, когда в первом множестве 1 элемент, 2 элемента, 3 элемента - одинаковое. Но это не так. Всего вариантов разбиения 126. (На самом деле 63, если считать, что s1=[1,2] и s2 = [1,2] в принципе одно и тоже разбиение) (Это комбинаторика, которую я, разумеется не помню, просто погуглил https://ru.wikipedia.org/wiki/%D0%A7...%D0%B4%D0 %B0) Но на самом деле вариантов выбора 1 элемента - 7 А вариантов выбора 2 элементов - 6+5+4+3+2+1 = 21 |
voraa,
спасибо подумаю. |
voraa,
мысли вслух ... :)
<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, m = 1/((length - 1)/2);
for (let i = 1; i < length; i++) {
Math.random() > m || n++;
}
for (let i = 0; i < n; i++) {
let k = random(length - i);
ar.push(...set.splice(k, 1))
}
ar.sort(sort);
return ar[0] == 1 ? [ar, set] :[set, ar];
}
let v1 = 0;
let v2 = 0;
let v3 = 0;
let v4 = 0;
let v5 = 0
for (let i = 0; i < 63000; 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++
if (s1.length == 3 && s1[0] ==1 && s1[1] == 2 && s1[2] == 3) v3++
if (s1.length == 4 && s1[0] ==1 && s1[1] == 2 && s1[2] == 3 && s1[3] == 4) v4++
if (s1.length == 5 && s1[0] ==1 && s1[1] == 2 && s1[2] == 3 && s1[3] == 4 && s1[4] == 5) v5++
}
document.write(`[1] - ${v1} [1,2] - ${v2} [1,2,3] - ${v3} [1,2,3,4] - ${v4} [1,2,3,4,5] - ${v5}`)
</script>
</pre>
|
Цитата:
P.S. формулу написал, но если интересно напишите свой вариант. |
разбить массив на две части
:):) :)
<pre>
<script>
const randomNetto = length => {
let ar = [],
sum = 0;
for (let i = 1; i <= length / 2; i++) {
var n = 1,
j = length;
for (let k = i; k; k--) {
n *= j--;
n /= k;
}
sum += n;
ar.push(sum);
}
ar = ar.map(a => a / sum);
return random => {
let len = 0;
for (let k of ar) {
len++;
if (random < k) break;
}
return len
}
}
function splitSet(set) {
const random = a => Math.trunc(Math.random() * a),
sort = (a, b) => a - b;
let {
length
} = set = set.slice(0), ar = [], count = randomNetto(length), n = count(Math.random());
for (let i = 0; i < n; i++) {
let k = random(length - i);
ar.push(...set.splice(k, 1))
}
ar.sort(sort);
return ar[0] == 1 ? [ar, set] : [set, ar];
}
let v1 = 0;
let v2 = 0;
let v3 = 0;
let v4 = 0;
let v5 = 0
for (let i = 0; i < 63000; 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++
if (s1.length == 3 && s1[0] == 1 && s1[1] == 2 && s1[2] == 3) v3++
if (s1.length == 4 && s1[0] == 1 && s1[1] == 2 && s1[2] == 3 && s1[3] == 4) v4++
if (s1.length == 5 && s1[0] == 1 && s1[1] == 2 && s1[2] == 3 && s1[3] == 4 && s1[4] == 5) v5++
}
document.write(`[1] - ${v1} [1,2] - ${v2} [1,2,3] - ${v3} [1,2,3,4] - ${v4} [1,2,3,4,5] - ${v5}`)
</script>
</pre>
|
Цитата:
Количество сочетаний из n элементов по k (т.е сколькими способами можно выбрать k элементов из n) C(n,k) = n!/ (k! * (n-k)!) Сумма C(n,k) k=2...n-1 дает количество вариантов разбиения множества из n элементов на два непустых подмножества. Отсюда получаем такой счет
<pre>
<script>
// Формирует массив из n элементов
// a[k] - количество вариантов выбора k элементов из n
// a[0] и a[n] = 1
// и считаем сумму a[i] (i=1...n-1)
const nsel = (n) => {
let a = [1, n]; s=n
for (let i=2; i<=n-1; i++) {
a[i] = a[i-1]*(n-i+1)/i
s+=a[i]
}
a[n] = 1;
return [a, s]
}
for (let k=3; k<=10; k++) {
let [a,s] = nsel(k)
document.write(`${k} : ${a} sum = ${s}<br>`)
}
</script>
</pre>
Про лишние циклы. Я все равно убежден, что [...x] и x.sort() (так же как и forEach, map, reduce...) это все равно циклы. Хоть они может быть (хотя не факт) и выполняются чуть быстрее, чем явно написанный, но на производительности сказываются. |
voraa,
спасибо!:thanks: |
:write:
<pre>
<script>
const randomNetto = length => {
let n = length, ar = [n], sum = n, k = n;
for (let i = 2; i < length; i++) {
n *= --k;
n /= i;
sum += n;
ar.push(sum);
}
ar = ar.map(a => a / sum);
return random => {
let len = 0;
for (let k of ar) {
len++;
if (random < k) break;
}
return len
}
}
function splitSet(set) {
const random = a => Math.trunc(Math.random() * a),
sort = (a, b) => a - b;
let {length} = set = set.slice(0),
ar = [],
count = randomNetto(length),
n = count(Math.random());
for (let i = 0; i < n; i++) {
let k = random(length - i);
ar.push(...set.splice(k, 1))
}
ar.sort(sort);
return ar[0] == 1 ? [ar, set] : [set, ar];
}
let obj = {};
for (let i = 0; i < 63000; i++) {
let [s1, s2] = splitSet([1, 2, 3, 4, 5, 6, 7])
obj[[s1]] = (obj[[s1]] >> 0) + 1;
obj[[s2]] = (obj[[s2]] >> 0) + 1;
}
document.write(JSON.stringify(obj, "", " "))
obj = {};
for (let i = 0; i < 15500; i++) {
let [s1, s2] = splitSet([1, 2, 3, 4, 5])
obj[[s1]] = (obj[[s1]] >> 0) + 1;
obj[[s2]] = (obj[[s2]] >> 0) + 1;
}
document.write(JSON.stringify(obj, "", " "))
</script>
</pre>
|
Ну завершающий тест :)
<pre>
<script>
let t0, t1;
let nloop=0;
function splitSet (set) {
let sub1, sub2;
do {
nloop++;
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];
}
let obj = {};
t0 = performance.now()
for (let i = 0; i < 100_000; i++) {
let [s1, s2] = splitSet([1, 2, 3, 4, 5, 6, 7])
obj[[s1]] = (obj[[s1]] >> 0) + 1;
obj[[s2]] = (obj[[s2]] >> 0) + 1;
}
t1 = performance.now()
document.write(JSON.stringify(obj, "", " "))
document.write(`<br>Time ${t1-t0} nloop ${nloop}`)
document.write('<br><br>')
const randomNetto = length => {
let n = length, ar = [n], sum = n, k = n;
for (let i = 2; i < length; i++) {
n *= --k;
n /= i;
sum += n;
ar.push(sum);
}
ar = ar.map(a => a / sum);
return random => {
let len = 0;
for (let k of ar) {
len++;
if (random < k) break;
}
return len
}
}
function splitSet1(set) {
const random = a => Math.trunc(Math.random() * a),
sort = (a, b) => a - b;
let {length} = set = set.slice(0),
ar = [],
count = randomNetto(length),
n = count(Math.random());
for (let i = 0; i < n; i++) {
let k = random(length - i);
ar.push(...set.splice(k, 1))
}
ar.sort(sort);
return ar[0] == 1 ? [ar, set] : [set, ar];
}
obj = {};
t0 = performance.now()
for (let i = 0; i < 100_000; i++) {
let [s1, s2] = splitSet1([1, 2, 3, 4, 5, 6, 7])
obj[[s1]] = (obj[[s1]] >> 0) + 1;
obj[[s2]] = (obj[[s2]] >> 0) + 1;
}
t1 = performance.now()
document.write(JSON.stringify(obj, "", " "))
document.write(`<br>Time ${t1-t0}`)
</script>
</pre>
Примерно 1500 "лишних" циклов. Как я и писал (пост #9) вероятность 1/64 = 1.56% |
voraa,
:lol: |
В посте #2 этого топика максимально простое и очевидное решение. Я правильно понимаю, что далее дискуссия ведется по поводу строки 11, из-за которой это решение теоретически может работать бесконечно долго?
|
Alexandroppolus,
дискуссии не было, полностью согласен что #2 простое решение и чем больше начальный массив, тем меньше "лишних" циклов вероятность, мне было интересно решить это как-то иначе. |
Я покрутил алгоритм из поста #2 со множеством из 20 элементов 1 000 000 раз.
Получил 2 лишних цикла. Как и положено по теории, с вероятностью 1/2^20 получаем последовательность из 20 случайных чисел, каждое из которых < 0.5 или >=0.5 Годный датчик случайных чисел |
чисто ради прикола докрутил #2, чтобы не было вероятности лишнего цикла
function splitSet(set) {
const subs = [[], []];
for(let i = 0; i < set.length; i++) {
subs[Math.round(Math.random())].push(set[i]);
}
if (!subs[0].length || !subs[1].length) {
const srcIndex = subs[0].length ? 0 : 1;
const index = Math.floor(Math.random() * set.length);
subs[1 - srcIndex] = subs[srcIndex].splice(index, 1);
}
return subs;
}
for (let i = 0; i < 25; i++) {
let [s1, s2] = splitSet([1,2,3,4,5,6,7]);
console.log(s1, s2);
}
суть: если в одном из массивов пусто, из другого перекидываем случайно выбранный элемент. Это сохраняет равные шансы для каждого из элементов попасть в любой массив. Можно было бы перекидывать, допустим, первый элемент. Но тогда немного уменьшились бы его шансы оказаться вместе со вторым, хотя по отдельности и у первого, и у второго одинаковые шансы быть в любом из массивов. Этот "парадокс" я пока не осмыслил. |
Цитата:
Да, задачка хитрая) |
| Часовой пояс GMT +3, время: 03:25. |