from __future__ import division
from itertools import * # your code goes here
 
data = [('Plate 1',[('A',i) for i in range(92)]),
        ('Plate 2',[('A',i) for i in range(92)]),
        ('Plate 3',[('A',i) for i in range(64)]),
        ('Plate 4',[('A',i) for i in range(42)]+[('B',j) for j in range(42,92)]),
        ('Plate 5',[('A',i) for i in range(12)]+[('B',j) for j in range(12,61)]),
        ('Plate 6',[('B',i) for i in range(92)])]   
 
# make data longer - note the solution will still be the same as we're adding in
# exactly the same ratio
#data = data + [d for d in data] + [d for d in data]
 
def powerset_no_empty(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(1,len(s)+1))
 
tot_types = 0
tot_A = 0
for name,samples in data:
    tot_types += len(samples)
    tot_A += len([t for t in samples if t[0]=='A'])
 
#calculate the target ratio for each bin
ratio_A = tot_A / tot_types # note ratio_B = 1.0 - ratio_A
 
p = powerset_no_empty(data)
 
scores = []
comb_ratios = []
num_batch_list = []
comb_list = []
print(p)
for j in p:
    batch_types = 0
    batch_A = 0
    for name,samples in j:
        batch_types += len(samples)
        batch_A += len([t for t in samples if t[0]=='A'])
 
    batch_ratio = batch_A/batch_types
    num_batches = int(batch_types/(3*92)+1)
 
    #You might want to change the line below to weight nearness of ratio
    #and number of batches differently in the group score
    score = abs(batch_ratio - ratio_A) + num_batches
    comb_ratios.append(batch_ratio)
    num_batch_list.append(num_batches)
    scores.append(score)
    comb_list.append(j)
 
ranked_combs = sorted(zip(scores,comb_ratios,num_batch_list,comb_list))
 
plate_list = [k[0] for k in ranked_combs[0][3]]
print('Best combination found was using {} in {} batches'.format(plate_list,ranked_combs[0][2]))
 
#for score, ratio, batches, combo in ranked_combs:
#    print(score, ratio, batches, [k[0] for k in combo])# your code goes here

