Как найти все подмножества множества
Перейти к содержимому

Как найти все подмножества множества

  • автор:

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

Например так. Ваша ошибка — вы не делаете копию списка, вы работаете с самим списком по другой ссылке.

Отслеживать
ответ дан 5 ноя 2019 в 13:56
9,894 3 3 золотых знака 29 29 серебряных знаков 43 43 бронзовых знака

Я добавил в своем коде .copy(),но оно все равно не работает.В консоли оно выдает следуйщие результаты: видно,что временный список,есть таким каким он должен быть,но после слития с главным,в главном пустой список меняется на той которым есть временным,тоесть не действует копия списка,почему?

5 ноя 2019 в 14:37

@VitalykChernysh копировать надо 2 раза. Один раз весь список в новый, второй в цикле вложенные списки.

Как найти все подмножества множеств

На простом примере напомним, что называется подмножеством, какие бывают подмножества (собственные и несобственные), формулу нахождения числа всех подмножеств, а также калькулятор, который выдает множество всех подмножеств.

Пример 1. Дано множество А = . Выпишите все подмножества
данного множества.

Решение:

Несобственные: , Ø.

Всего: 16 подмножеств.

Пояснение. Множество A является подмножеством множества B если каждый элемент множества A содержится также в B.

• пустое множество ∅ является подмножеством любого множества, называется несобственным;
• любое множество является подмножеством самого себя, также называется несобственным;
У любого n-элементного множества ровно 2 n подмножеств.

Последнее утверждение является формулой для нахождения числа всех подмножеств без перечисления каждого.

Вывод формулы: Допустим у нас имеется множество из n-элементов. При составлении подмножеств первый элемент может принадлежать подмножеству или не принадлежать, т.е. первый элемент можем выбрать двумя способами, аналогично для всех остальных элементов (всего n-элементов), каждый можем выбрать двумя способами, и по правилу умножения получаем: 2∙2∙2∙ . ∙2=2 n

Для математиков сформулируем теорему и приведем строгое доказательство.

Теорема . Число подмножеств конечного множества, состоящего из n элементов, равно 2 n .

1. Для n = 1 (база индукции) (и даже для n = 2, 3) теорема доказана.

2. Допустим, что теорема доказана для n = k, т.е. число подмножеств множества, состоящего из k элементов, равно 2 k .

3. Докажем, что число подмножеств множества B, состоящего из n = k + 1 элемента равно 2 k+1 .
Выбираем некоторый элемент b множества B. Рассмотрим множество A = B \ . Оно содержит k элементов. Все подмножества множества A – это подмножества множества B, не содержащие элемент b и, по предположению, их 2 k штук. Подмножеств множества B, содержащих элемент b, столько же, т.е. 2 k
штук.

Следовательно, всех подмножеств множества B: 2 k + 2 k = 2 ⋅ 2 k = 2 k+1 штук.
Теорема доказана.

В примере 1 множество А = состоит из четырех элементов, n=4, следовательно, число всех подмножеств равно 2 4 =16.

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

Пример 2. Eсть множество , в соответствие ставятся следующие числа:
000 = (пустое множество)
001 =
010 =
011 =
100 =
101 =
110 =
111 =

Калькулятор множества всех подмножеств.

В калькуляторе уже набраны элементы множества А = , достаточно нажать кнопку Submit. Если вам необходимо решение своей задачи, то набираем элементы множества на латинице, через запятую, как показано в примере.

Как пройти все подмножества в множестве?

Желательно пример на java, но можно и на другом любом языке.

  • Вопрос задан более трёх лет назад
  • 4512 просмотров

4 комментария

Оценить 4 комментария

А у Вас какие мысли по этому поводу? Вы хотя бы пытались решить эту задачу?
eatmypants @eatmypants Автор вопроса

Yuxus: конечно. Я застрял на том, что моё алгоритмическое мышление слишком примитивно. Обычными вложенными циклами мне не удалось решить проблему.

Покажите код с вложенными циклами.
eatmypants @eatmypants Автор вопроса
Yuxus: скажите пожалуйста, какой в нем толк, если он все равно не работает правильно?
Решения вопроса 0
Ответы на вопрос 1

Rsa97

Для правильного вопроса надо знать половину ответа

Вообще-то у n-элементного множества 2 n подмножеств, так что n 2 при n > 2 получить нереально.
Один из алгоритмов перечисления:
1. Заводим второй массив (булеан), того же размера, что и исходный, инициализируем его нулями.
2. Выводим подмножество из тех элементов исходного массива, которым в булеане соответствуют единицы.
3. Трактуя булеан как запись числа в двоичной системе прибавляем к нему 1.
4. Если в булеане есть хоть одна 1, переходим к пункту 2.

Найдите ВСЕ подмножества множества M= . Как это делать, объясните пожалуйста!

Множество A является подмножеством множества B если каждый элемент множества A содержится также в B. Например, для твоего множества M: — является подмножеством, — нет.

• пустое множество ∅ является подмножеством любого множества,
• любое множество является подмножеством самого себя.
• У любого n-элементного множества ровно 2^n подмножеств.

Остальные ответы

дано множесто А (1,2,3,4,5,6,7,8,9).
Б (a,b,с, e,k)

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *