How to create list of sets with k+1 elements from list of set with k elements if order does not matter?

I am trying to implement a variant of the Apriori algorithm which involves forming lists of sets of size k+1 from lists of sets of size k. For example, if I had list [[1], [2], [3], [4]], I would like to form list [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]] and then[[1,2,3], [1,2,4], [2,3,4]]. I have considered using a LinkedHashSet data structure to prune out repeated elements, but LinkedHashSets don't prune out cases in structure [x, y] [y, x] which I want removed. Does anyone have any suggestions or experience in stuff like this?

Thanks

2 Answers
2

Store the sets as values in a Hashtable with keys consisting of the list, sorted, joined with a separator. This will cause [x, y] and [y, x] to both be stored under the key String.format('%d:%d', x, y) (assuming that x <= y). This will let you catch duplicates.

Hashtable

[x, y]

[y, x]

String.format('%d:%d', x, y)

x <= y

This will be slow. Try it on large data with many items. You'll run into combinatorial explosion.

There are good reasons why APRIORI sorts it's data, and why it does the more complicated (but way more efficient) AprioriGen method, as well as the hash tree.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.