ZnJvbSBfX2Z1dHVyZV9fIGltcG9ydCBkaXZpc2lvbgpmcm9tIGl0ZXJ0b29scyBpbXBvcnQgKiAjIHlvdXIgY29kZSBnb2VzIGhlcmUKIApkYXRhID0gWygnUGxhdGUgMScsWygnQScsaSkgZm9yIGkgaW4gcmFuZ2UoOTIpXSksCiAgICAgICAgKCdQbGF0ZSAyJyxbKCdBJyxpKSBmb3IgaSBpbiByYW5nZSg5MildKSwKICAgICAgICAoJ1BsYXRlIDMnLFsoJ0EnLGkpIGZvciBpIGluIHJhbmdlKDY0KV0pLAogICAgICAgICgnUGxhdGUgNCcsWygnQScsaSkgZm9yIGkgaW4gcmFuZ2UoNDIpXStbKCdCJyxqKSBmb3IgaiBpbiByYW5nZSg0Miw5MildKSwKICAgICAgICAoJ1BsYXRlIDUnLFsoJ0EnLGkpIGZvciBpIGluIHJhbmdlKDEyKV0rWygnQicsaikgZm9yIGogaW4gcmFuZ2UoMTIsNjEpXSksCiAgICAgICAgKCdQbGF0ZSA2JyxbKCdCJyxpKSBmb3IgaSBpbiByYW5nZSg5MildKV0gICAKCiMgbWFrZSBkYXRhIGxvbmdlciAtIG5vdGUgdGhlIHNvbHV0aW9uIHdpbGwgc3RpbGwgYmUgdGhlIHNhbWUgYXMgd2UncmUgYWRkaW5nIGluCiMgZXhhY3RseSB0aGUgc2FtZSByYXRpbwojZGF0YSA9IGRhdGEgKyBbZCBmb3IgZCBpbiBkYXRhXSArIFtkIGZvciBkIGluIGRhdGFdCiAKZGVmIHBvd2Vyc2V0X25vX2VtcHR5KGl0ZXJhYmxlKToKICAgIHMgPSBsaXN0KGl0ZXJhYmxlKQogICAgcmV0dXJuIGNoYWluLmZyb21faXRlcmFibGUoY29tYmluYXRpb25zKHMsIHIpIGZvciByIGluIHJhbmdlKDEsbGVuKHMpKzEpKQogCnRvdF90eXBlcyA9IDAKdG90X0EgPSAwCmZvciBuYW1lLHNhbXBsZXMgaW4gZGF0YToKICAgIHRvdF90eXBlcyArPSBsZW4oc2FtcGxlcykKICAgIHRvdF9BICs9IGxlbihbdCBmb3IgdCBpbiBzYW1wbGVzIGlmIHRbMF09PSdBJ10pCiAKI2NhbGN1bGF0ZSB0aGUgdGFyZ2V0IHJhdGlvIGZvciBlYWNoIGJpbgpyYXRpb19BID0gdG90X0EgLyB0b3RfdHlwZXMgIyBub3RlIHJhdGlvX0IgPSAxLjAgLSByYXRpb19BCiAKcCA9IHBvd2Vyc2V0X25vX2VtcHR5KGRhdGEpCiAKc2NvcmVzID0gW10KY29tYl9yYXRpb3MgPSBbXQpudW1fYmF0Y2hfbGlzdCA9IFtdCmNvbWJfbGlzdCA9IFtdCnByaW50KHApCmZvciBqIGluIHA6CiAgICBiYXRjaF90eXBlcyA9IDAKICAgIGJhdGNoX0EgPSAwCiAgICBmb3IgbmFtZSxzYW1wbGVzIGluIGo6CiAgICAgICAgYmF0Y2hfdHlwZXMgKz0gbGVuKHNhbXBsZXMpCiAgICAgICAgYmF0Y2hfQSArPSBsZW4oW3QgZm9yIHQgaW4gc2FtcGxlcyBpZiB0WzBdPT0nQSddKQoKICAgIGJhdGNoX3JhdGlvID0gYmF0Y2hfQS9iYXRjaF90eXBlcwogICAgbnVtX2JhdGNoZXMgPSBpbnQoYmF0Y2hfdHlwZXMvKDMqOTIpKzEpCiAgICAKICAgICNZb3UgbWlnaHQgd2FudCB0byBjaGFuZ2UgdGhlIGxpbmUgYmVsb3cgdG8gd2VpZ2h0IG5lYXJuZXNzIG9mIHJhdGlvCiAgICAjYW5kIG51bWJlciBvZiBiYXRjaGVzIGRpZmZlcmVudGx5IGluIHRoZSBncm91cCBzY29yZQogICAgc2NvcmUgPSBhYnMoYmF0Y2hfcmF0aW8gLSByYXRpb19BKSArIG51bV9iYXRjaGVzCiAgICBjb21iX3JhdGlvcy5hcHBlbmQoYmF0Y2hfcmF0aW8pCiAgICBudW1fYmF0Y2hfbGlzdC5hcHBlbmQobnVtX2JhdGNoZXMpCiAgICBzY29yZXMuYXBwZW5kKHNjb3JlKQogICAgY29tYl9saXN0LmFwcGVuZChqKQogCnJhbmtlZF9jb21icyA9IHNvcnRlZCh6aXAoc2NvcmVzLGNvbWJfcmF0aW9zLG51bV9iYXRjaF9saXN0LGNvbWJfbGlzdCkpCgpwbGF0ZV9saXN0ID0gW2tbMF0gZm9yIGsgaW4gcmFua2VkX2NvbWJzWzBdWzNdXQpwcmludCgnQmVzdCBjb21iaW5hdGlvbiBmb3VuZCB3YXMgdXNpbmcge30gaW4ge30gYmF0Y2hlcycuZm9ybWF0KHBsYXRlX2xpc3QscmFua2VkX2NvbWJzWzBdWzJdKSkKCiNmb3Igc2NvcmUsIHJhdGlvLCBiYXRjaGVzLCBjb21ibyBpbiByYW5rZWRfY29tYnM6CiMgICAgcHJpbnQoc2NvcmUsIHJhdGlvLCBiYXRjaGVzLCBba1swXSBmb3IgayBpbiBjb21ib10pIyB5b3VyIGNvZGUgZ29lcyBoZXJl