Как вывести все подмножества множества A?

@Pufik11 · Регистрация: 15.12.2019

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

Допустим есть 1,2,3

Должно вывести:
1
1,2
1,2,3
1,3
2
2,3
3

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
            Console.WriteLine("Введите кол-во элементов:" );
            int y = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("Введите Ваши элементы множества: ");
            double[] mas= new double[y];
            for (int j = 0; j < y; j++)
            {
                mas[j] = Convert.ToInt32(Console.ReadLine());
            }
 
            Console.WriteLine();
 
            Console.Write("Множество: ");
            for (int j = 0; j < y; j++)
            {
                Console.Write(mas[j] + " ");
            }
            Console.WriteLine();
            Console.Write("Подмножества: ");
            Console.WriteLine();

Какой алгоритм нужен дальше?

@amr-now · 21.03.2020, 10:22

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
33
34
35
36
37
38
39
40
41
42
43
using System;
using System.Collections.Generic;
 
namespace Question2601927
{
    class Program
    {
        static void Main(string[] args)
        {
            // Здесь получили от пользователя массив чисел, возможно повторяющихся.
 
            Console.Write("Введите кол-во элементов: ");
            int y = Convert.ToInt32(Console.ReadLine());
 
            var mas = new int[y]; // { 1, 2, 3 };
            for (int j = 0; j < y; j++)
            {
                Console.Write("Введите целое число: ");
                mas[j] = Convert.ToInt32(Console.ReadLine());
            }
 
            // В множестве а будут содержаться только уникальные значения.
            var a = new HashSet<int>(mas);
            var tmp = new int[a.Count];
            a.CopyTo(tmp);
 
            for (var i = 0; i < tmp.Length; i++)
            {
                // Во временном множестве всегда будут добавляться элементы,
                // а непосредственно перед печатью множество будет клонироваться в отдельное множество
                var tmpSet = new HashSet<int>();
                for (var j = i; j < tmp.Length; j++)
                {
                    tmpSet.Add(tmp[j]);
                    var set = new HashSet<int>(tmpSet); // Клон временного множества
                    Console.WriteLine(String.Join(", ", set));
                }
 
            }
            Console.ReadKey();
        }
    }
}

@chumich · 21.03.2020, 10:25

Ну, а если нужно "по-простому", то так:

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
Console.WriteLine("Введите кол-во элементов:");
int y = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Введите Ваши элементы множества: ");
double[] mas = new double[y];
for (int j = 0; j < y; j++)
{
    mas[j] = Convert.ToInt32(Console.ReadLine());
}
Console.WriteLine();
Console.Write("Множество: ");
for (int j = 0; j < y; j++)
{
    Console.Write(mas[j] + " ");
}
Console.WriteLine();
Console.Write("Подмножества: ");
Console.WriteLine();
string s = "";
for (int j = 0; j < y - 1; j++)
{
    s = mas[j].ToString();
    Console.WriteLine(s);
    for (int k = j + 1; k < y; k++)
    {
        s = s + ", " + mas[k].ToString();
        Console.WriteLine(s);
    }
}
Console.WriteLine(mas[y - 1]);
Console.Read();
}

@amr-now · 21.03.2020, 11:03

Pufik11, chumich, если нужно только печатать числа, то так:

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
33
34
35
36
37
38
39
40
using System;
 
namespace Question2601927
{
    class Program
    {
        static void Main(string[] args)
        {
            // Здесь получили от пользователя массив чисел, возможно повторяющихся.
 
            Console.Write("Введите кол-во элементов: ");
            int y = Convert.ToInt32(Console.ReadLine());
 
            var mas = new int[y]; // { 1, 2, 3 };
            for (int j = 0; j < y; j++)
            {
                Console.Write("Введите целое число: ");
                mas[j] = Convert.ToInt32(Console.ReadLine());
            }
 
            Console.Write("Множество: ");
            for (int j = 0; j < y; j++)
            {
                Console.Write(mas[j] + " ");
            }
            Console.WriteLine();
            Console.WriteLine("Подмножества: ");
            for (var i = 0; i < mas.Length; i++)
            {
                var s = "";
                for (var j = i; j < mas.Length; j++)
                {
                    s += mas[j] + " ";
                    Console.WriteLine(s);
                }
            }
            Console.ReadKey();
        }
    }
}

Но в решении не пострадало ни одного множества.

Добавлено через 6 минут
Если в псевдо-подмножествах нужен разделитель-запятая, то чуть надо изменить вывод:

