генерация большого количества перестановок с использованием Mathematica 5.2

Question

Я использую Mathematica 5.2. Я использовал команду Tuples для генерации перестановок, таких как:

In[1]:=Tuples[{0,1},3]

Out[1]={{0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1},{1,1,0},{1,1,1}}

Но проблема в том, что когда я хочу сгенерировать все возможные перестановки, разместив 0 и 1 в более чем 20 местах, команда Tuples не может выдать вывод из-за недостатка памяти. например, если я хочу сгенерировать большое количество перестановок, используя 0 и 1, например,

 Tuples[{0,1},25]

Команда «Кортежи» не выдает выходных данных, она выдает сообщение о том, что недостаточно места в памяти для генерации такого большого количества перестановок, так как я могу решить эту проблему? Есть ли другой процесс генерации больших перестановок? Или, если я хочу сгенерировать каждую из перестановок одну за другой вместо одновременной генерации в массиве, подобном выводу [1], как я могу это сделать?

Answer 1

Для создания списка этих перестановок в одной оценке требуется более 3 ГБ памяти.Вот вывод, полученный с помощью Mathematica 8:

In[1]:= NumberForm[ ByteCount [ Tuples[{0, 1}, 25] ], DigitBlock -> 3]
Out[1]//NumberForm= 3,355,443,368

Ядро Mathematica 5.2 является 32-разрядным исполняемым файлом и не может обрабатывать необходимый объем памяти.Вместо этого вы можете использовать цикл Do для создания одной перестановки за раз:

With[{n = 4}, Do[Print[IntegerDigits[i, 2, n]], {i, 0, 2^n - 1}]]

Answer 2

В вашем конкретном примере, Tuples из {0,1}, гораздо эффективнее хранить результаты в виде целых чисел.

a = Tuples[{0, 1}, 20];
b = Range[0, 2^20 - 1];

ByteCount /@ {a, b}

<b>  {83886168, 4194388}</b>

Length /@ {a, b}

<b>  {1048576, 1048576}</b>

a[[618021]] == IntegerDigits[ b[[618021]] , 2, 20]

<b>  True</b>

---

Использование памяти кортежей длиной 25:

Range[0, 2^25 - 1] // ByteCount

<b>  134217812</b>

Answer 3

Чтобы конкретно ответить на вопрос «Или, если я хочу сгенерировать каждую из перестановок одну за другой вместо одновременной генерации в массиве, подобном выводу [1], как я могу это сделать?»

Mathematica 5.2 использовала пакет дополнений Combinatorica для NextPermutation.

In[1]:= <<"DiscreteMath`Combinatorica`"

In[2]:= somepermutation={0,1,2}; NextPermutation[somepermutation]

Out[3]= {0,2,1}

In[4]:= NextPermutation[%]

Out[4]= {1,0,2}

In[5]:= NextPermutation[%]

Out[5]= {1,2,0}

и т. Д.Но NextPermutation корректно устанавливает только наборы, а не мультимножества.Книга ниже объясняет это, и есть обходные пути.

In[6]:= somepermutation={0,1,0};NextPermutation[somepermutation]

Out[7]= {0,0,1}

In[8]:= NextPermutation[%]

Out[8]= {0,1,0}

Если вы планируете использовать Combinatorica в Mathematica, то получите копию «Вычислительная дискретная математика, комбинаторика и теория графов с Mathematica» Пеммараю и Скиенырядом с вами будет необходимо.Части этого лучше написать в качестве справочного материала, но без него вам, вероятно, будет гораздо сложнее использовать Combinatorica