Coda Formula Challenge: All Combinations

Given a list of elements, return all possible combinations of those elements of all possible lengths.

For example, given this list List(A,B,C,D) return this result:

The result you return can be in any order. All that matters are the combinations.

Ideally, the result does not use a helper table, it’s just a pure Coda formula. Honestly, I haven’t figured it out yet. Have fun!

Found a solution!
all combinations of all lengths

However, my solution is very inefficient. It generates all possible permutations, then filters down to the ones that are correct.

Would love to see what others come up with.

@Paul_Danyliuk @Federico.Stefanato @joost_mineur @Ryan_Martens2 @Johg_Ananda I’ve been placed on this earth to tempt you with Coda puzzles

Oh no. My day shall now be wasted.

Honestly cannot think about any more optimized algorithm given that we don’t have recursion in Coda. If the task was to only get permutations of a hard-coded length that would be easier.

We do have a sort of formulaic WHILE loops in Coda so let me give it a try with two formulas recursively updating each other.

1 Like

Well, this algorithm is not ideal either because it uses expensive Unique() on the end result (otherwise it produces many duplicates) but it’s an alternative:

Maybe I can adjust the algorithm to eliminate duplicates as soon as those get collected.

2 Likes

Also, figured I’d share this, it’s the background behind my approach:

And the idea behind my algo is this iterative subtractive approach:

  1. Construct a list where the only element is the full set

    [ [A, B, C, D] ]
    
  2. For each set on the list (which so far is the only item – the full set) take it and for as many times as there are elements in that set, remove one element from it, a different one each time:

    [ [A, B, C, D] ] -> [ [B, C, D], [A, C, D], [A, B, D], [A, B, C] ]
    
  3. If there are duplicates, remove them using Unique() (this is the step yet to be optimized if possible)

  4. Repeat steps 2-3 until we have sets of size 1 in that list and there’s no further way to take away items.

    [ [B, C, D], [A, C, D], [A, B, D], [A, B, C] ]
      -> [ [C, D], [B, D], [B, C], [C, D], [A, D], [A, C], ... ]
    
  5. The collection of all sets produced in step 3, along with the initial set, is the result.


Sure it’s not the best algo because it still calculates duplicate sets, e.g. [C, D] is retrieved from both [A, C, D] and [B, C, D], which need to be deduped. The most straightforward one would be the “additive” approach, i.e. for all items in the list take an item and repeat the algo recursively for all the items in the remaining list. But I’m not sure if computationally that one would be easier. Also a pretty hard limitation is that we don’t have ListCombine() that would only unwrap lists up to a certain level and not flatten them completely.

1 Like

Hey @Connor_McCormick1 ,
Is the list always going to have unique values, or also duplicates?
As in: List(A,A,B,C) might, among others, allow for AAB, or would AAB be excluded?
Greetings,
Joost

The list will always have unique values. It will never have AABC