General Algorithm to optimize order of events while requiring the minimum number of changes

Question

I am trying to optimize the order of wedding photos with the family and others that need to be included. in order to keep the chaos and people wrangling to a minimum I am trying to optimize the order the pictures are taken so that there is the fewest number of changes required.

For example:

optimal:

Bride,Groom,Mom1,Dad1
Bride,Groom,Mom1,Dad1,Mom2,Dad2
Bride,Groom,Mom2,Dad2

non-optimal:

Bride,Groom,Mom1,Dad1
Bride,Groom,Mom2,Dad2
Bride,Groom,Mom1,Dad1,Mom2,Dad2

the non-optimal order requires Mom1 and Dad1 to come in to the picture, leave, then rejoin, whereas the first one they come in to the picture, stay and then are no longer needed I have a list of the 64 pictures that need to be taken, all with varying numbers of people in each picture

My approach so far has been to take the list of combinations and enter each combination into rows of a CSV file.

(56 unique individuals, 64 total pictures, all of varying numbers of participants,

ex:
picture 1,Bride,Groom,Mom1,Dad1
picture 2 Bride,Mom1,Dad1
picture 3 Groom,Mom1,Dad1
picture 4 Bride,Groom,Mom2,Dad2
etc...

I then made a dictionary where the keys are the people and the value is how many times they appear in a picture

beyond this I cannot think of how to logically step through this without issue

I can A: start with the largest picture and remove those that are not in another picture, slowly working my way to the smallest groups

or B: start at the smallest groups and add people until reaching the most inclusive pictures

I am unable to figure out a general way to approach this in a way I could code it

Answer 1

This is essentially a type of optimization problem called the "Minimum Set Cover Problem".

from typing import List, Dict, Set

def min_set_cover(photos: Dict[str, Set[str]]) -> List[str]:
    # Sort photos by the number of people, in descending order
    photos = sorted(photos.items(), key=lambda x: len(x[1]), reverse=True)

    result = []
    photographed = set()

    while photos:
        # Select the group with the maximum intersection with photographed people and minimum new people
        next_photo = max(photos, key=lambda x: (len(x[1] & photographed), -len(x[1])))
        result.append(next_photo[0])
        photographed |= next_photo[1]
        photos.remove(next_photo)

    return result

photos = {
    'photo1': {'Bride', 'Groom', 'Mom1', 'Dad1'},
    'photo2': {'Bride', 'Mom1', 'Dad1'},
    'photo3': {'Groom', 'Mom1', 'Dad1'},
    'photo4': {'Bride', 'Groom', 'Mom2', 'Dad2'}
}

print(min_set_cover(photos))  # Output: ['photo1', 'photo4', 'photo3']