How to list all permutations without repetition?

The limitations described below are because of lambda functions. The first solution can be successfully implemented without lambda:

=ARRAYFORMULA(QUERY(BASE(SEQUENCE(PERMUTATIONA(7,7)),7,7),"where not Col1  matches '.*(("&JOIN(")|(",SEQUENCE(7,1,0)&".*"&SEQUENCE(7,1,0))&")).*'",0))

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 different SEQUENCEs 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 BASE equal 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., COUNTUNIQUE per number = 7(eg:0124536). Here’s a implementation:

=ARRAYFORMULA(LAMBDA(n,QUERY(BYROW(SPLIT(REGEXREPLACE(TO_TEXT(BASE(SEQUENCE(PERMUTATIONA(n,n)-1),n,n)),"\B","."),"."),LAMBDA(r, IF(COUNTUNIQUE(r)<>n,"👀",JOIN(,r)))),"where not Col1='👀' ",0))(5))

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:

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
Find the largest index l greater than k such that a[k] < a[l].
Swap the value of a[k] with that of a[l].
Reverse the sequence from a[k + 1] up to and including the final element a[n].

For example, given the sequence [1, 2, 3, 4] (which is in increasing order), and given that the index is zero-based, the steps are as follows:

Index k = 2, because 3 is placed at an index that satisfies condition of being the largest index that is still less than a[k + 1] which is 4.
Index l = 3, because 4 is the only value in the sequence that is greater than 3 in order to satisfy the condition a[k] < a[l].
The values of a[2] and a[3] are swapped to form the new sequence [1, 2, 4, 3].
The sequence after k-index a[2] to the final element is reversed. Because only one value lies after this index (the 3), the sequence remains unchanged in this instance. Thus the lexicographic successor of the initial state is permuted: [1, 2, 4, 3].

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 at n=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 even n=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 to 1.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:

  1.Pixie	2.Shikigami	3.Kodama	4.Hua Po	5.Datsue Ba	6.Angel	7.Fomorian

• A2:

  =GET_NEXT_LEX(A1:G1)
  

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):

=ARRAYFORMULA(
  TRANSPOSE(
    LAMBDA(arr,     
      LAMBDA(k,       
        LAMBDA(sarr,k,{SPLICE(sarr,k+1,2^999);REVERSE(SPLICE(sarr,1,k+1))})  
          (SWAP(arr,k,XMATCH(TRUE,INDEX(arr,k)<SPLICE(arr,1,k+1),,-1)+k),k)
      )(XMATCH(TRUE,POP(arr)<SHIFT(arr),,-1))
    )(TRANSPOSE(arr))
  )
)

Helper functions:

Functions similar to javascript or python

• SPLICE(arr,i,j)

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

• REVERSE(arr)

=POP(REDUCE(,arr,LAMBDA(a,c,{c;a})))

• SWAP(arr,i,j)

=SORT(arr,LAMBDA(keys,SWITCH(keys,i,j,j,i,keys))(SEQUENCE(ROWS(arr))),1)

• POP(arr)

=ARRAY_CONSTRAIN(arr,ROWS(arr)-1,1)

• SHIFT(arr)

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