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

Question

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

[{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 памяти).

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

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

Answer 1

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

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

-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.

Answer 2

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

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

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

Например, 123456790-ая перестановка чисел (от 1 до 12) - это List (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))}}

Answer 3

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

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