The current post is a follow-up question to this linked one:
Surprise! My problem child is actually for Shin Megami Tensei 3 permutations -- for a video game. I thought putting it into terms of trading cards would make more sense to the layman. Forgive me.
Okay. I messed around with a data set of 7 unique monsters (an initial set that's easy to obtain early in the video game). They can't be duplicated in my party but can be combined to make different ones. At the start, there are just 8 slots available for monsters in the video game.
This project focuses on building all the permutations of a "fusion chain" that attempts to take these monsters and arrange them into unique orders for a later combination within this chain.
It starts with A+B and then cleans that list to eliminate any B+A scenarios from the initial pairings (fusing A+B or B+A makes the same result). Then, the fusions just tack on C, D, E, F, G, and H (currently broken) to the result of the previous fusion until no more possible fusions remain (having only a single monster in my party).
The problem is this: the query or other functions within the permutation cell throw the error "The resulting array was too large" when attempting to list permutations for sorting 8 monsters at once -- even before the fusions can happen. I have isolated the issue to this formula (a bit long):
=iferror(if(counta($A$2:$A$13)>=2,arrayformula(query(query(split(flatten(flatten(flatten(flatten(flatten(flatten(
filter($F$2:$F,$F$2:$F<>"")&if(counta($A$2:$A$13)>=3,","&transpose(
filter($A$2:$A$13,$A$2:$A$13<>"")),""))&if(counta($A$2:$A$13)>=4,","&transpose(
filter($A$2:$A$13,$A$2:$A$13<>"")),""))&if(counta($A$2:$A$13)>=5,","&transpose(
filter($A$2:$A$13,$A$2:$A$13<>"")),""))&if(counta($A$2:$A$13)>=6,","&transpose(
filter($A$2:$A$13,$A$2:$A$13<>"")),""))&if(counta($A$2:$A$13)>=7,","&transpose(
filter($A$2:$A$13,$A$2:$A$13<>"")),""))&if(counta($A$2:$A$13)>=8,","&transpose(
filter($A$2:$A$13,$A$2:$A$13<>"")),"")),","),
"where Col1 <> Col2"&
if(counta($A$2:$A$13)>=3," and Col1 <> Col3 and Col2 <> Col3"&
if(counta($A$2:$A$13)>=4," and Col1 <> Col4 and Col2 <> Col4 and Col3 <> Col4"&
if(counta($A$2:$A$13)>=5," and Col1 <> Col5 and Col2 <> Col5 and Col3 <> Col5 and Col4 <> Col5"&
if(counta($A$2:$A$13)>=6," and Col1 <> Col6 and Col2 <> Col6 and Col3 <> Col6 and Col4 <> Col6 and Col5 <> Col6"&
if(counta($A$2:$A$13)>=7," and Col1 <> Col7 and Col2 <> Col7 and Col3 <> Col7 and Col4 <> Col7 and Col5 <> Col7 and Col6 <> Col7"&
if(counta($A$2:$A$13)>=8," and Col1 <> Col8 and Col2 <> Col8 and Col3 <> Col8 and Col4 <> Col8 and Col5 <> Col8 and Col6 <> Col8 and Col7 <> Col8",),),),),),),0),"where Col1 <>''",0)),"not enough data"),)
And the first range this formula was looking at is here in its previously stable form (column F):
| unique init pairs |
|---|
| Pixie,Shikigami |
| Kodama,Pixie |
| Hua Po,Pixie |
| Datsue-Ba,Pixie |
| Angel,Pixie |
| Fomorian,Pixie |
| Kodama,Shikigami |
| Hua Po,Shikigami |
| Datsue-Ba,Shikigami |
| Angel,Shikigami |
| Fomorian,Shikigami |
| Hua Po,Kodama |
| Datsue-Ba,Kodama |
| Angel,Kodama |
| Fomorian,Kodama |
| Datsue-Ba,Hua Po |
| Angel,Hua Po |
| Fomorian,Hua Po |
| Angel,Datsue-Ba |
| Datsue-Ba,Fomorian |
| Angel,Fomorian |
It was provided by a sort of "cleaner" formula I made but that isn't the problem.
The overall input I was testing is like this (in column A) and is also the input for the cleaner formulas for the initial pairs:
| available |
|---|
| Pixie |
| Shikigami |
| Kodama |
| Hua Po |
| Datsue Ba |
| Angel |
| Fomorian |
| High Pixie |
And the expected output... is really big. Here's a sample of the first lines to get an idea (hosted in H2 of the original sheet):
| A | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|
| Pixie | Shikigami | Kodama | Hua Po | Datsue Ba | Angel | Fomorian | High Pixie |
| Pixie | Shikigami | Kodama | Hua Po | Datsue Ba | Fomorian | Angel | High Pixie |
| Pixie | Shikigami | Kodama | Hua Po | Angel | Datsue Ba | Fomorian | High Pixie |
| Pixie | Shikigami | Kodama | Hua Po | Angel | Fomorian | Datsue Ba | High Pixie |
| Pixie | Shikigami | Kodama | Hua Po | Fomorian | Datsue Ba | Angel | High Pixie |
| Pixie | Shikigami | Kodama | Hua Po | Fomorian | Angel | Datsue Ba | High Pixie |
| Pixie | Shikigami | Kodama | Datsue Ba | Hua Po | Angel | Fomorian | High Pixie |
| and so on... |
I am currently at a loss for how to fix this problem. I would like to fit at least 8 starting monsters within my sheets for analysis, if not a full 12 for the end of the game.
There is probably a better, more compact way to generate these permutations than the way I have. I would probably like to boot up Excel to try this on my suped-up system and then see where it breaks offline. Yet, I want more efficient formulae to work around my "array too large" issues in Google Sheets. It's where I work best and where I have many other projects.
The limitations described below are because of lambda functions. The first solution can be successfully implemented without lambda:
The trick here is to use regex to find unique elements using query...match. The only problem with this is memory size needed will exceed 10 million for 8 items
PERMUTATIONA(8,8). But that can be overcome with repeating the formula with differentSEQUENCEs in a array{}.There are different algorithms to implement this. See Permutation in computing:
The straight forward and the easiest approach is create a sequence of numbers with
BASEequal to the number of items to choose from. For eg, if there are 7 items to choose from, create a sequence like this:Notice at each position, there are 7 variables(0 to 6) and there are 7 positions. Once we get all the numbers for
PERMUTATIONA(7,7), it's a simple matter of removing all the duplicates only getting numbers, where all numbers in each position are unique, i.e.,COUNTUNIQUEper number = 7(eg:0124536). Here's a implementation:Unfortunately, Google arbitrarily limited execution to less than a few seconds. So, this formula is unable to get all permutations for more than
n=5.The next in the list is using factorial(Lehmer's code) to get the permutations. See permutations here. Note how there's a direct relation between a sequence of numbers and permutation.
Table from https://wikipedia.org/wiki/Factorial_number_system Licensed under CC-BY-SA 3.0
I implemented this algorithm and I've hit Google's limit again at
n=5. (Code not shown here).Up next, we have Lexicographic ordering. Algorithm is as follows:
Quoted from https://en.wikipedia.org/wiki/Permutation Licensed under CC-BY-SA 3.0
Thanks to Google's latest support for recursion and named functions, I implemented this and I was able to get up to
n=6(720 items) within a single formula, but I still hit the Google's recursion limit atn=7(5040 items). Having said that, it's still possible to get all the 5k permutations one by one without a array formula(and maybe evenn=8(40320 items) depending on what your device can handle).Showing the first few permutations for
n=7. For the formula to work, it's important to note that there must be a inherent ascending order in the list. I added prefixes:1.,2., etc to1.Pixie,2.Shikigami... and so on to enforce ascending order. It is possible to the order within the formula itself, but it's not implemented.A1:G1:A2:Drag fill or auto fill down as much as needed (40k or 5k rows). The advantage of using this method is, you can continue where you left off. If you need 2 million permutations, and Google sheets cannot handle more than 1 million. You can put the first million in one spreadsheet and continue the next million in another(all you need is the last permutation from the previous spreadsheet).
Named functions:
Create these functions
Main function:
GET_NEXT_LEX(arr):Helper functions:
Functions similar to javascript or python
SPLICE(arr,i,j)REVERSE(arr)SWAP(arr,i,j)POP(arr)SHIFT(arr)