|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Valentin Kononov 2:5035/38.9 27 Dec 2001 23:24:35
To : Nail Zakirov
Subject : re: разбиение множества
--------------------------------------------------------------------------------
Чет Дек 27 2001 08:46, you wrote to All:
NZ> Подскажите plz алгоритм разбивающий множество из n элементов на k
NZ> подмножеств. Hапример имеем: {1,2,3,4} n = 4, k = 2 получаем
NZ> : {{1,2,3},{4}} {{1,2,4},{3}} {{1,3,4},{2}} {{1,2},{3,4}} {{1,3},{2,4}}
NZ> {{1 ,4},{2,3}} {{1},{2,3,4}}
Можно в цикле от 1 до (2^n)-1 считать количество R(i) единиц в двоичном
представлении переменной цикла i и, если R(i)<=n-k+1, рекурсивно переходить
к разбиению множества из n-R(i) элементов на k-1 подмножество. Если k-1=1,
то расставляем элементы по подмножествам - в 1-е войдут элементы,
соответствующие единицам в i1, во 2-е - те из оставшихся элементов, которым
единички достались в i2 и т.д.; в k-е - все оставшиеся.
Hапример, если i1=5, i2=2, то начало разбиения такое: {(1,3),(4)...
Однако, очевидно, что такой алгоритм будет постоянно повторять одни и те же
циклы. Поэтому логично запустить его в обратном порядке:
от 2 до n-k+1 элементов разбить на 2 подмножества;
от 3 до n-k+2 -->>-- на 3 подмножества,
и т.д., используя каждый раз те разбиения, которые были получены на
предыдущем шаге. Разумеется, их надо куда-то записывать.
Да, чуть не забыл - так будут повторяться одинаковые разбиения с
перестановкой подмножеств. Hо это даже проще: достаточно в каждое
подмножество автоматически записывать первый свободный элемент.
Цикл надо делать от 0 до (2^(n-1))-1, R(i)<=n-k
В том примере будет {(1,2,4),(3,6)...
NZ> хотелось бы еще получить только те варианты в
NZ> которых кол-во подмножеств имеющих одинаковое кол-во элементов было
NZ> максимально. В данном случае это: {{1,2},{3,4}} {{1,3},{2,4}}
NZ> {{1,4},{2,3}}
Если остальные подмножества вообще не нужны, наложи соответствующее
ограничение на R(i).
С уважением, Valentin
--- * ---
* Origin: Пейте соки и нектары GSM (Kursk 2:5035/38.9)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
re: разбиение множества 
