mercredi 26 septembre 2018

generate all unique triplets

there is a series of triplets:

[[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12],[13, 14, 15]]

(can be longer than that). They are all unique.

Q: What is the efficient way of generating all possible combinations of these triplets such that none of the items that have met before, 'meet' again?

So for instance in this sequence none of triplets contain any items that encountered before:

[[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12],[13, 14, 15]]
[[1, 5, 9], [4, 8, 12], [7, 11, 15], [10, 14, 3],[2, 6, 13]]
[[1, 4, 7], [5, 8, 11], [9, 12, 15], [10, 13, 2],[14, 3, 6]]

but this one would not work:

[[1, 5, 9], [4, 6, 12], [7, 11, 15], [10, 14, 3],[2, 8, 13]]

because 4 and 6 from the second triplet have been in the same triplet before, specifically in [4, 5, 6] of the first record

I think that it can be done by picking random triplets from initial sequence using random.sample(l, 3) and then check if this triplet has not been used before, but it looks pretty unefficient and I wonder if there is a nicer way.




Aucun commentaire:

Enregistrer un commentaire