C#
1
2
3
4
5
6
7
8
9
10
11
12
            Console.WriteLine("Подмножества: ");
            for (var i = 0; i < mas.Length; i++)
            {
                var s = "";
                for (var j = i; j < mas.Length; j++)
                {
                    s += mas[j];
                    if (j < mas.Length - 1)
                        s += ",";
                    Console.WriteLine(s);
                }
            }

@Pufik11 · 21.03.2020, 11:11 **[ТС]**

А что значит y-1? Зачем он

@chumich · 21.03.2020, 11:22

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

А что значит y-1? Зачем он

Чтобы не дублировать последний элемент. Но у amr-now, более лаконичный вариант (второй), так что лучше его используйте.

@amr-now · 21.03.2020, 11:27

Pufik11, chumich, кстати да. Если используем исходный массив, то от него переменная y осталась ))
Я забыл уже про неё ))))
Вместо mas.Length можно написать y

@Pufik11 · 21.03.2020, 11:28 **[ТС]**

Проблема в другом, у меня есть вариант как должно находить подмножества, а в программе у arm row, оно находит не всё

@amr-now · 21.03.2020, 11:46

Pufik11, народ предложил ухищрения через эмуляцию двоичного кода.
Найти все подмножества множества
Задача, получается, явно не для новичка ))

@ZoAs · 21.03.2020, 11:53

Каждому подмножеству можно поставить в соответствие характеристический вектор из нулей и единиц.
К примеру для множества A = {a, b, c, d} (считаем, что в массиве элементы лежат в таком порядке, как я записал), некоторые подмножества и соответствующие им вектора таковы:
{ } ~ (0,0,0,0)
{a} ~ (1,0,0,0)
{a,c} ~ (1,0,1,0)
{a,c,d} ~ (1,0,1,1)

Каждый характеристический вектор можно воспринимать как двоичное число. А каждому двоичному числу соответствует десятичное. Таким образом, перебирая все десятичные числа от 0 до 2⁴-1 можно перебрать все подмножества A. Если элементов во множестве A было бы n, то подмножеств было бы 2ⁿ, так что перебирали бы от 0 до 2ⁿ-1. То есть
0 ~ (0,0,0,0) ~ { }
1 ~ (0,0,0,1) ~ {d}
2 ~ (0,0,1,0) ~ {c}
...
10 ~ (1,0,1,0) ~ {a,c}
...
15 ~ (1,1,1,1) ~ {a,b,c,d}

Сейчас начну писать код и окажется, что вектора удобней в обратном порядке читать, что не существенно.

Теперь вопрос, как перебирая целые числа в нужном диапазоне получать на их основе подмножества. Для этого пригодятся побитовые операции над целыми числами. В коде ниже как раз этот перебор и 1<<mas.Length для получения нужной степени двойки.

C#
1
2
3
4
for (int subset = 0; subset < 1<<mas.Length; subset++)
{
    Console.WriteLine(subset);
}

Чтобы понять, на каких местах в переменной subset биты равны единице (и вывести соответствующие элементы mas), нужно последовательно выполнять поэлементную конъюнкцию переменной subset с двоичными числами вида:
0001 ~ 1
0010 ~ 2
0100 ~ 4
1000 ~ 8
которые, являются степенями двойки (степень двойки получаем операцией 1<<p). Если в результате поэлементной конъюнкции получится 0, значит бит равен нулю, иначе единице. И если бит равен единице, то из переменной mas можно печатать элемент.

Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
for (int subset = 0; subset < 1<<mas.Length; subset++)
{
    for (int p = 0; p < mas.Length; p++)
    {
        if (((1 << p) & subset) != 0)
            Console.Write($"{mas[p]} ");
    }
    Console.WriteLine();
}

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

Или нужен именно такой вывод, как указан? Тогда я всё это зря писал

@amr-now · 21.03.2020, 13:36

У меня на основе двоичной системы соответствия элементам так получилось:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
using System;
 
namespace Question2601927
{
    class Program
    {
        static void Main(string[] args)
        {
            // Здесь получили от пользователя массив чисел, возможно повторяющихся.
 
            Console.Write("Введите кол-во элементов: ");
            int y = Convert.ToInt32(Console.ReadLine());
 
            var mas = new int[y]; // { 1, 2, 3 };
            for (int j = 0; j < y; j++)
            {
                Console.Write("Введите целое число: ");
                mas[j] = Convert.ToInt32(Console.ReadLine());
            }
 
            Console.Write("Множество: ");
            for (int j = 0; j < y; j++)
            {
                Console.Write(mas[j] + " ");
            }
            Console.WriteLine();
            Console.WriteLine("Подмножества: ");
            for (int n = 1; n < Math.Pow(2, y); n++)
            {
                var s = "";
 
                var tmp = n;
                for (var i = 0; tmp > 0; i++)
                {
                    int reminder;
                    tmp = Math.DivRem(tmp, 2, out reminder);
                    if (reminder > 0)
                        s += mas[i] + ",";
                }
                s = s.Substring(0, s.Length - 1);
                Console.WriteLine(s);
            }
            Console.ReadKey();
        }
    }
}

