Get all possible subsets - preserving order

Question

This is a follow up to this question: Generate all "unique" subsets of a set (not a powerset)

My problem is the same, but I think there might be a more optimized solution when order of items in the new subsets and across the subsets needs to be preserved.

Example:

[1, 2, 3]

Would result in:

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

Szabolcs · Answer 1 · 2012-03-16T15:57:57.480

3

If I understand it correctly, you want to insert "delimiters" into a list, to partition it. Taking your example, and using the | character to indicate the delimiter,

are the solutions you want.

In a list (I'm calling it a list and not a set because you need the order preserved) of n elements, there are n-1 potential positions for a delimiter. In the example above, there are two positions. In each position, a delimiter might or might not be present.

You can use the binary representation of numbers from 0 to 2^(n-1) - 1 to list all possible arrangements of delimiters. In your example, this'll be number from 0..3.

edited Mar 16 '12 at 15:57

answered Mar 16 '12 at 10:05

Szabolcs

24,728
9
85
174

This has been really helpful. Since I need combinations with exact number of delimiters, I found my problem can also be specialized to this question: http://stackoverflow.com/questions/1851134/generate-all-binary-strings-of-length-n-with-k-bits-set but since I have small sets the function given and filtering out non fitting combinations is good for now. – mbdev Mar 16 '12 at 18:11

score 2 · Accepted Answer · edited May 23 '17 at 12:30

I've already answered this question for Python, so I quickly ported my solution over 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 complete explanation of how and why this works.

Get all possible subsets - preserving order

2 Answers2

Linked