How do I get a list of permutations in one cell?

Question

Below is 5 columns - the 6th column contains the desired outcome: the names in the 5 columns in every permutation possible.

Two rows only have two columns with values - so only two permutations in column 6 (delimited by ";").

One row has 4 values, so 24 permutations.

Sorry for the image, I couldn't work out how to paste a table from Excel into Stack without having to rewrite it all.

Rows in the real dataset could have 1 value, 5 values, or anything in between.

The answers here only seem to work for a two dimensional array - this array is one dimensional. I can't think of any obvious way to make it 2d so that those solutions work, nor does that seem like an efficient way to do it. One of the formulas from the above answer is below (I had a look at all of them and couldn't figure how to adapt them to my needs):

=LET(A,A1:C3,B,ROWS(A),C,COLUMNS(A),D,B^C,E,UNIQUE(MAKEARRAY(D,C,LAMBDA(rw,cl,INDEX(IF(A="","",A),MOD(CEILING(rw/(D/(B^cl)),1)-1,B)+1,cl)))),FILTER(E,MMULT(--(E<>""),SEQUENCE(C,,,0))=C))

Most of the solutions I've googled also don't seem to work (or I can't make them work) on a simple array of 1 row and 5 columns.

I tried to do it from scratch, and got as far as generating a list of numbers containing only the digits 1-5 and with no repititions -

=LET(firstperm,VALUE(CONCAT(SEQUENCE(1,COLUMNS(Tablestu[@[First Name]:[Preferred Last Name]])))),lastperm,VALUE(CONCAT(SORT(SEQUENCE(1,COLUMNS(Tablestu[@[First Name]:[Preferred Last Name]])),,-1,TRUE))),diff,(lastperm-firstperm)+1,list,SEQUENCE(diff,1,firstperm),wanted,(IF((ISNUMBER(SEARCH("1",list))*ISNUMBER(SEARCH("2",list))*ISNUMBER(SEARCH("3",list))*ISNUMBER(SEARCH("4",list))*ISNUMBER(SEARCH("5",list))),list,"")),FILTER(wanted,wanted<>"",""))

Thinking I could then somehow split up these 5 digit numbers, and use an INDEX formula to return words in that order. I.e. 31452 would return the third word, then the first, then the fourth, and so on... but I am still a million keyboard-head-smashes away from turning this into what I need it for, and it will be stupidly inefficient when I even get there.

The answer linked seems like the right kind of thing - I'm using Excel 365 and I need a solution that uses formulas, not VBA or power query.

LAMDAs and LETs are fine.

Answer 1

Alternate solution:

=LET(range, A1:E1,
     f,     FILTER(range,range<>""),
     c,     COLUMNS(f),
     s,     c^c,
     a,     MAKEARRAY(  s, c,
               LAMBDA( rw, cl,
                       MOD(CEILING(rw/(s/(c^cl)),1)-1,c)+1)),
     p,     FILTER(a,
                   BYROW(  a,
                   LAMBDA( x,
                           AND(MMULT(N(TRANSPOSE(x)=x),SEQUENCE(c)^0)=1)))),
TEXTJOIN(";",,UNIQUE(BYROW(p,LAMBDA(x,TEXTJOIN("",1,CHOOSECOLS(f,x)))))))

This also takes into account that if a duplicate name is used within the range, it won't generate duplicate permutations.

EDIT: Solution based on version suggested by Bo Rydobon on Linked In (So credits to Bo, many thanks!).

=LET(z,TOROW(A2:L2,3),TEXTJOIN(";",,REDUCE(TOCOL(z),DROP(z,,1),LAMBDA(a,w,TOCOL(IFS(ISERR(FIND(z,a)),a&z),3)))))

This still leaves us with the character limit of the cell, but we could also spill the range:

=LET(z,TOROW(A2:L2,3),REDUCE(TOCOL(z),DROP(z,,1),LAMBDA(a,w,TOCOL(IFS(ISERR(FIND(z,a)),a&z),3))))

This alows up to 9 different cells containing a string to be permutated, after that we meet the boundaries of the excel sheet rows and it'll throw an error.

Answer 2

Caveat: this is not to be recommended as a general solution, though since the OP gives an upper bound of 5 on the number of entries it's perhaps worth considering.

=LET(
    ζ,A2:E2,
    ξ,COUNTA(ζ),
    κ,SEQUENCE(,ξ),
    λ,LEFT(12345,ξ),
    γ,REPT(1+ξ,ξ)-λ,
    δ,SEQUENCE(γ-λ+1,,λ),
    α,INDEX(FILTER(ζ,ζ<>""),
        MID(FILTER(δ,MMULT(N(ISERR(FIND(MID(λ,κ,1),δ))),TOCOL(κ))=0),κ,1)
      ),
    TEXTJOIN(";",,BYROW(α,LAMBDA(β,CONCAT(β))))
)

Answer 3

Considering the comments in previous answers, in regards to Excel performance and the fact that Excel doesn't provide an out-of-the-box permutation generator. This solution uses an efficient approach using Excel javascript integration via free Add-ins: Script Lab. It is a Microsoft Garage Project. It is multi-platform, I tested under Excel for the Web version, but you can try with Excel Desktop.

In regards to the javascript algorithm for doing permutation, I adapted two of them from the question: Permutations in JavaScript?.

By 'adapted' I mean:

• Add comments/@tags required for parameter definition. Check Office Script Metadata reference for more information.
• Convert the input array (arr) from a 2D array to a one-dimensional array. All the algorithms in the javascript question assume a one-dimensional array, but when we invoke a javascript function that receives an Excel range, such range is represented as a 2D array ([][]) even if it is a row/column wise range, so we use the javascript array built-in flat() method to do the conversion before calling the algorithm.

From @caub: Shortest one, but less efficient

/**
 * Generates all permutations without repetition of the input argument
 * @customfunction
 * @param {any[][]} arr Array of input values
 * @returns {any[][]} 2D array with all permutations.
 */
function permute(arr) {
  if (Array.isArray(arr[0])) {
    arr = arr.flat();
  }
  function recur(a) {
    if (!a.length) return [[]];
    return a.flatMap((x, i) => {
      return recur(a.filter((v, j) => i !== j)).map((vs) => [x, ...vs]);
    });
  }
  return recur(arr);
}

From @le_m: larger, but the most efficient one

/**
 * Generates all permutations without repetition of the input argument
 * @customfunction
 * @param {any[][]} arr Array of input values
 * @returns {any[][]} 2D array with all permutations.
 */
function permute_eff(arr) {
  if (Array.isArray(arr[0])) {
    arr = arr.flat();
  }
  var length = arr.length,
    result = [arr.slice()],
    c = new Array(length).fill(0),
    i = 1,
    k,
    p;

  while (i < length) {
    if (c[i] < i) {
      k = i % 2 && c[i];
      p = arr[i];
      arr[i] = arr[k];
      arr[k] = p;
      ++c[i];
      i = 1;
      result.push(arr.slice());
    } else {
      c[i] = 0;
      ++i;
    }
  }
  return result;
}

Having the javascript function, the next step is to invoke it from Excel. Thanks Script Lab, it is an easy task, I created a new Snippet, which I called lib. Then just to invoke it. For example:

The functions defined work as expected for row/column array input as well as for numeric or text data type. I tested both functions for finding all permutations for SEQUENCE(8) i.e. more than 40K permutations. It returns the result (both javascript formulas) in the range of 2-4 seconds, with no significant difference between them.

Now back to the original question. It results in a very straightforward formulation, then drag it down:

=TEXTJOIN(";",,BYROW(SCRIPTLAB.LIB.PERMUTE(FILTER(A2:E2,A2:E2<>"")),
  LAMBDA(x, CONCAT(x))))

Here is the output:

Note: You can import the lib Snippet via the following URL (Gist repository), using the Import option from Script Lab.

The only inconvenience of this solution is that it seems you cannot invoke a custom Script Lab function using the name of the LAMBDA as input for a dynamic array helper function such as BYROW. For example, the following doesn't work (feature request):

=BYROW(A2:E4, LAMBDA(x, 
 TEXTJOIN(";",,BYROW(SCRIPTLAB.LIB.PERMUTE(FILTER(x,x<>"")),
  LAMBDA(y, CONCAT(y))))))

so you cannot generate an array version that would spill the entire result. You get the following error, without too much information:

Obviously, you can create a more specific javascript function for this problem, so it receives a 2D array and for each row, generates the expected result, building all the logic inside javascript. In such a case, it spills the entire result, but this would be out of the scope of my answer. The current solution provided is good enough to show the point on how to integrate Excel with javascript functions in situations where Excel function/calculation is not efficient.

I hope it helps, I think it is a good workaround in situations where using Excel functions won't provide a good performance or it freezes, such as heavy computational processes like generating all permutations.

Answer 4

I'm adding this as an alternative, since the approach is significantly different to that used in my previous answer.

=LET(
    ζ,A2:E2,
    ξ,FILTER(ζ,ζ<>""),
    TEXTJOIN(";",,
        SORT(UNIQUE(BYROW(RANDARRAY(2^10,COLUMNS(ξ)),LAMBDA(γ,CONCAT(SORTBY(ξ,γ))))))
    )
)

As long as RANDARRAY's first parameter is chosen so as to be sufficiently large, the probability of the resulting array not being unique will be so small as to virtually guarantee a correct output. Here, 2^10 seems to be sufficient for up to 5 non-blank entries.

Again, this set-up is not readily extendible beyond 5 non-blank entries, though it's perhaps worth considering due to its succinctness and/or performance.