Minimum cases of n choose k with respect of n choose q

Question

I have a list

people = ['P1', 'P2', 'P3', 'P4', 'P5', 'P6', 'P7']

allComb4 = list(itertools.combinations(people,4)) # n choose k
#[('P1', 'P2', 'P3', 'P4'), ('P1', 'P2', 'P3', 'P5'), ('P1', 'P2', 'P3', 'P6'), ('P1', 'P2', 'P3', 'P7'), ('P1', 'P2', 'P4', 'P5'), ('P1', 'P2', 'P4', 'P6'), ('P1', 'P2', 'P4', 'P7'), ('P1', 'P2', 'P5', 'P6'), ('P1', 'P2', 'P5', 'P7'), ('P1', 'P2', 'P6', 'P7'), ('P1', 'P3', 'P4', 'P5'), ('P1', 'P3', 'P4', 'P6'), ('P1', 'P3', 'P4', 'P7'), ('P1', 'P3', 'P5', 'P6'), ('P1', 'P3', 'P5', 'P7'), ('P1', 'P3', 'P6', 'P7'), ('P1', 'P4', 'P5', 'P6'), ('P1', 'P4', 'P5', 'P7'), ('P1', 'P4', 'P6', 'P7'), ('P1', 'P5', 'P6', 'P7'), ('P2', 'P3', 'P4', 'P5'), ('P2', 'P3', 'P4', 'P6'), ('P2', 'P3', 'P4', 'P7'), ('P2', 'P3', 'P5', 'P6'), ('P2', 'P3', 'P5', 'P7'), ('P2', 'P3', 'P6', 'P7'), ('P2', 'P4', 'P5', 'P6'), ('P2', 'P4', 'P5', 'P7'), ('P2', 'P4', 'P6', 'P7'), ('P2', 'P5', 'P6', 'P7'), ('P3', 'P4', 'P5', 'P6'), ('P3', 'P4', 'P5', 'P7'), ('P3', 'P4', 'P6', 'P7'), ('P3', 'P5', 'P6', 'P7'), ('P4', 'P5', 'P6', 'P7')]

allComb2 = list(itertools.combinations(people,2)) # n choose q
# [('P1', 'P2'), ('P1', 'P3'), ('P1', 'P4'), ('P1', 'P5'), ('P1', 'P6'), ('P1', 'P7'), ('P2', 'P3'), ('P2', 'P4'), ('P2', 'P5'), ('P2', 'P6'), ('P2', 'P7'), ('P3', 'P4'), ('P3', 'P5'), ('P3', 'P6'), ('P3', 'P7'), ('P4', 'P5'), ('P4', 'P6'), ('P4', 'P7'), ('P5', 'P6'), ('P5', 'P7'), ('P6', 'P7')]

I need to find in allComb4 minimum number of elements with respect of allComb2. Desired result like bellow.

output = [['P1', 'P2', 'P5', 'P6'], ['P1', 'P3', 'P4', 'P7'], ['P2', 'P3', 'P5', 'P7'], ['P2', 'P4', 'P5', 'P6'], ['P3', 'P4', 'P6', 'P7']]

That means, any pair I pick up from allComb2 I will find that pair elements in one element of output. How can I do that?

LE: Always q < k

Answer 1

If I understand correctly, you want to constitute the minimal number of groups of 4 persons where every pair of persons is included in at least one of the groups.

If so, here is an example of implementation:

people = {'P1', 'P2', 'P3', 'P4', 'P5', 'P6', 'P7'}
people_total = len(people)

group_total = 4  # size of groups we want to constitute

visited_persons = {
    person: {person}
    for person in people
}

minimum_groups = []

while any(len(v) < people_total for v in visited_persons.values()):  # while there is someone who hasn't visited another person
    # take the person who has visited the least
    person = min(people, key=lambda p: (len(visited_persons[p]), p))

    # start a new group with this person
    group = {person}
    while len(group) < group_total:
        # find the person which knowns the least people
        person = min(people - group, key=lambda p: len(visited_persons[p] & group))

        # save visits
        for other in group:
            visited_persons[person].add(other)
            visited_persons[other].add(person)

        group.add(person)

    minimum_groups.append(group)

print(minimum_groups)

It prints [{'P1', 'P3', 'P4', 'P2'}, {'P1', 'P6', 'P5', 'P7'}, {'P7', 'P5', 'P4', 'P2'}, {'P5', 'P6', 'P3', 'P7'}, {'P1', 'P4', 'P6', 'P2'}]

The idea then is to build groups one by one, by keeping track of who has visited who in the visited_persons. We create a new group by considering the person who has visited the least people. Then we add people in the group who have the less visited the others in the group.

Answer 2

import itertools, math

E = 7 # number of elements
K = 4 # E choose K
Q = 3 # E choose Q

# construct list
a = [x for x in range(1, E+1)]

# construct combinations
allCombQ = list(itertools.combinations(a,Q))
allCombK = list(itertools.combinations(a,K))

# start iteration
iteration = 1
coverDone = False
while not coverDone:
    iteration += 1
    if iteration > len(allCombK):
        break
    print("Iteration: ", iteration)

    # scan combinations `len(allCombK)` choose `iteration`
    for sublist in itertools.combinations([x for x in range(len(allCombK))], iteration):
        sublist = list(sublist)
        sublistFound = True

        # check if every element of set of allComb2 exists in subslist (construct above)
        for subCombQ in allCombQ:
            subCombQ = list(subCombQ)
            foundInK = False
            for subCombK in sublist:
                subCombK = list(allCombK[subCombK])
                check = all(item in subCombK for item in subCombQ)
                if check:
                    foundInK = True
                    break
            if not foundInK:
                sublistFound = False
                break
        if sublistFound:
            coverDone = True
            break

for i in sublist:
    print(allCombK[i])

for Q=2 take few seconds to finish

for Q=3 is still working for about 90 minutes

Any optimisation is welcome.