Вывод тоже упорядочен по-другому. Здесь он явно имитирует двоичное число.

Добавлено через 1 минуту
----
Не. Ну тут явно под дурака косить не получится.
Если не списывать, то студент явно должен хорошо знать алгебру.

Добавлено через 12 минут
----
С принудительным упорядочением результата с помощью Array.Sort():

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
using System;
 
namespace Question2601927
{
    class Program
    {
        static void Main(string[] args)
        {
            // Здесь получили от пользователя массив чисел, возможно повторяющихся.
 
            Console.Write("Введите кол-во элементов: ");
            int y = Convert.ToInt32(Console.ReadLine());
 
            var mas = new int[y]; // { 1, 2, 3 };
            for (int j = 0; j < y; j++)
            {
                Console.Write("Введите целое число: ");
                mas[j] = Convert.ToInt32(Console.ReadLine());
            }
 
            Console.Write("Множество: ");
            for (int j = 0; j < y; j++)
            {
                Console.Write(mas[j] + " ");
            }
            Console.WriteLine();
            Console.WriteLine("Подмножества: ");
            int count = (int)(Math.Pow(2, y) - 1);
            var sets = new string[count];
            for (int n = 1; n <= count; n++)
            {
                var s = "";
 
                var tmp = n;
                for (var i = 0; tmp > 0; i++)
                {
                    int reminder;
                    tmp = Math.DivRem(tmp, 2, out reminder);
                    if (reminder > 0)
                        s += mas[i] + ",";
                }
                s = s.Substring(0, s.Length - 1);
                sets[n-1] = s;
            }
            Array.Sort(sets);
            Console.WriteLine(string.Join("\n", sets));
            Console.ReadKey();
        }
    }
}

Добавлено через 1 час 2 минуты
---
В обсуждениях мелькала мысль - если мы хотим, чтобы в множестве было много элементов (больше разрядности целого числа), то надо делать служебный массив булевых значений присутствия/отсутствия.
Соответственно, "инкремент" счетчика для булевых переключателей придется написать самостоятельно.

@kolorotur · 21.03.2020, 14:35

Пустое подмножество — тоже элемент множества.

C#
1
2
3
4
5
6
7
8
9
10
11
12
static IEnumerable<IEnumerable<T>> PowerSet<T>(IEnumerable<T> initialSet)
{
    var set = new List<IEnumerable<T>>() { Enumerable.Empty<T>() };
    return initialSet.Aggregate((IEnumerable<IEnumerable<T>>)set, (x, y) => x.Concat(x.Select(z => z.Concat(new List<T>() { y }))));
}
 
static void Main()
{
    int[] set = { 1, 2, 3 };
    Console.WriteLine(string.Join(Environment.NewLine, PowerSet(set).Select(s => '{' + string.Join(", ", s) + '}')));
    Console.ReadKey(true);
}

Новые блоги и статьи Все статьи Все блоги /
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .

@Pufik11 2 / 2 / 0 Регистрация: 15.12.2019 Сообщений: 94
	21.03.2020, 11:11 [ТС]
	А что значит y-1? Зачем он 0

@amr-now 6496 / 3907 / 2006 Регистрация: 14.06.2018 Сообщений: 6,781
	21.03.2020, 11:27
	Pufik11, chumich, кстати да. Если используем исходный массив, то от него переменная y осталась )) Я забыл уже про неё )))) Вместо mas.Length можно написать y 0

@Pufik11 2 / 2 / 0 Регистрация: 15.12.2019 Сообщений: 94
	21.03.2020, 11:28 [ТС]
	Проблема в другом, у меня есть вариант как должно находить подмножества, а в программе у arm row, оно находит не всё Миниатюры 0

@amr-now 6496 / 3907 / 2006 Регистрация: 14.06.2018 Сообщений: 6,781
	21.03.2020, 11:46
	Pufik11, народ предложил ухищрения через эмуляцию двоичного кода. Найти все подмножества множества Задача, получается, явно не для новичка )) 0