I have a large list of over N = 1e7 variable length tuples. I want to use python to sample tuples from the list such that the concatenated tuples have K balanced characters. They may be multiple solutions, but I just want one solution.
Here is a simplified example. Say I want K = 4 from this list of tuples:
[ ('C', 'A', 'D'),
('D', 'E', 'A'),
('A', 'D', 'C', 'E'),
('D', 'B', 'A', 'B'),
('B', 'C'),
('B', 'D', 'E', 'B', 'C'),
('E', 'B', 'C'),
('E', 'A', 'B', 'A', 'E'),
('B', 'E', 'E', 'A'),
('A', 'D') ]
One solution has these indexes:
[0, 2, 4, 5, 8, 9]
Which has corresponding values:
[ ('C', 'A', 'D'),
('A', 'D', 'C', 'E'),
('B', 'C'),
('B', 'D', 'E', 'B', 'C'),
('B', 'E', 'E', 'A'),
('A', 'D') ]
Sorted and concatenated, the solution is clearly balanced:
['A', 'A', 'A', 'A',
'B', 'B', 'B', 'B',
'C', 'C', 'C', 'C',
'D', 'D', 'D', 'D',
'E', 'E', 'E', 'E']
My idea was to randomly sample tuples from the list until one of the characters totaled K = 4. Then, sample from the subset of remaining tuples that did not have the character. However, if there are no valid subsets, this means we would need to redo the original sample... potentially infinitely.
Is there a solution that is expected to finish in a reasonable number of finite steps?