Случайное разбиение множества

[voraa]

Ошибка в самом методе.
Вот это
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>

[рони]

Но на самом деле вариантов выбора 1 элемента - 7
А вариантов выбора 2 элементов - 6+5+4+3+2+1 = 21

вы не могли бы написать формулу на js, по которой можно получить 7, 21, 63?
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>

[voraa]

вы не могли бы написать формулу на js, по которой можно получить 7, 21, 63?
P.S. формулу написал, но если интересно напишите свой вариант.

Математическая формула известна (вспоминаем комбинаторику )
Количество сочетаний из 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,
спасибо!

[рони]

<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>

[voraa]

Ну завершающий тест

<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,