1

I would like to generate partitions for a set in a specific way: I need to filter out all partitions which are not of size N in the process of generating these partitions. The general solution is "Generate all “unique” subsets of a set (not a powerset)".

For the set S with the following subsets:

[a,b,c]
[a,b]
[c]
[d,e,f]
[d,f]
[e]

and the following 'unique' elements:

a, b, c, d, e, f

the result of the function/method running with the argument N = 2 should be:

[[a,b,c], [d,e,f]]

While the following partitions should be filtered out by the function/method:

[[a,b,c], [d,f], [e]]
[[a,b], [c], [d,e,f]]
[[a,b], [c], [d,f], [e]]

The underlying data structure is not important and could be arrays, sets or whatever.

Reason: I need to filter some partitions out before I have the full set of all partitions, because the function/method which generates all partitions is rather computationally intensive.

According to "Generating the Partitions of a Set", the number of possible partitions can be huge: 44152005855084346 for 23 elements. My data is 50-300 elements in the starting set, so I definitely need to filter out partitions that have size not equal to N before I save them anywhere.

Community
  • 1
  • 1
skanatek
  • 5,133
  • 3
  • 47
  • 75
  • 1
    are you using `Set` objects, or arrays? – m_x Dec 27 '11 at 16:03
  • Why does `N=2` produce sets which have three elements? Are you using zero-based counting? Or is that the number of subsets in the resulting set? – Phrogz Dec 27 '11 at 17:10
  • @Phrogz, N is the number of subsets in the resulting set. – skanatek Dec 27 '11 at 18:20
  • 1
    If you are using arrays, you should write so in the question. In the question, you write as if they are sets, and that is making it confusing. – sawa Dec 27 '11 at 19:13
  • Are you saying that `S = [["a", "b", "c"], ["a", "b"], ["c"], ["d", "e", "f"], ["d", "f"], ["e"]]`? – the Tin Man Dec 28 '11 at 09:29
  • the Tin Man, if you are asking if a, b, c, d, e, f can be in different subsets of S, then yes. S is a set of sets. However I do not see any difference between [[a,b]] and [["a","b"]]. There is a difference between [[a,b], [a,b,c]] and simply [a,b]. The former is a set of sets, the latter is just a set. – skanatek Jan 10 '12 at 11:09

1 Answers1

0

Once you have the partitions as given by Frederick Cheung that you linked, do:

partitions.select{|partition| partition.length == 2}
sawa
  • 165,429
  • 45
  • 277
  • 381
  • thanks, but I can not use this obvious solution due to the fact that I need to filter the partitions out right in the process of their generation. – skanatek Dec 27 '11 at 18:24