генерировать все комбинации для списка с повторяющимися элементами

Question

Относительно этого вопроса , мне интересно, алгоритмы (и фактический код в java / c / c ++ / python / и т. Д., Если у вас есть!) Для генерации всех комбинаций r элементов длясписок с m элементами в общей сложности.Некоторые из этих m элементов могут повторяться.

Спасибо!

Answer 1

рекурс для каждого типа элемента

int recurseMe(list<list<item>> items, int r, list<item> container)
{
  if (r == container.length)
  {
    //print out your collection;
    return 1;
  }
  else if (container.length > score)
  {
    return 0;
  }
  list<item> firstType = items[0];
  int score = 0;
  for(int i = 0; i < firstType.length; i++)
  {
    score += recurseMe(items without items[0], r, container + i items from firstType);
  }
  return score;
}

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

//start with a list<item> original;
list<list<item>> grouped = new list<list<item>>();
list<item> sorted = original.sort();//use whichever method for this
list<item> temp = null;
item current = null;
for(int x = 0; x < original.length; x++)
  if (sorted[x] == current)
  {
    temp.add(current);
  }
  else
  {
    if (temp != null && temp.isNotEmpty)
      grouped.add(temp);
    temp = new list<item>();
    temp.add(sorted[x]);
  }
}
if (temp != null && temp.isNotEmpty)
  grouped.add(temp);
//grouped is the result

Это сортирует список, затем создает подсписки, содержащие одинаковые элементы, вставляя их в список списков grouped

Answer 2

Вот рекурсия, которая, по моему мнению, тесно связана с алгоритмом Жана-Бернарда Пеллера в Mathematica .

. В качестве входных данных принимается число элементов каждого типа.Вывод в аналогичной форме.Например:

{a,a,b,b,c,d,d,d,d} -> {2,2,1,4}

Функция:

f[k_, {}, c__] := If[+c == k, {{c}}, {}]

f[k_, {x_, r___}, c___] := Join @@ (f[k, {r}, c, #] & /@ 0~Range~Min[x, k - +c])

Использование:

f[4, {2, 2, 1, 4}]

{{0, 0, 0, 4}, {0, 0, 1, 3}, {0, 1, 0, 3}, {0, 1, 1, 2}, {0, 2, 0, 2},
 {0, 2, 1, 1}, {1, 0, 0, 3}, {1, 0, 1, 2}, {1, 1, 0, 2}, {1, 1, 1, 1},
 {1, 2, 0, 1}, {1, 2, 1, 0}, {2, 0, 0, 2}, {2, 0, 1, 1}, {2, 1, 0, 1},
 {2, 1, 1, 0}, {2, 2, 0, 0}}

---

Запрошено объяснение этого кода.Это рекурсивная функция, которая принимает переменное число аргументов.Первый аргумент k, длина подмножества.Второй - это список значений каждого типа для выбора.Третий аргумент и далее используется внутри функции для хранения подмножества (комбинации) в том виде, как он создан.

Поэтому это определение используется, когда в наборе выбора больше нет элементов:

f[k_, {}, c__] := If[+c == k, {{c}}, {}]

Если сумма значений комбинации (ее длина) равна k, вернуть эту комбинацию, в противном случае вернуть пустой набор.(+c сокращенно для Plus[c])

В противном случае:

f[k_, {x_, r___}, c___] := Join @@ (f[k, {r}, c, #] & /@ 0~Range~Min[x, k - +c])

Чтение слева направо:

• Join используетсячтобы сгладить уровень вложенных списков, чтобы результат не становился все более глубоким тензором.

• f[k, {r}, c, #] & вызывает функцию, отбрасывая первую позицию набора выбора (x) и добавление нового элемента в комбинацию (#).

• /@ 0 ~Range~ Min[x, k - +c]) для каждого целого числа от нуля до меньшего из первого элемента набора выбора, иk меньше общего количества комбинации, что является максимальным значением, которое можно выбрать, не превышая размер комбинации k.

Answer 3

Я собираюсь сделать это ответом, а не кучей комментариев.

Мой оригинальный комментарий:

Класс Java CombinationGenerator систематически генерирует все комбинации из n элементов, взятые по r за раз. Алгоритм описанный Кеннет Х. Розен, Дискретная математика и ее Applications, 2nd edition (NY: McGraw-Hill, 1991), стр. 284-286. "См. merriampark.com/comb.htm. Имеет ссылку на исходный код.

Как вы указали в своем комментарии, вам нужны уникальные комбинации. Итак, учитывая массив ["a", "a", "b", "b"], вы хотите, чтобы он генерировал aab, abb. Код, который я связал, генерирует aab, aab, baa, baa.

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

Поиск чего-либо в хэш-таблице - это операция O(1), поэтому любая из них будет эффективной. Делать это после факта будет немного дороже, потому что вам придется копировать предметы. Тем не менее, вы говорите O(n), где n - количество сгенерированных комбинаций.

Есть одно осложнение: порядок не имеет значения. То есть, учитывая массив ["a", "b", "a", "b"], код сгенерирует aba, abb, aab, bab. В этом случае aba и aab являются дублирующими комбинациями, как и abb и bab, и использование хеш-таблицы не удалит эти дубликаты за вас. Однако вы можете создать битовую маску для каждой комбинации и использовать идею хеш-таблицы с битовыми масками. Это было бы немного сложнее, но не так ужасно.

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

Несомненно, есть способ изменить код, чтобы он не генерировал дубликаты. Я вижу возможный подход, но это было бы грязно и дорого. Это, вероятно, сделает алгоритм медленнее, чем если бы вы просто использовали идею хеш-таблицы. Подход, который я выбрал бы:

Sort the input array
Use the linked code to generate the combinations
Use a hash table or some other code to select unique items.

Хотя ... мысль пришла мне в голову.

Правда ли, что если вы сортируете входной массив, то любые сгенерированные дубликаты будут смежными? То есть, учитывая входной массив ["a", "a", "b", "b"], сгенерированный вывод будет aab, aab, abb, abb, в этом порядке. Это будет зависеть от реализации, конечно. Но если это верно в вашей реализации, то изменение алгоритма для удаления дубликатов - это простой вопрос проверки, совпадает ли текущая комбинация с предыдущей.