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

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

How can i find all subsets of a set using c#? here set is a sentence(string).for example:
s=”i am nik”;What will be the code for that?

here the subsets of s will be-> i, am, nik, i am, i nik, am nik, i am nik.

asked Apr 16, 2010 at 4:34

NikRED's user avatar

NikREDNikRED

1,1712 gold badges21 silver badges39 bronze badges

2

Here’s a function I wrote to find all incontiguous subsets from a given array.

List<T[]> CreateSubsets<T>(T[] originalArray)
{
    List<T[]> subsets = new List<T[]>();

    for (int i = 0; i < originalArray.Length; i++)
    {
        int subsetCount = subsets.Count;
        subsets.Add(new T[] { originalArray[i] });

        for (int j = 0; j < subsetCount; j++)
        {
            T[] newSubset = new T[subsets[j].Length + 1];
            subsets[j].CopyTo(newSubset, 0);
            newSubset[newSubset.Length - 1] = originalArray[i];
            subsets.Add(newSubset);
        }
    }

    return subsets;
}

So given an integer array of 1,2,3,4,5, it will return a List<int[]> containing 31 subsets.

Edit: Based upon your update, you can generate the 6 subsets you need with the function above and by using string.Split(‘ ‘) on your original sentence. Consider:

string originalString = "i am nik";
List<string[]> subsets = CreateSubsets(originalString.Split(' '));

foreach (string[] subset in subsets)
{
    Console.WriteLine(string.Join("t", subset));
}

answered Apr 16, 2010 at 4:39

Anthony Pegram's user avatar

Anthony PegramAnthony Pegram

123k27 gold badges221 silver badges245 bronze badges

1

    // all subsets of given set 
    static void numbcomb (string [] list) 
    {            
        int gelen = (int)Math.Pow(2,list.Length); // number of subsets (2^n)
        string [] result = new string [gelen]; // array with subsets as elements

        for(int i=0; i<gelen; i++) // filling "result"
        {
            for(int j=0;j<list.Length;j++)  // 0,1,2 (for n=3)
            {
                int t = (int)Math.Pow(2, j); // 1,2,4 (for n=3)
                if ((i&t)!=0)  // the MAIN THING in the program
                               // i can be:
                               // 000,001,010,011,100,101,110,111
                               // t can be: 001,010,100
                               // take a pensil and think about!
                { result[i]+=list[j]+" ";} // add to subset
            }
            Console.Write("{0}: ",i);// write subset number
            Console.WriteLine(result[i]);//write subset itself
        }
    }

answered Jul 27, 2011 at 7:35

Orlovnikt's user avatar

2

Источник

Павел Сергунин

Гуру

(3734)


9 лет назад

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

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

В твоем случае будет 2^3 = 8 штук:
{{∅}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}

Дмитрий Проклов

Профи

(603)


4 года назад

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

Источник

Учитывая набор S, сгенерировать все различные его подмножества, т. е. найти различные мощности множества S. Силовой набор любого набора S это множество всех подмножеств S, включая пустое множество и S сам.

Например, если S установлен {x, y, x}, то подмножества S находятся:

  • {} (also known as the empty set or the null set).
  • {x}
  • {y}
  • {x}
  • {x, y}
  • {x, x}
  • {y, x}
  • {x, y, x}

Следовательно, различные подмножества в множестве мощностей S находятся: { {}, {x}, {y}, {x, y}, {x, x}, {x, y, x} }.

Потренируйтесь в этой проблеме

Подход 1: Использование рекурсии

Проблема очень похожа на 0/1 проблема с рюкзаком, где для каждого элемента множества S, у нас есть два варианта:

  1. Рассмотрим этот элемент.
  2. Не принимайте во внимание этот элемент.

Следующее решение генерирует все комбинации подмножеств, используя приведенную выше логику. Чтобы распечатать только отдельные подмножества, сначала сортировать подмножество и исключить все соседние повторяющиеся элементы из подмножества вместе с текущим элементом в случае 2. Это показано ниже на C++, Java и Python:

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

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

// Функция для печати элементов вектора

void printVector(vector<int> const &input)

{

    cout << “[“;

    int n = input.size();

    for (int i: input) {

        cout << i;

        if (—n) {

            cout << “, “;

        }

    }

    cout << “]n”;

}

// Рекурсивная функция для вывода всех различных подмножеств `S`.

// `S` ——> входной набор

// `out` ——> vector для хранения подмножества

// `i` ——> индекс следующего элемента в наборе `S` для обработки

void printPowerSet(vector<int> &S, vector<int> &out, int i)

{

    // если все элементы обработаны, вывести текущее подмножество

    if (i < 0)

    {

        printVector(out);

        return;

    }

    // включить текущий элемент в текущее подмножество и повторить

    out.push_back(S[i]);

    printPowerSet(S, out, i – 1);

    // возврат: исключить текущий элемент из текущего подмножества

    out.pop_back();

    // удаляем соседние повторяющиеся элементы

    while (S[i] == S[i–1]) {

        i—;

    }

    // исключаем текущий элемент из текущего подмножества и повторяем

    printPowerSet(S, out, i – 1);

}

// Обертка над функцией `printPowerSet()`

void findPowerSet(vector<int> S)        // без ссылки, без константы

{

    // сортируем набор

    sort(S.begin(), S.end());

    // создаем пустой vector для хранения элементов подмножества

    vector<int> out;

    printPowerSet(S, out, S.size() – 1);

}

int main()

{

    vector<int> S = { 1, 3, 1 };

    findPowerSet(S);

    return 0;

}

Скачать  Выполнить код

результат:

[3, 1, 1]
[3, 1]
[3]
[1, 1]
[1]
[]

Java

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

51

52

53

import java.util.ArrayDeque;

import java.util.Arrays;

import java.util.Deque;

class Main

{

    // Рекурсивная функция для вывода всех различных подмножеств `S`.

    // `S` ——> входной набор

    // `out` ——> список для хранения подмножества

    // `i` ——> индекс следующего элемента в наборе `S` для обработки

    public static void printPowerSet(int[] S, Deque<Integer> out, int i)

    {

        // если все элементы обработаны, вывести текущее подмножество

        if (i < 0)

        {

            System.out.println(out);

            return;

        }

        // включить текущий элемент в текущее подмножество и повторить

        out.addLast(S[i]);

        printPowerSet(S, out, i – 1);

        // возврат: исключить текущий элемент из текущего подмножества

        out.pollLast();

        // удаляем соседние повторяющиеся элементы

        while (i > 0 && S[i] == S[i – 1]) {

            i—;

        }

        // исключаем текущий элемент из текущего подмножества и повторяем

        printPowerSet(S, out, i – 1);

    }

    // Обертка над функцией `printPowerSet()`

    public static void findPowerSet(int[] S)

    {

        // сортируем набор

        Arrays.sort(S);

        // создаем пустой список для хранения элементов подмножества

        Deque<Integer> out = new ArrayDeque<>();

        printPowerSet(S, out, S.length – 1);

    }

    public static void main(String[] args)

    {

        int[] S = { 1, 3, 1 };

        findPowerSet(S);

    }

}

Скачать  Выполнить код

результат:

[3, 1, 1]
[3, 1]
[3]
[1, 1]
[1]
[]

Python

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

from collections import deque

# Рекурсивная функция для печати всех различных подмножеств `S`.

# `S` ——> входной набор

# `i` ——> индекс следующего элемента в наборе `S` для обработки

# `out` ——> список для хранения элементов подмножества

def printPowerSet(S, i, out=deque()):

    #, если все элементы обработаны, вывести текущее подмножество

    if i < 0:

        print(list(out))

        return

    # включает текущий элемент в текущее подмножество и повторяет

    out.append(S[i])

    printPowerSet(S, i – 1, out)

    # Возврат #: исключить текущий элемент из текущего подмножества

    out.pop()

    # удалить соседние повторяющиеся элементы

    while i > 0 and S[i] == S[i – 1]:

        i = i – 1

    # исключить текущий элемент из текущего подмножества и повторить

    printPowerSet(S, i – 1, out)

# Обертка над функцией `printPowerSet()`

def findPowerSet(S):

    # сортировать набор

    S.sort()

    # распечатать набор мощности

    printPowerSet(S, len(S) – 1)

if __name__ == ‘__main__’:

    S = [1, 3, 1]

    findPowerSet(S)

Скачать  Выполнить код

результат:

[3, 1, 1]
[3, 1]
[3]
[1, 1]
[1]
[]

Временная сложность приведенного выше решения равна O(n.2n), куда n – это размер заданного набора.

Подход 2

Для данного набора S, набор мощности можно найти, сгенерировав все двоичные числа от 0 до 2n-1, куда n это размер набора. Например, для набора S {x, y, z}, генерировать двоичные числа от 0 до 23-1 и для каждого сгенерированного числа соответствующий набор можно найти, рассматривая установленные биты в числе.

  • 0 = 000 = {}
  • 1 = 001 = {z}
  • 2 = 010 = {y}
  • 3 = 011 = {y, z}
  • 4 = 100 = {x}
  • 5 = 101 = {x, z}
  • 6 = 110 = {x, y}
  • 7 = 111 = {x, y, z}

Чтобы избежать печати повторяющихся подмножеств, сначала отсортируйте набор. Кроме того, вставьте каждое подмножество в набор. Поскольку набор поддерживает все различные комбинации, у нас будут уникальные подмножества в наборе. Ниже приведена программа на C++, Java и Python, которая демонстрирует это:

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

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

#include <iostream>

#include <set>

#include <vector>

#include <algorithm>

#include <cmath>

using namespace std;

// Функция для печати заданного набора

void printSet(vector<int> const &input)

{

    cout << “[“;

    int n = input.size();

    for (int i: input) {

        cout << i;

        if (—n) {

            cout << “, “;

        }

    }

    cout << “]n”;

}

// Итерационная функция для поиска всех различных подмножеств `S`

set<vector<int>> findPowerSet(vector<int> S)        // без ссылки, без константы

{

    // `N` хранит общее количество подмножеств

    int N = pow(2, S.size());

    // сортируем набор

    sort(S.begin(), S.end());

    set<vector<int>> powerset;

    // генерируем каждое подмножество одно за другим

    for (int i = 0; i < N; i++)

    {

        vector<int> set;

        // проверить каждый бит `i`

        for (int j = 0; j < S.size(); j++)

        {

            // если установлен j-й бит `i`, добавляем `S[j]` к подмножеству

            if (i & (1 << j)) {

                set.push_back(S[j]);

            }

        }

        // вставляем подмножество в набор мощности

        powerset.insert(set);

    }

    return powerset;

}

int main()

{

    vector<int> S = { 1, 2, 1 };

    // находим powerset множества S

    set<vector<int>> powerset = findPowerSet(S);

    // вывести все подмножества, присутствующие в наборе мощности

    for (vector<int> subset: powerset) {

        printSet(subset);

    }

    return 0;

}

Скачать  Выполнить код

результат:

[]
[1]
[1, 1]
[1, 1, 2]
[1, 2]
[2]

Java

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

import java.util.*;

class Main

{

    // Итерационная функция для вывода всех различных подмножеств `S`

    public static void findPowerSet(int[] S)

    {

        // `N` хранит общее количество подмножеств

        int N = (int)Math.pow(2, S.length);

        Set<List<Integer>> set = new HashSet<>();

        // сортируем набор

        Arrays.sort(S);

        // генерируем каждое подмножество одно за другим

        for (int i = 0; i < N; i++)

        {

            List<Integer> subset = new ArrayList<>();

            // проверить каждый бит `i`

            for (int j = 0; j < S.length; j++)

            {

                // если установлен j-й бит `i`, добавляем `S[j]` к подмножеству

                if ((i & (1 << j)) != 0) {

                    subset.add(S[j]);

                }

            }

            // вставляем подмножество в множество

            set.add(subset);

        }

        // вывести все подмножества, присутствующие в наборе

        System.out.println(set);

    }

    public static void main(String[] args)

    {

        int[] S = { 1, 2, 1 };

        findPowerSet(S);

    }

}

Скачать  Выполнить код

результат:

[[1], [], [1, 1], [2], [1, 1, 2], [1, 2]]

Python

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

# Итеративная функция для печати всех различных подмножеств `S`

def findPowerSet(S):

    # `N` хранит общее количество подмножеств

    N = int(pow(2, len(S)))

    s = set()

    # сортировать набор

    S.sort()

    # генерирует каждое подмножество по одному

    for i in range(N):

        subset = []

        # проверяет каждый бит `i`

        for j in range(len(S)):

            #, если установлен j-й бит `i`, добавить `S[j]` к подмножеству

            if i & (1 << j):

                subset.append(S[j])

        # вставить подмножество в набор

        s.add(tuple(subset))

    # распечатать все подмножества, присутствующие в наборе

    print(s)

if __name__ == ‘__main__’:

    S = [1, 2, 1]

    findPowerSet(S)

Скачать  Выполнить код

результат:

{(1, 1), (1,), (1, 1, 2), (1, 2), (), (2,)}

Временная сложность приведенного выше решения равна O(n.2n), куда n – это размер заданного набора.

Источник

Ввожу например множество 1 2 3 4

Должно вывести вроде

2 3 4,
1 3 4,
1 2 4,
1 2 3,
1 2,
1 3,
1 4,
2 3,
2 4,
3 4,
1,
2,
3,
4

Пока что получается нормально вывести 

2 3 4,
1 3 4,
1 2 4,
1 2 3

Что изменить/дописать, чтоб выводились остальные подмножества?
И мне нужна работа именно с рекурсией

#include <iostream>
using namespace std;
int rec(int *mas, int n);
int n, m, null;
int main () {
    cout << "n = ";
    cin >> n;
    cout << "Array: ";
    m = n;
    null = 0;
    int* mas = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> mas[i];
    }
    rec(mas, n);
    system("pause");
    return 0;
}


int rec(int *mas, int n) {
    for (int i = 0; i < n; i++) {
        if (i != null) {
            cout << mas[i] << " ";
        }
    }
    cout << endl;
    null++;
    m--;
    if (m == 0) {
        return 0;
    }
    else  
        rec(mas, n);
    return 0;
}

Источник

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

Здравствуйте,

Есть множество объектов. К примеру: {A,B,C}. Нужно найти все подмножества множества {A,B,C} через циклы. Как лучше это сделать? Сложность алгоритма должна быть O(2^n). Ж

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

Спасибо.


  • Вопрос задан

    более трёх лет назад

  • 4313 просмотров

Пригласить эксперта

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


  • Показать ещё
    Загружается…

19 мая 2023, в 13:22

7000 руб./за проект

11 мая 2023, в 16:20

1500 руб./в час

19 мая 2023, в 13:05

4000 руб./за проект

Минуточку внимания

Источник

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