Сгенерировать все наборы размера N из набора объектов MALLER объектов размера K

Question

Учитывая набор объектов K, сгенерируйте все наборы размера N (где N> K). Например, начиная с набора {1,2} (K = 2}, генерируя все множества размера N = 3, вы получите следующие выходные множества: {1,1,1} {1,1,2}, { 1,2,1}, {2,1,1}, {2,2,1}, {2,1,2}, {1,2,2}, {2,2,2}. эффективный алгоритм для генерации таких множеств?

Примечание для Кена Уайта: В моих исследованиях появились только алгоритмы, имеющие отношение к C (mn), где n < m; алгоритмы для перестановок и комбинации элементов из заданного набора. Это не то, что Я пытаюсь сделать это. Я не размещаю код, потому что без алгоритма, что я попробую сделать, чтобы мой код выполнил?

Возможно, моя предыдущая публикация была неясной, но ваш ответ - «Пожалуйста, извините мое полное отсутствие но кто-то может написать этот код для меня? Вернитесь позже, чтобы поднять его. Tx bye. - Ken White 27 июня в 22:54 "был действительно профессиональным и полезным.

Answer 1

Вы можете назначить заказ наборам, чтобы вы не повторно посещали тех, с которыми вы уже обращались. Начните со всех наборов, где K[0] встречается 0 раз, и K[1] происходит 0 раз, и, наконец, K[last] появляется N раз. Затем рассмотрите, когда K[last-1] появляется 1 раз и т. Д., Сокращая ваш поиск каждый раз, когда сумма элементов, которые вы уже присвоили, достигает N.

Псевдо-код:

addAllSets(N, K, 0, new int[K], new Set()) //Initial call 

addAllSets(int targetCount, int K, int index, int[] prefix, Set allSets){ 
    if (index < k): //We still have the rest of the elements to consider 
     for i in range 0 to targetCount - 1: 
      prefix[index] = i //Try it with i of this element 
      addAllSets(targetCount - i, K, index + 1, prefix.copy, allSets) //Recursively check remaining elements 
    prefix[index] = targetCount //Or just fill in the rest of the set with copies of this element 
    allSets.add(prefix) //Add this to the set of sets 

префикс магазинов подсчитывает для некоторого числа элементов (общее число всегда будет K - targetCount при вызове функции.) Каждый раз, когда мы «заполнить его», мы добавим его в множество всех множеств.