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

Question

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

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

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

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

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

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

[{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}). 

Everytime вы достигнете максимума 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

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

Zlib модуль, похоже, что-то вроде этого.

Answer 3

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

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

Извините, что не знаю Erlang, но I wrote a functional algorithm in 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))}}