Apriori Candidate Join

Perform the candidate-generation join step of the Apriori algorithm. prev is a collection of frequent $(k-1)(k-1)$-itemsets (each a sequence of items). Sort the itemsets and join every pair whose first $k-2k-2$ items agree, appending the last item of the second to the first. No pruning is applied.

Implement solve(prev).

Returns. Return a sorted list of distinct $kk$-item tuples.

Examples

Example 1

Input:

solve([('a', 'b'), ('a', 'c'), ('b', 'c')])

Output:

[('a', 'b', 'c')]

Example 2

Input:

solve([('a',), ('b',), ('c',)])

Output:

[('a', 'b'), ('a', 'c'), ('b', 'c')]