Алгоритм построение композиции множества

@ivansv04 · Регистрация: 08.06.2015

Студворк — интернет-сервис помощи студентам

Здравствуйте, помогите,пожалуйста, построить алгоритм построения всех композиций конечного множества с увеличение количества блоков

@Shamil1 · 13.06.2015, 19:22

Сообщение от ivansv04

Знаете как организовать весь перебор таких н значных чисел по модулю н, чтобы количество одинаковых цыфр уменьшалось?

Знаю

.
Перебрать k-ичные n-разрядные числа, в которых присутствует ровно k разных цифр (то есть, все) для k от 1 до n.

@ivansv04 · 13.06.2015, 19:30 **[ТС]**

Сообщение от Shamil1

Перебрать k-ичные n-разрядные числа, в которых присутствует ровно k разных цифр (то есть, все) для k от 1 до n.

Я имел ввиду, такой алгоритм перебора : 000
111
222
100
010
001
200
020
002
110
011
101
202
220
022
123
132
132
213
231
312
321

@Shamil1 · 13.06.2015, 19:49

А вот код, который это делает:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void Solve2(int n)
{
    var sets = new List<int>[n];
    for(int i = 0; i < sets.Length; i++) 
        sets[i] = new List<int>();
    var digits = new int[n];
    
    for(int k = 1; k <= n; k++)
        Solve2(n, k, sets, digits);
}
 
void Solve2(int n, int k, List<int>[] sets, int[] digits)
{
    for(int i = 0; i < digits.Length; i++)
        digits[i] = 0;
    do
    {
        if(digits.Distinct().Count() != k)
            continue;
            
        for(int i = 0; i < k; i++) 
            sets[i].Clear();
            
        for(int j = 0; j < digits.Length; j++)
        {
            int i = digits[j];
            sets[i].Add(j+1);
        }
        
        Console.WriteLine("[" + string.Join(",", sets.Take(k).Select(x => "{" + string.Join(",", x.Select(y => y.ToString()).ToArray()) + "}").ToArray()) + "]");
    } while(Next(digits, k-1));
}

Добавлено через 4 минуты

Сообщение от ivansv04

Я имел ввиду, такой алгоритм перебора : 000
111

111 нам не нужен, так как в нём есть "разрыв" (нет цифры "0" и есть цифра "1", 1 > 0). Фактически, это та же композиция, что и 000 (то есть, дубль).

Если Вы выкинете из моего кода все манипуляции с sets и вместо sets будете выводить digits, то получите код, который перебирает числа.

@ivansv04 · 13.06.2015, 20:06 **[ТС]**

Сообщение от Shamil1

111 нам не нужен, так как в нём есть "разрыв"

Ну да, я в курсе, я просто все выписал

Спасибо

Добавлено через 12 минут
Только оно не строит для k=2 или я туплю

Добавлено через 2 минуты
Прошу прошения, баловался с кодом и не забыл что исправлял, теперь всё отлично

@Shamil1 · 14.06.2015, 17:31

Сообщение от XRuZzz

моё скромное, независимое решение задачки на Haskell:

Мой вариант:

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import Data.List
import Data.Functor
import Control.Applicative
import Data.Function (on)
 
solve :: (Num b, Enum b) => Int -> [[[b]]]
solve n = concat $ map solve1 [1..n]
    where solve1 k = map f2 .filter ((==k) .length) .map f1 .unfoldr (next $ k-1) .Just $ replicate n 0
          f1 = groupBy ((==) `on` snd) .sortBy (compare `on` snd) .zip [1..]
          f2 = map (map fst)
 
next :: (Num a, Ord a) => a -> Maybe [a] -> Maybe ([a], Maybe [a])
next max a = (\x -> (x, next1 x)) <$> a
    where next1 []     = Nothing
          next1 (x:xs) = if x == max then (0:) <$> (next1 xs) else Just ((x+1):xs)
 
main = do
    let res = solve 3
    print $ length res
    putStr . unlines . map show $ res

Для n = 5 выполняется мгновенно.

Добавлено через 12 часов 5 минут
Немного изменил код, чтобы он больше соответствовал коду на C# и (как мне кажется) стал более читаемым:

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import Data.List (unfoldr, groupBy, sortBy)
import Data.Functor ((<$>))
import Control.Applicative ((<*>))
import Data.Function (on)
 
solve :: (Num b, Enum b) => Int -> [[[b]]]
solve n = concat $ map (solve1 $ replicate n 0) [1..n]
    where solve1 ds k = map (map (map fst)) 
                       .filter ((==k) .length) 
                       .map (groupBy ((==) `on` snd) .sortBy (compare `on` snd) .zip [1..]) 
                       .unfoldr ((,) <*> (next $ k-1) <$>) $ Just ds
 
next :: (Num a, Ord a) => a -> [a] -> Maybe [a]
next _ []     = Nothing
next max (x:xs) = if x == max then (0:) <$> (next max xs) else Just ((x+1):xs)
          
main = do
    let res = solve 3
    print $ length res
    putStr . unlines . map show $ res

Теперь next и solve1 делают то же, что аналогичные функции из C# кода.

Новые блоги и статьи Все статьи Все блоги /
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .

@ivansv04 0 / 0 / 0 Регистрация: 08.06.2015 Сообщений: 14

	Алгоритм построение композиции множества 08.06.2015, 21:16. Показов 2327. Ответов 24 Метки нет (Все метки) Здравствуйте, помогите,пожалуйста, построить алгоритм построения всех композиций конечного множества с увеличение количества блоков 0