Get all possible subsets - save order

Question

This is the next question: Create all “unique” subsets of a set (not a set of parameters)

My problem is the same, but I think there may be a more optimized solution when it is necessary to preserve the order of elements in new subsets and subsets.

Example:

[1, 2, 3] 

Result:

 [[1], [2], [3]] [[1, 2], [3]] [[1], [2, 3]] [[1, 2, 3]] 

Answer 1

I already answered this question for Python , so I quickly ported my solution to Ruby:

 def spannings(lst) return enum_for(:spannings, lst) unless block_given? yield [lst] (1...lst.size).each do |i| spannings(lst[i..-1]) do |rest| yield [lst[0,i]] + rest end end end p spannings([1,2,3,4]).to_a 

See my other answer for a full explanation of how and why this works.

Answer 2

If I understand correctly, you want to insert “delimiters” in the list in order to split it. Taking your example and using the symbol | to indicate the delimiter

 1 2 3 1 2|3 1|2 3 1|2|3 

- the decisions you need.

In a list (I call it a list, not a collection, because you need order) of n elements, there are potential n-1 positions for the separator. There are two positions in the above example. At each position, a separator may or may not be present.

You can use the binary representation of numbers from 0 to 2^(n-1) - 1 to list all possible separator locations. In your example, it will be a number from 0..3.

 0: 00 1: 01 2: 10 3: 11