|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vitaly Slobodskoy 2:5015/128.22 28 Dec 2001 00:31:33
To : Nail Zakirov
Subject : RE:разбиение множества
--------------------------------------------------------------------------------
NZ> Подскажите plz алгоритм разбивающий множество из n элементов на k
NZ> подмножеств. Hапример имеем: {1,2,3,4} n = 4, k = 2
NZ> получаем :
NZ> {{1,2,3},{4}}
NZ> {{1,2,4},{3}}
NZ> {{1,3,4},{2}}
NZ> {{1,2},{3,4}}
NZ> {{1,3},{2,4}}
NZ> {{1,4},{2,3}}
NZ> {{1},{2,3,4}}
Фиксируешь один элемент (первый), а для всех остальных генеришь стандартный
алгоритм разбиения n-элементного множ-ва на k-подмножеств (если ты не знаешь и
его, то могу объяснить). Hапример, будешь генерить его для какой-нить маски -
массива с элементами, значения которых соответствуют принадлежности элемента
соответствующему множ-ву. Все это для n-1 элементов - первый всегда имеет в
маске значение 0 (или 1 - для первого множ-ва) и не входит в генерацию. Теперь
составляешь ответ по маске. Все. Кстати, ты не сказал о том, могут ли множ-ва
быть пустыми?? Судя по примеру, нет, тогда тебе еще нужно сделать проверку
перед выводои ответа на то, чтобы все множ-ва были непустыми.
NZ> хотелось бы еще получить только те варианты в которых кол-во подмножеств
NZ> имеющих одинаковое кол-во элементов было максимально.
NZ> В данном случае это:
NZ> {{1,2},{3,4}}
NZ> {{1,3},{2,4}}
NZ> {{1,4},{2,3}}
Тут максимум для кол-ва элементов будет n div k. Посему выбираешь из всех
наборов только те наборы, где кол-во таких подмножеств (с таким кол-вом
элементов) было равно n-(n mod k). Вроде так, еси не наврал :)))
ПОКА!
--- F.I.P.S./32 v1.0r W95/NT [M]
* Origin: Жить вредно - от этого умирают! (2:5015/128.22)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
