从一袋袜子中配上袜子

Question

我当时正在读“Algortihms要靠”一书，受到它的启发，我开始尝试模拟如何从一堆袜子中配对？ (目前还没有有效的部分)。

import random
from operator import add


def get_pair_of_socks(num_of_socks):
    return random.sample(range(num_of_socks), num_of_socks)


def index_to_pull_sock_from(bag_of_socks: list):
    return random.randint(a=0, b=len(bag_of_socks) - 1)


def attempt_counts_matching_socks(num_of_socks_to_consider):
    # Keep attempt counts in this list.
    attempt_counts = []

    # Generate pairs of random socks.
    socks = get_pair_of_socks(num_of_socks_to_consider) + get_pair_of_socks(num_of_socks_to_consider)

    while len(socks) != 0:
        # Pick one pair from the bag..
        first_pair = socks.pop(index_to_pull_sock_from(socks))

        # Pick a second pair..
        random_pick = index_to_pull_sock_from(socks)
        second_pair = socks[random_pick]

        # We did an attempt..
        attempt_count = 1

        # If they matched, perfect. We will never enter this block.
        # Otherwise loop until you do find the match..
        while second_pair != first_pair:
            # Increment the attempt_count whenever you loop..
            attempt_count = attempt_count + 1
            random_pick = index_to_pull_sock_from(socks)
            second_pair = socks[random_pick]

        # Remove the second matching pair from the bag..
        socks.pop(random_pick)

        # Keep the number of attempts it took you to find the second pair..
        attempt_counts.append(attempt_count)

    return attempt_counts


num_of_iterations = 1000
pair_of_socks = 10

# Initalise a list of length `pair_of_socks`
attempt_counts_so_far = [0] * pair_of_socks

for _ in range(num_of_iterations):
    # Get attempt counts for 1 iteration..
    attempt_counts_single_iteration = attempt_counts_matching_socks(pair_of_socks)

    # Add the attempt counts aligned by index. We will be dividing by the total number of iterations later for averages.
    attempt_counts_so_far = list(map(add, attempt_counts_so_far, attempt_counts_single_iteration))

average_takes = list(map(lambda x: x / num_of_iterations, attempt_counts_so_far))
print(average_takes)
# [18.205, 16.967, 14.659, 12.82, 11.686, 9.444, 7.238, 4.854, 2.984, 1.0]

Answer 1

您的get_pair_of_socks似乎正在初始化一堆袜子，因此您的名称错误。

如果我正确理解，你会初始化一堆“左”袜子，然后初始化一堆“右”袜子(袜子没有左右，但标签让你更容易跟踪发生了什么)，然后把一堆“左”袜子放在“右”袜子的顶部。因此，每一半的最后一堆只有一份副本的每个袜子对。这是一个奇怪的情况来模拟。我建议用random.sample(list(range(number_of_socks_to_consider))*2,2*number_of_socks_to_consider)一次初始化这个堆。

我认为您可以在不影响结果的情况下将袜子放在堆的顶部，而不是您目前使用的复杂的pop语句。(随机排列集中的随机元素并不比随机排列集中的第一个元素更随机)。

first_pair似乎是尝试中的第一只袜子，而second_pair则是第二只袜子，这也是错误的命名(也许您混淆了“对”和“伙伴”)。

我不认为你在遵循那个链接中描述的算法:那包括拿袜子，然后把剩下的袜子整理好，当你拿袜子的时候，然后用替换的方法检查剩下的袜子，这又让它花的时间更长。

你不需要一个单独的案例来处理第一个袜子，你试图与你选择的袜子配对。你可以这么做：

    first_pair = socks.pop(index_to_pull_sock_from(socks))
    attempt_count = 0
    while True:
        attempt_count = attempt_count + 1
        random_pick = index_to_pull_sock_from(socks)
        second_pair = socks[random_pick]
        if second_pair == first_pair:
                break

Answer 2

你用数字的lists来表示袜子袋。set将是一个更符合逻辑的容器，用于表示一堆无序的袜子。由于set不能包含相同的项目，您需要另一种方法来识别相同设计的不同袜子。逻辑的方法是使用元组(sock_design, id)。这也使得在桩中每个设计模拟1对以上的工作变得非常容易。

def generate_socks(num_designs, amount=2):
    return {(design, i)  for i in range(amount) for design in range(num_designs)}
socks = generate_socks(10)

{ {(0，0)，(0，1)，(1，0)，(1，1)，(2，0)，(2，1)，(3，0)，(3，1)，(4，0)，(4，1)，(4，1)，(5，0)，(5，1)，(6，0)，(6，1)，(7，0)，(7，1)，(8，0)，(8，1)，(9 )(9，1)}

从堆中随机挑选袜子的算法也略有变化：

def pick_sock(socks):
    return random.choice(tuple(socks))

或者：

def pick_sock(socks):
    return random.sample(socks, 1)[0]

while

while len(socks) != 0:可以简化为while socks:

挑选第一只袜子

变成简单的：

def sort_socks(socks):
    socks = socks.copy()

    while socks:
        first = pick_sock(socks)
        socks.remove(first)
        attempts = 0

socks.copy()是为了防止对原始输入的更改。由于元素是不可变的元组，所以不需要deepcopy。

挑选第二个袜子

同时循环

我将使用一个while True:循环和一个匹配的break，而不是第一个选择，然后使用带比较的while循环。

产量

而不是附加到一个列表，然后返回列表，让一个生成器和yield尝试是一个更干净的选择。

        while True:
            second = pick_sock(socks)
            attempts += 1
            if second[0] == first[0]:
                socks.remove(second)
                # print(f'found {first} and {second} after {attempts} tries: {len(socks)} socks left')
                yield attempts
                break

聚合

我不会将尝试保留在列表中，而是为此使用defaultdict(list)或Counter。这简化了聚合。

num_socks = 10
num_iterations = 1000

all_attempts = Counter()
random.seed(42)
for _ in range(num_iterations):
    for i, attempts in enumerate(sort_socks(generate_socks(num_socks, 2))):
        all_attempts[i] += attempts
average_attempts = {
    i: attempts / num_iterations
    for i, attempts in all_attempts.items()
}

或

all_attempts = defaultdict(list)  

random.seed(42)
for _ in range(num_iterations):
    for i, attempts in enumerate(sort_socks(generate_socks(num_socks, 2))):
        all_attempts[i].append(attempts)
average_attempts = {
    i: sum(attempts) / num_iterations
    for i, attempts in all_attempts.items()
}

{0: 18.701，1: 16.968，2: 15.203，3: 13.133，4: 11.2，5: 9.23，6: 6.945，7: 4.937，8: 2.999，9: 1.0}

这比两个list(map(..))操作更具可读性。

性能

num_sock    10  30
Original    193 1490
counter     157 1440
defaultdict 174 1470

我用10双和30双袜子测试了这一点，性能也差不多。