algorithm - 为家庭创造一个家务轮

Question

有点愚蠢的问题，但很有趣，在我看来，它应该是一个“已解决的问题”。我主要只是对算法感兴趣，我可以自己处理实现。

规范是:

假设有 n 个人的房子。

假设 m 家务。

现在，为简单起见，假设 n == m。

假设一个元组的排除列表，即 Bob 不必清理
楼上的浴室，因为他住在不同的地方
房子，有自己的私有(private)浴室。然而他负责
其他家务。

假设一个“每周偏移量”整数变量在
磁盘。如果这个变量不增加，程序吐出
每次输出相同。现在，我只是手动增加这个变量。

在给定的一周内，不应为两个人分配相同的家务。

每个人都应该在重复一项家务之前，只做一次“他们有能力做的每一项家务”。

现在出于调试目的，我正在手动增加这个变量并检查输出是否正常。

到目前为止我的代码:

users = [
"Alice",
"Bob",
"Carl",
"Dani",
"Elmer",
]

chores = [
"Kitchen",
"Dining room",
"Upstairs bathroom",
"Living room", 
"Lawn",
] 

exclusion_list = [
("Bob", "Upstairs bathroom")
] 

weekly_offset = 0

# Generate a list of chores "doable" by each user
# Horrible method I know, but just trying to get something working
# and for trivial n and m it shouldn't matter.

user_list = {}
for i in users:
    temp_list = []
    for j in chores:
        for k in exclusion_list:
            if k[0] == i and k[1] == j:
                print("Excluded")
            else:
                temp_list.append(j)
    user_list[i] = temp_list

# Confirm this list is accurate
print(user_list)

print()

user_offset = 0
for i in user_list:
    print(i, end = ": ")
    chore_index = (weekly_offset + user_offset) % len(user_list[i]) 
    print(user_list[i][chore_index])
    user_offset += 1

第一周，一切都很好。第二周，虽然我看到人们加倍，这对于我的幼稚算法是可以预料的。

然后我试图想出一种算法来满足所有这些规范，现在我什至不确定它是否可能。

这种情况肯定类似于其他计算问题，不是吗？也许是操作系统开发领域的东西，也许是进程调度？

你会建议什么算法或者这个问题类似于什么？

为了好玩，我计划在某个时候实现的其他功能:

m > n(有些家务不会每周都做完，但有一个“必要”的标志来做家务
以确保它永远不会被跳过)

n > m(确保公平分配休息日)

能够修改代码以添加或删除用户并且仍然
继续满足“每个人都应该做”的每一件家务
能够“在重复一项家务之前只做一次”
规范。

Answer 1

The specs are:

• Assume a house of n people.

• Assume m chores.

• For now, for simplicity's sake, assume n == m.

• Assume an exclusion list of tuple, ie, Bob doesn't have to ever clean the upstairs bathroom since he lives in a different part of the house, with his own private bathroom. He is however responsible for the other chores.

• Assume a "weekly offset" integer variable that is incremented on disk. If this variable is not incremented, the program spits out the same output each time. For now, I'm simply incrementing this variable manually.

• No two people should be assigned the same chore for a given week.

• Each person should do "each chore they are capable of doing" exactly once before repeating a chore.

您的规范条件是 不兼容 .上面的最后一个条件需要 一连串的家务其中有一个 长度 的 用户能够做的家务数量 .但它会导致 矛盾 如果我们介绍 exclusion_list ，即第四个条件。

例如，如果我们忽略 exclusion_list ，一种可能的解决方案如下:

# Abbreviations:
# K == "Kitchen", D == "Dining room", U == "Upstairs bathroom"
# Lr == "Living room", L == "Lawn"

Week   1     2     3     4     5

Alice: K  -> D  -> U  -> Lr -> L
Bob:   D  -> U  -> Lr -> L  -> K
Carl:  U  -> Lr -> L  -> K  -> D
Dani:  Lr -> L  -> K  -> D  -> U
Elmer: L  -> K  -> D  -> U  -> Lr 

每个用户都有一个长度为 5 的链。

但是，如果我们应用 exclusion_list , Bob 应该有一个长度为 4 的链。这意味着 Bob 将在 5 周内完成 4 项不同的家务活，如下所示:

Week   1     2     3     4    5

Bob:   D  -> Lr -> L  -> K -> D

5 周后，有 (5 kinds of chores) * (5 weeks) = 25要做的家务。并且，由于其他 4 个用户将在 5 周内做 5 种不同类型的家务(因为他们应该有一个长度为 5 的链)，分配给 4 个用户后剩余的家务数量为 25 - ((5 kinds of chores) * (4 users)) = 25 - 20 = 5 .这 5 件家务活都是不同的种类。 它与 相矛盾Bob 应该有一个长度为 4 的链。

如果我们假设一个非常简单的情况，可以如下表示:

users = [
    "Alice",
    "Bob",
]

chores = [
    "Kitchen",
    "Dining room",
]

exclusion_list = [
    ("Bob", "Kitchen")
]

然后，在重复“厨房”家务之前，爱丽丝不能做爱丽丝能够做的“餐厅”家务，因为鲍勃总是做“餐厅”家务。