Creating minimal groups from two lists

user_5492786 0
Viewed 115

I have a tuple containing a letter/name and a list of chars. I also have a list of purely chars. The idea is that I want to create new lists containing all the possible combinations of the letter/name from the tuple. Where their respective char list contains all the chars which is in the other char list. However this new list should be minimal, meaning there shouldn't be any redudant letter/names. An example, I have the following tuples,

('C', ['l'])
('D', ['l', 'q'])
('E', ['q', 's'])
('F', ['s'])
('H', ['q', 's'])

I should mention that the tuples are in a list aswell. So a list of tuples

The input list is, ['l', 'q', 's']

In this example I should get the following lists,

['C', 'E']
['C', 'H']
['D', 'E']
['D', 'F']
['D', 'H']

Because 'C' and 'E' combined gives ['l', 'q', 's'] and so forth. It should not return ['C', 'F', 'H'] Because here 'F' would be redundant.

My first thought was that I would check the result of appending each of them together. However this would not work for a larger example where the return list is larger than two chars.

algorithm python
1 Answers

This worked for me:

list_tuples = [('C', ['l']), ('D', ['l', 'q']),
               ('E', ['q', 's']), ('F', ['s']), ('H', ['q', 's'])]
input_list = ['l', 'q', 's']
out_list = []
for i in range(len(list_tuples)):
    for one_tuple in list_tuples:
        if list_tuples[i][0] != one_tuple[0]:
            to_compare_list = list_tuples[i][1] + one_tuple[1]
            counter = 0
            for one_letter in input_list:
                if one_letter in to_compare_list:
                    counter += 1
            if counter >= len(input_list):
                out_list.append([list_tuples[i][0], one_tuple[0]])

out_list = out_list[:int(len(out_list) / 2)]
print(out_list)

Output:

[['C', 'E'], ['C', 'H'], ['D', 'E'], ['D', 'F'], ['D', 'H']]

Please note that this code is not efficient, for better results refer to the itertools library in python that counts with permutation and combination modules.

EDIT

A corrected and more general solution:

import itertools
import copy

list_tuples = [('A', ['a', 'b', 'd', 'e']), ('B', ['d', 'e', 'i']), ('C', ['i', 'l', 'n']), ('D', ['l', 'n', 'o', 'r']), ('E', [
    'n', 'o', 'r', 's', 't']), ('F', ['a', 'b', 'r', 's', 't']), ('G', ['a', 'e', 'i', 'o']), ('H', ['b', 'e', 's'])]
input_list = ['a', 'b', 'd', 'e', 'i', 'l', 'n', 'o', 'r', 's', 't']
dic_of_list_tuples = dict(list_tuples)
keys = dic_of_list_tuples.keys()
out_list = []
posible_combinations = []
letter_space = []

for i in range(len(keys)):
    posible_combinations += list(itertools.combinations(keys, i + 1))

for one_combinations in posible_combinations:
    for one_letter in one_combinations:
        letter_space += dic_of_list_tuples[one_letter]
    if (all(item in letter_space for item in input_list)):
        out_list.append(list(one_combinations))
    letter_space = []

filter_out_list = copy.deepcopy(out_list)
for one_list in out_list:
    for i in range(len(out_list)):
        if (one_list != out_list[i]) and (all(item in out_list[i] for item in one_list)):
            try:
                filter_out_list.remove(out_list[i])
            except ValueError:
                pass

print(filter_out_list)

Output:

[['A', 'C', 'E'], ['B', 'D', 'F'], ['A', 'B', 'D', 'E'], ['A', 'C', 'D', 'F'], ['A', 'C', 'F', 'G'], ['A', 'D', 'E', 'G'], ['A', 'D', 'F', 'G'], ['B', 'C', 'E', 'F'], ['B', 'C', 'F', 'G'], ['B', 'C', 'E', 'G', 'H'], ['B', 'D', 'E', 'G', 'H']]
user_115960810
Related