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

Я хотел бы получить все возможные подмножества заданной длины, которые приводят к реальному набору. Итак, для набора [a, b, c] и размеров подмножества 1 и 2 я хотел бы рассчитать:

[[a,b],[c]] , [[b,c],[a]] , [[a,c],[b]]

Я экспериментировал с кодом из Алгоритм вычисления набора мощностей (всех возможных подмножеств) набора в R , но этот алгоритм будет генерировать все подмножества, а не только те, которые предшествуют набору.

Я пытаюсь решить эту проблему для размера ~ 30. Я хочу рассчитать оценку каждой комбинации подмножеств и сохранить только лучшие из них, таким образом, я надеюсь, что память не составит труда. Выбранный язык программирования — python.


python set algorithm superset
person Maocx    schedule 31.10.2014    source источник
comment
Подмножество+подмножество = полный набор; они составляют весь набор   -  person Maocx    schedule 31.10.2014
comment
Итак, вы имеете в виду разделы набора.   -  person senderle    schedule 31.10.2014

Ответы (2)


arrow_upward
3
arrow_downward

Как насчет создания комбинаций длины 2 и генерирования остатка путем вычисления разницы с исходным набором? Вот что я имею в виду:

from itertools import combinations

s = {'a', 'b', 'c'}

res = [(set(comb), s.difference(comb)) for comb in combinations(s, 2)]

Генерирует:

[({'a', 'c'}, {'b'}), ({'b', 'c'}, {'a'}), ({'a', 'b'}, {'c'})]
person w-m    schedule 31.10.2014

arrow_upward
0
arrow_downward

Вы можете использовать следующий код для определения размера подмножества внутри списка:

     list1=[[1,2,3],[1,3],[2,3,3,4]]
     x= len(list1)
     while(x>0):
        print len(list1[x-1])
        x=x-1

выход:

  4
  2
  3
person jack    schedule 31.10.2014