Нахождение всех подмножеств набора

Мне нужен алгоритм для нахождения всех подмножеств набора, где число элементов в наборе n.

S={1,2,3,4...n}

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

Например,

S={1,2,3,4,5}

Как Вы знаете {1} и {1,2} подмножества?

Мог кто-то помогать мне с простой функцией в C++ найти подмножества {1,2,3,4,5}

33
задан Rahul Vyas 16 October 2019 в 05:56
поделиться

0 ответов

Это очень просто сделать рекурсивно. Основная идея заключается в том, что для каждого элемента набор подмножеств можно разделить поровну на те, которые содержат этот элемент, и на те, которые его не содержат, и эти два набора в противном случае равны.

  • Для n = 1 набор подмножеств is {{}, {1}}
  • Для n> 1 найдите набор подмножеств 1, ..., n-1 и сделайте две его копии. Для одного из них добавьте n к каждому подмножеству. Затем возьмите объединение двух копий.

Редактировать Чтобы сделать его кристально ясным:

  • Множество подмножеств {1} есть {{}, {1}}
  • Для {1, 2 }, возьмите {{}, {1}}, добавьте 2 к каждому подмножеству, чтобы получить {{2}, {1, 2}}, и возьмите объединение с {{}, {1}}, чтобы получить {{}, { 1}, {2}, {1, 2}}
  • Повторяйте до достижения n
106
ответ дан Michael Borgwardt 27 November 2019 в 17:20
поделиться

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

8
ответ дан sris 27 November 2019 в 17:20
поделиться

одним простым способом был бы следующий псевдокод:

Set getSubsets(Set theSet)
{
  SetOfSets resultSet = theSet, tempSet;


  for (int iteration=1; iteration < theSet.length(); iteration++)
    foreach element in resultSet
    {
      foreach other in resultSet
        if (element != other && !isSubset(element, other) && other.length() >= iteration)
          tempSet.append(union(element, other));
    }
    union(tempSet, resultSet)
    tempSet.clear()
  }

}

Ну, я не совсем уверен, что это правильно, но выглядит нормально.

0
ответ дан AndreasT 27 November 2019 в 17:20
поделиться
Другие вопросы по тегам:

Похожие вопросы: