Как эффективно хранить большой набор перестановок?

Допустим, у нас есть список элементов:

[{dog,1},{dog,2},{cat,1},{cat,2},{bird,1},{bird,2},...]

Я хотел бы хранить все возможные перестановки этого списка в оперативной памяти.

Поскольку список может быть довольно длинным (10 элементов и более), его хранение занимает много места (факториал N).

Например, если у меня есть список, который занимает около 70 байт пространства и имеет 12 элементов, то мне нужно 12! * 70 ~ 31 GB, Если я добавлю еще один элемент в список, то может оказаться невозможным хранить перестановки в ОЗУ.

Есть ли более эффективное представление для хранения всех перестановок в памяти, чем следующее представление Эрланга?

[{dog,1},{dog,2},{cat,1},{cat,2},{bird,1},{bird,2},...]

(Я знаю что атом dog хранится только один раз в таблице атомов, но так как она повторяется при каждой перестановке, она занимает N памяти).

Может быть, эти перестановки могут быть сохранены в виде байтов? (Извините, я новичок в байтах и ​​двоичных файлах).

Ведь это просто одни и те же элементы, но переставленные по-разному.

Источник

3 ответа

Решение

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

Например (если вам нужно перебрать перестановки):

-record(perm, {list_a, list_b, index_a, index_b}).

Каждый раз, когда вы достигаете максимума index_b, вы сбросили его до 0 и приращение index_a с одним. Затем, получая доступ к N-му элементу списков (где N - индексы), вы можете воссоздать любой экземпляр перестановки.

Конечно, это означает, что вам придется обходить списки каждый раз, когда производится перестановка. Чтобы избежать этого, вы можете использовать списки в качестве самих индексов:

-record(perm2, {list_a, list_b, list_b_orig}).

Чтобы сгенерировать следующую перестановку, вставьте новый элемент из list_b и добавить его к главе list_a, Если list_b пусто, уберите голову list_a и начать заново, установив list_b к оригиналу, который сохраняется в list_b_orig,

Источник

Если у вас есть список из N элементов, есть N! Перестановки. Так что, если мы сможем произвести отображение из чисел от 1 до N! (или от 0 до N!-1) для этих перестановок воспроизводимым способом, нам не нужно хранить N! списки элементов, но только N! номера.

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

Извините, что не знаю Эрланга, но я написал функциональный алгоритм в Scala, который позволяет воспроизводить перестановки произвольного размера воспроизводимым образом.

Например, 123456790-й перестановкой чисел (от 1 до 12) является список (4, 2, 1, 5, 12, 7, 10, 8, 11, 9, 3, 6).

В качестве специального бонуса этот алгоритм производит перестановки отсортированным способом. Просто найти все перестановки в воспроизводимом виде, но без порядка проще:

def permutationIndex (idx: Int, list: List [Int]) : List [Int] = {
  if (list.isEmpty) list else {
    val el = list (idx % list.size) 
    el :: permutationIndex (idx / list.size, list.remove (_ == el))}}
Источник

Может быть, сжатие это сделает работу?

Модуль Zlib, кажется, делает что-то вроде этого.

Источник
Другие вопросы по тегам