несколько коэффициентов с питоном

Question

Вот проблема: Пусть будет 9 разных объектов, найди все способы разделить его на группы по 2, 3 и 4.

Математически, общее количество методов деления может быть выражено как 9! / 2! 3! 4!

Вот что я пробовал,

import itertools
def multiCoef(seta, n1, n2):
  seta = set(seta)
  for comba in itertools.combinations(seta, n1):
    comba = set(comba)
    for combb in itertools.combinations(seta-comba, n2):
      combb = set(combb)
      yield comba, combb, seta-comba-combb

Вы можете попробовать что-то вроде этого, оно работает довольно хорошо:

>>> y = multiCoef(x, 2, 3)
>>> for i in y: print i

Но как только число групп увеличивается, такой подход становится громоздким. Есть ли лучший способ?

Answer 1

См. Itertools.

http://docs.python.org/library/itertools.html

Answer 2

Чтобы найти количество способов разделения (m+n+p) элементов в группе m,n,p, сначала нужно разделить набор на группы m, а затем каждую из этих групп разделить на n, а затем разделить на p.

Теперь способов разделить (m + n + p) элементов на группы (n + p) составляет

==> ^{(n + m + n)} C _{n + p}

==> (m + n + p)! / (M! * (N + p)!)

Теперь путейразделить (n + p) элементов на группы по n *

==> ^{(n + p)} C _n

==>(n + p)! / (n! * (p)!)

, поэтому ^{(n + m + n)} C _m * ^{(n+ p)} C _n = (m + n + p)! / (m! * (n + p)!) * (n + p)! / (n! * (p)!)

==> (m + n + p)! / (M! * N! * P!)

Для создания комбинаций мы можем использовать itertools.combination

Учитывая m = 4, n = 3, p = 2

Разделить группу на (n + p) = 5 элементов

>>> g1=(x for x in itertools.combinations(xrange(9),5))

Примечание ::Вы можете оставить это как генератор.

Разделите каждую из этих групп на подгруппы из n элементов = 3 элемента

>>> groups=[(x,tuple(set(g)-set(x))) for g in g1 for x in itertools.combinations(g,3)]

Примечание :: tuple (set (g) -s)et (x)) даст вам элементы, отличные от x, то есть другая часть группы

Размер группы:

>>> len(groups)
1260
>>>

Теперь проверка

>>> factorial(9)/(factorial(2)*factorial(3)*factorial(4))
1260

Answer 3

Ниже приведен рекурсивный генератор, который принимает диапазон чисел (first и last) и avail, список требуемых размеров набора. Предполагается, что sum(avail) == last - first + 1)

На каждой итерации цикла алгоритм пытается сначала присвоить один из наборов, а затем сгенерировать все назначения для first + 1, ..., last. Генерирование создает кортежи наборов назначений: значение в каждой позиции в кортеже идентифицирует набор наборов для соответствующего индекса. Другими словами t(k) - это заданное назначение для first+k, число в диапазоне 0..len(avail)-1

def generate(first, last, avail): 
   for index, n in enumerate(avail):
       if n == 0:
           continue
       new_avail = list(avail)
       new_avail[index]-=1
       if first < last:
           for d in generate(first + 1, last, new_avail):
               d = (inex,) + d
               yield d
       elif first == last:
           yield (index, )

for perm in generate(1, 9, [2, 3, 4]):
    print perm

Answer 4

Как только вы определили подмножества функций (a, b) для перечисления всех подмножеств размера b в a

for i in subsets(mySet,2):
    for j in subsets(mySet.difference(i),3):
        for k in subsets(j.difference(k),4)
            print i,j,k