Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 23.12.2020, 01:49
Новичок на форуме
Отправить личное сообщение для vsco89 Посмотреть профиль Найти все сообщения от vsco89
 
Регистрация: 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} }; //.....

! Перестановка элементов внутри подмножества не будет разбиением !

Нужно, чтобы написанная функция случайным образом разбивала множество, полученное как аргумент этой функции.

Спасибо, большое!
Ответить с цитированием
  #2 (permalink)  
Старый 23.12.2020, 07:48
Аватар для voraa
Профессор
Отправить личное сообщение для voraa Посмотреть профиль Найти все сообщения от voraa
 
Регистрация: 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.
Ответить с цитированием
  #3 (permalink)  
Старый 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
Ответить с цитированием
  #4 (permalink)  
Старый 23.12.2020, 09:44
Аватар для voraa
Профессор
Отправить личное сообщение для voraa Посмотреть профиль Найти все сообщения от voraa
 
Регистрация: 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
! Перестановка элементов внутри подмножества не будет разбиением !
Ответить с цитированием
  #5 (permalink)  
Старый 23.12.2020, 10:11
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,109

voraa,
это никак не противоречит условию задания.
(+добавил сортировку)
Ответить с цитированием
  #6 (permalink)  
Старый 23.12.2020, 10:35
Новичок на форуме
Отправить личное сообщение для vsco89 Посмотреть профиль Найти все сообщения от vsco89
 
Регистрация: 04.12.2020
Сообщений: 8

Спасибо огромное!
Ответить с цитированием
  #7 (permalink)  
Старый 23.12.2020, 11:22
Аватар для voraa
Профессор
Отправить личное сообщение для voraa Посмотреть профиль Найти все сообщения от voraa
 
Регистрация: 03.02.2020
Сообщений: 2,745

рони,
В таких задачах (на случайность, на вероятность) меня всегда смущает вопрос, а на сколько будет сохраняться случайность распределения и плотность вероятности.
В этой задаче существует 126 способов разбиения.
А случаев попадания 1 элемента в первое множество - 7.
Т.е вероятность такого исхода всего 7/126 = 5.5%
В твоем решении ты сразу определяешь, что в первое множество 1 элемент попадет с вероятностью 1/6 = 16.7 %
По мне такой результат нельзя назвать достаточно случайным
Ответить с цитированием
  #8 (permalink)  
Старый 23.12.2020, 14:10
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,109

voraa,
расчёты сомнительны, не вижу условий для перекоса, вероятность одинакова для всех комбинаций,
и нет череды бесполезных циклов.
Ответить с цитированием
  #9 (permalink)  
Старый 23.12.2020, 15:00
Аватар для voraa
Профессор
Отправить личное сообщение для voraa Посмотреть профиль Найти все сообщения от voraa
 
Регистрация: 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.
Ответить с цитированием
  #10 (permalink)  
Старый 23.12.2020, 15:35
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,109

voraa,
хорошо, но я не понимаю где ошибка, ваши объяснения(#7) ,я увы, не осилил.
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Выбор случайного количества элементов из множества Black_Star jQuery 6 23.10.2016 21:00
случайное число в span ultrahomie Общие вопросы Javascript 2 16.04.2016 14:29
Случайное число при перезагрузке страницы logi Общие вопросы Javascript 8 21.10.2011 15:47
Вывести случайное число от 1 до 20 beliykot Events/DOM/Window 12 29.08.2011 13:22
Случайное число в цикле sanhai Events/DOM/Window 15 11.04.2010 06:12