Thursday, August 1, 2019

Combinations of all numbers in List

Recently I was asked this seemingly innocent problem, given an array of numbers, generate all combination of indices of all lengths possible. For example, if there is an array of length 3, the result should be combinations of all indices of length 1, 2 and 3. The answer should be like below.

{{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2}

The problem at first seemed extremely simple, but as I got down to writing code for it, it was clear very quickly that it is not that simple a problem. The final solution is not very complex. Basically, we start with all the sets of length 1 and then for every higher length, we create elements with all the indices prefixed to all the solutions of a lower length. Here is a solution that I finally came up with.