google-sheets google-sheets-formula permutation factorial

How to get permutations from factoradic numbers without lambda as a array formula?

Data:

Input#1(C1):

0,1,2

(A1)Input#2	Expected Output
0:0:0	0,1,2
0:1:0	0,2,1
1:0:0	1,0,2
1:1:0	1,2,0
2:0:0	2,0,1
2:1:0	2,1,0

Sample for 0,1,2,3,4 below:

For Input#1(C1): 0,1,2,3,4    
(A1)Input#2    Output
0:0:0:0:0   0,1,2,3,4
0:0:0:1:0   0,1,2,4,3
0:0:1:0:0   0,1,3,2,4
0:0:1:1:0   0,1,3,4,2
0:0:2:0:0   0,1,4,2,3
0:0:2:1:0   0,1,4,3,2
0:1:0:0:0   0,2,1,3,4
0:1:0:1:0   0,2,1,4,3
0:1:1:0:0   0,2,3,1,4
0:1:1:1:0   0,2,3,4,1
0:1:2:0:0   0,2,4,1,3
0:1:2:1:0   0,2,4,3,1
0:2:0:0:0   0,3,1,2,4
0:2:0:1:0   0,3,1,4,2
0:2:1:0:0   0,3,2,1,4
0:2:1:1:0   0,3,2,4,1
0:2:2:0:0   0,3,4,1,2
0:2:2:1:0   0,3,4,2,1
0:3:0:0:0   0,4,1,2,3
0:3:0:1:0   0,4,1,3,2
0:3:1:0:0   0,4,2,1,3
0:3:1:1:0   0,4,2,3,1
0:3:2:0:0   0,4,3,1,2
0:3:2:1:0   0,4,3,2,1
1:0:0:0:0   1,0,2,3,4
1:0:0:1:0   1,0,2,4,3
1:0:1:0:0   1,0,3,2,4
1:0:1:1:0   1,0,3,4,2
1:0:2:0:0   1,0,4,2,3
1:0:2:1:0   1,0,4,3,2
1:1:0:0:0   1,2,0,3,4
1:1:0:1:0   1,2,0,4,3
1:1:1:0:0   1,2,3,0,4
1:1:1:1:0   1,2,3,4,0
1:1:2:0:0   1,2,4,0,3
1:1:2:1:0   1,2,4,3,0
1:2:0:0:0   1,3,0,2,4
1:2:0:1:0   1,3,0,4,2
1:2:1:0:0   1,3,2,0,4
1:2:1:1:0   1,3,2,4,0
1:2:2:0:0   1,3,4,0,2
1:2:2:1:0   1,3,4,2,0
1:3:0:0:0   1,4,0,2,3
1:3:0:1:0   1,4,0,3,2
1:3:1:0:0   1,4,2,0,3
1:3:1:1:0   1,4,2,3,0
1:3:2:0:0   1,4,3,0,2
1:3:2:1:0   1,4,3,2,0
2:0:0:0:0   2,0,1,3,4
2:0:0:1:0   2,0,1,4,3
2:0:1:0:0   2,0,3,1,4
2:0:1:1:0   2,0,3,4,1
2:0:2:0:0   2,0,4,1,3
2:0:2:1:0   2,0,4,3,1
2:1:0:0:0   2,1,0,3,4
2:1:0:1:0   2,1,0,4,3
2:1:1:0:0   2,1,3,0,4
2:1:1:1:0   2,1,3,4,0
2:1:2:0:0   2,1,4,0,3
2:1:2:1:0   2,1,4,3,0
2:2:0:0:0   2,3,0,1,4
2:2:0:1:0   2,3,0,4,1
2:2:1:0:0   2,3,1,0,4
2:2:1:1:0   2,3,1,4,0
2:2:2:0:0   2,3,4,0,1
2:2:2:1:0   2,3,4,1,0
2:3:0:0:0   2,4,0,1,3
2:3:1:1:0   2,4,1,3,0
2:3:2:0:0   2,4,3,0,1
2:3:2:1:0   2,4,3,1,0
3:0:0:0:0   3,0,1,2,4
3:0:0:1:0   3,0,1,4,2
3:0:1:0:0   3,0,2,1,4
3:0:1:1:0   3,0,2,4,1
3:0:2:0:0   3,0,4,1,2
3:0:2:1:0   3,0,4,2,1
3:1:0:0:0   3,1,0,2,4
3:1:0:1:0   3,1,0,4,2
3:1:2:1:0   3,1,4,2,0
3:2:0:0:0   3,2,0,1,4
3:2:0:1:0   3,2,0,4,1
3:2:1:0:0   3,2,1,0,4
3:2:1:1:0   3,2,1,4,0
3:2:2:0:0   3,2,4,0,1
3:2:2:1:0   3,2,4,1,0
3:3:0:0:0   3,4,0,1,2
3:3:0:1:0   3,4,0,2,1
3:3:1:0:0   3,4,1,0,2
3:3:1:1:0   3,4,1,2,0
3:3:2:0:0   3,4,2,0,1
3:3:2:1:0   3,4,2,1,0
4:0:0:0:0   4,0,1,2,3
4:0:0:1:0   4,0,1,3,2
4:0:1:0:0   4,0,2,1,3
4:0:1:1:0   4,0,2,3,1
4:0:2:0:0   4,0,3,1,2
4:0:2:1:0   4,0,3,2,1
4:1:0:0:0   4,1,0,2,3
4:1:0:1:0   4,1,0,3,2
4:1:1:0:0   4,1,2,0,3
4:1:1:1:0   4,1,2,3,0
4:1:2:0:0   4,1,3,0,2
4:1:2:1:0   4,1,3,2,0
4:2:0:0:0   4,2,0,1,3
4:2:0:1:0   4,2,0,3,1
4:2:1:0:0   4,2,1,0,3
4:2:1:1:0   4,2,1,3,0
4:2:2:0:0   4,2,3,0,1
4:2:2:1:0   4,2,3,1,0
4:3:0:0:0   4,3,0,1,2
4:3:0:1:0   4,3,0,2,1
4:3:1:0:0   4,3,1,0,2
4:3:1:1:0   4,3,1,2,0
4:3:2:0:0   4,3,2,0,1
4:3:2:1:0   4,3,2,1,0

Constrains:

No lambda functions or their helpers, including but not limited to REDUCE,MAP,etc. Named functions without lambda/lambda helper functions are allowed.
No brute forcing. Need a dry, scalable solution. For eg, I might need a corresponding permutation for "5:4:0:0:0:1:0" for input#1 of 0,1,2,3,4,5,6
Must be ARRAYFORMULA solution in B2, which will fill all of B2:B for corresponding A2:A(no BYROW)
No workarounds. It maybe be a XY problem. I still need to solve Y, and not X.
Should go without saying, but No scripts
Should be able to handle ₈P₈(40320)factoradic numbers without issues
Recursion allowed. Turning on Iterative calculation not allowed.

Explanation:

Indexes start from 0 instead of 1. For Input#1, 0,1,2, For A2, 0:0:0, for the first 0, remove 0th element 0. The remaining array is 1,2. For the second 0, remove 0th element 1 from the remaining 1,2. For the third 0, remove 0th element 2. The final result 0,1,2 for 0:0:0. For 0:1:0:

index(from input#2)	remaining input#1	output
0	0,1,2 ^ ^ ^ [0],1,2 <<< Index	0
1	1,2 ^ ^ 0,[1] <<< Index	2
0	1 ^ [0] <<< Index	1

What can be assumed:

Input#1 will always be ascending sequence.
Length of input#1 will be equal to length of each of input#2

What cannot be assumed:

Number of elements will always be 3. No it may be so much more.

What have I tried?

Many things for days. The closest I got was a direct approach. But it's inefficient and most importantly, doesn't support arrays. I did it with named functions. Note the order of arguments matter. For eg, in SPLICE, the first argument should be a arr, then i and then j, exactly in that order as shown above.

`SHIFT(arr)`

Description:
- Removes first element in a array
Arguments:
- arr A vertical array to remove the first element eg: {1;2;3}
Formula definition:

=FILTER(arr,{0;SEQUENCE(ROWS(arr)-1)})

Example:

=SHIFT({1;2;3}) returns {2;3}

`SPLICE(arr,i,j)`

Description:
- Removes a part of the array.
Arguments(in order):
- arr A vertical array
- i Starting index to splice(inclusive)
- j Ending index to splice(exclusive)
Formula definition:

=FILTER(arr,LAMBDA(seq,(seq<i)+(seq>=j))(SEQUENCE(ROWS(arr))))

Example:
- =SPLICE({1;2;3;4;5},2,4) removes second to the fourth element. Returns {1;4;5}

`FACTTOPERM(inparr,factarr)`

Description:
- Returns corresponding permutation from factorial.
Arguments(in order):
- inparr Vertical input array (Eg: {0;1;2})
- factarr Vertical Factorial array+1 (Eg: {0;1;0}+1)
Formula definition:

=IF(ISERROR(JOIN(,inparr)),,INDEX(inparr,INDEX(factarr,1))&FACTTOPERM(SPLICE(inparr,INDEX(factarr,1),INDEX(factarr,1)+1),SHIFT(factarr)))

Example:

=ARRAYFORMULA(FACTTOPERM({0;1;2},{0;1;0}+1))

will give 021, because as seen in the above table, 0:1:0 corresponds to 0,2,1.

I can use BYROW to call it repeatedly, but it quickly hits lambda limitations. Here's how I used BYROW to call it:

(A1)Input#2	Output	0,1,2	Formula in C column
0:0:0	0,1,2	012	=ARRAYFORMULA(BYROW(A2:A7,LAMBDA(row, FACTTOPERM(TRANSPOSE(SPLIT(C1,",")),TRANSPOSE(SPLIT(row,":")+1)))))
0:1:0	0,2,1	021
1:0:0	1,0,2	102
1:1:0	1,2,0	120
2:0:0	2,0,1	201
2:1:0	2,1,0	210

References:

https://math.stackexchange.com/a/1400468

Solution

The point of the question is to avoid iteration and use vectorized methods(similar to such methods used in pandas) to support array formulas. The hardest problem here is how to vectorize parsing the lehmer code.

0	1	2

If you remove the middle element 1, we get,

0	2

Say, we want to take element with index 1, in the first array, that refers to the second element(index starting at 0). But after removing 1(with index 1) from the array, the same index 1, now refers to 2. Now, we can't just take stuff from a array in google-sheets and have a formula as array-formula. If we take 1 from the first row, we have to take it from all rows. And other rows might not have the same element to take from. Therefore, vectorization is lost, if we attempt removal. The question itself shows a non-vectorized operation working well.

Fortunately, there is a magic formula which solves the entire problem. That is IF. So, what we want is index 1 to refer to value 1. But, if we do this again, it needs to refer to the value 2. Take the opposite end of the spectrum. If we want index 0, that should stay the same even after index 1 is removed. In other words, every index to the right to the array, where we took a element, is to be reduced by 1, but every index to the left of it shouldn't have their index changed. The IF can be written like this:

=IF(elementTaken<=arr,arr-1,arr)

What this does is, it actually creates 2 arrays first:

arr-1:

-1	0	1

arr(unchanged):

0	1	2

Here, IF does it's magic, merging both arrays to a single one based on the elementTaken. If the element taken is 1, the final array is:

0 arr	0 arr-1	1 arr-1

This array is beautiful. We have first 0 at the right index 0 and first 1 at the right index 2. Now, all we have to do is provide vertical arrays as elementTaken. The Input#2, when split looks like,

Col1	Col2	Col3
0	0	0
0	1	0
1	0	0
1	1	0
2	0	0
2	1	0

If we provide the first column to IF, we get a merged array like this for 0, 1, 2:

First Col as elementTaken(say input Array),

Col1
0
0
1
1
2
2

A resulting merged array from IF. Let's call this comparisionArray

Col1	Col2	Col3
-1	0	1
-1	0	1
0	0	1
0	0	1
0	1	1
0	1	1

Now, since the indexes are all in the correct place. All we have to do is compare the next array(Col2) against the comparision array.

Col2
0
1
0
1
0
1

=IF(Col2=comparisionArray created previously, {0,1,2},)

This creates the result we need for the second array:

Col1	Col2	Col3
	1
		2
0	1
		2
0
	1	2

If we take the first element in each of those, we have the corresponding result Array:

ResArr(for Col2)
1
2
0
2
0
1

If we keep repeating this using recursion, we get 1 column for each recursion as a array formula.

Helper function:

DROP(rng, to_drop):

=FILTER(rng,
  ISNA(MATCH(SEQUENCE(
    IF(ROWS(to_drop)>COLUMNS(to_drop),ROWS(rng),1),
    IF(ROWS(to_drop)>COLUMNS(to_drop),1,COLUMNS(rng))
  ),to_drop,0))
)

A function to drop columns as needed.

Main function

PERM_FROM_FACT(inpArr,compArr,resArr,limit):

ARRAYFORMULA(
  IF(
    AND(ISNA(inpArr)),
    resArr,
    DROP(
      {
        IF(AND(resArr=""),INDEX(inpArr,0,1),resArr),
        PERM_FROM_FACT(
          DROP(inpArr,{1}),
          IF(
            INDEX(inpArr,0,1)<=compArr,
            compArr-1,
            compArr
          ),
          --REGEXEXTRACT(
            " "&TRANSPOSE(QUERY(TRANSPOSE(
              IF(
                INDEX(inpArr,0,1)=compArr,
                SEQUENCE(1,limit,0),
              )
            ),,9^99)),
            "^\s*(\d+)"
          ),
          limit
        )
      },
      IF(AND(resArr=""),{1},{0})
    )
  )
)

Usage:

=ARRAYFORMULA(PERM_FROM_FACT(SPLIT(A2:A8,":"),SPLIT(C1,","),,3))

Output:

Input#2	Expected Output	0,1,2	D1	E1	F1
0:0:0	0,1,2	0	1	2	=ARRAYFORMULA(PERM_FROM_FACT(SPLIT(A2:A8,":"),SPLIT(C1,","),,3))
0:1:0	0,2,1	0	2	1
1:0:0	1,0,2	1	0	2
1:1:0	1,2,0	1	2	0
2:0:0	2,0,1	2	0	1
2:1:0	2,1,0	2	1	0

We can join byrow if needed using QUERY(,, unlimited headers). I was hoping to avoid string manipulation or query hacks, but it was(seemed) impossible to get the first item per row in the comparison array without merging by row using query. So, it's used already. Since the values are basically indexes, you can use the resulting array to lookup any other array with HLOOKUP(or VLOOKUP) using key range as {SEQUENCE(3);keyArray} to get different permutations.

I was able to get 40k(8 item permutation) rows easily, which was not possible with DRY formulas known to human kind before. I wasn't able to see ₉P₉(300,000+) permutations in my system, within a reasonable time. Nevertheless, this is a beautiful solution crafted elegantly, with special attention to detail, memory size and number of operations.