Комбинации элементов в несколько этапов, что позволяет перекрытия - PullRequest
Новая
       14

Комбинации элементов в несколько этапов, что позволяет перекрытия

0 голосов
/ 27 марта 2012

Контекст

  • У меня есть список элементов
  • У меня также есть структура с s этапами
  • Количество этапов этапов может быть больше, равноили меньше, чем количество элементов
  • Каждый этап может иметь n слотов
  • Элементы могут занимать один и тот же этап, занимая 2 слота на этом этапе
  • Порядок слотов не имеет значения
  • Количество слотов меньше или равно количеству элементов
  • Каждый слот может содержать один элемент
  • Слот может быть пустым
  • Любая заданная структураможет содержать каждый элемент только один раз

Проблема:

Я хочу сгенерировать все комбинации для распределения элементов в структуре, например:

  • Каждый элемент появляется один и только один раз в структуре
  • Все элементы присутствуют в каждой комбинации
  • Я хочу использовать Java для реализации

Пример: 

/* Inputs */
items = {1, 2}
structure = [ {}, {}, {}] // with 3 stages

/* Outputs */
comb1 = [ {1,2}, {}, {} ]
comb2 = [ {1}, {2}, {} ]
comb3 = [ {1}, {}, {2} ]
comb4 = [ {}, {1,2}, {} ]
comb5 = [ {}, {1}, {2} ]
comb6 = [ {}, {}, {1,2}]
comb7 = [ {}, {2}, {1} ]
comb8 = [ {2}, {1}, {} ]
comb9 = [ {2}, {}, {1} ]

Идеи очень приветствуются.

1 Ответ

0 голосов
/ 29 марта 2012

вот решение: 

import time


def get_stages(size):
   stages = []
   for i in range(0, size):
      stages.append([])
   return stages

def get_combos(combo_size, stage_size):
   combos = []
   for i in range(0, combo_size):
      combos.append(get_stages(stage_size))
   return combos


def insert_item_in_stage(stages, position, item):
   stages[position].append(item)

def copy_stages(stages):
   #print 'copying', stages
   copies = []
   for i in range(0, len(stages)):
      copy = []
      for stage in stages:
         stage_copy = []
         for slot in stage:
            stage_copy.append(slot)
         copy.append(stage_copy)
      copies.append(copy)
   return copies

def combine(items, stages, all_combos):
   #print items, 'with', stages
   if len(items) == 1:
      item = items[0]
      combos = copy_stages(stages)
      for combo in combos:
         combo[combos.index(combo)].append(item)
         all_combos.append(combo)
   elif len(items) > 1:
      item = items[0]
      items.remove(item)
      combos = copy_stages(stages)

      for combo in combos:
         combo[combos.index(combo)].append(item)
         combine(list(items), combo, all_combos)
   else:
      print 'oops'


def test (items, size):
   print 'test', items, 'with', size, "stages"
   stages = get_stages(size)
   all_combos = []
   combine(items, stages, all_combos)
   for combo in all_combos:
      print combo
   print len(all_combos)
   print ''

#run tests
test([1,2], 3)
test([1,2,3], 3)
start =  time.clock()
test([1,2,3,4,5, 6], 8)
end = time.clock()
print end-start
...