1
\$\begingroup\$

I was reading the book Algortihms to Live By and was inspired by it to take a shot at simulating How to pair socks from a pile? (sans the efficiently part at the moment).

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]
\$\endgroup\$
2
\$\begingroup\$

Your get_pair_of_socks seems to be initializing a pile of socks, so you have the wrong name.

If I understand things correctly, you initialize a pile of "left" socks, then initialize a pile of "right" socks (socks don't have left and right, but the labels make it easier to keep track of what's going on), and then put the pile of "left" socks on top of the "right" pile. So each half of the final pile has only one copy of each sock pair. This is an odd situation to be simulating. I recommend initializing the pile in one go with random.sample(list(range(number_of_socks_to_consider))*2,2*number_of_socks_to_consider).

I think you could just take the sock on the top of the pile without affecting the results, rather than the complicated pop statement you're currently using. (A random element from a random permuted set isn't any more random than the first element from a randomly permuted set).

first_pair seems to be the first sock in the attempted pair, while second_pair is the second sock, which, again, is poor naming (perhaps you are confusing "pair" with "partner").

I don't think you're following the algorithm describes in that link: that involves taking a sock, then taking the rest of the socks in order, while you are taking a sock, then checking the remaining socks with replacement, which again is making it take longer.

You don't need a separate case to handle the first sock you try to pair with the sock you picked. You can just do this:

    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
\$\endgroup\$
  • \$\begingroup\$ Thanks for your inputs but I am pretty confident I understand the algorithm. That is how it goes, pull one sock, if not a match, put it back in the bag. And I am pretty confident with the word pair as well. Thanks though. \$\endgroup\$ – Koray Tugay Sep 20 '18 at 0:41
  • \$\begingroup\$ @KorayTugay I think your algorithm is similar to the one in the book, but it's not the same as the page you link to. As for "pair", what do you think it means? \$\endgroup\$ – Acccumulation Sep 20 '18 at 14:54
  • \$\begingroup\$ Yes, I tried to implement the algorithm as it is explained in the book but I cant see why it is not accurate. Here is pair: english.stackexchange.com/questions/164847/… \$\endgroup\$ – Koray Tugay Sep 20 '18 at 15:03
  • \$\begingroup\$ @KorayTugay I looked the first five results for googling "pair definition", and I did not see that use. And calling something "the pair of" something else is quite different from just referring to it as "a pair". Finally, when naming things in a program, you should find something that clearly means what it is, not something that has one meaning that is what it is. \$\endgroup\$ – Acccumulation Sep 20 '18 at 15:24
  • \$\begingroup\$ Ok, that is really nit picking. Thanks for your time but I will just disagree this time. Lets agree we do not agree. \$\endgroup\$ – Koray Tugay Sep 20 '18 at 16:20
0
\$\begingroup\$

You use lists of numbers to represent the bag of socks. A set would be a more logical container to represent an unordered pile of socks. Since set's can not contain identical items, you'll need another way to discern different socks of the same design. The logical way would be to use tuples (sock_design, id). This would also make it easy to simulate more than 1 pair per design in the pile

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),
 (5, 0), (5, 1), (6, 0), (6, 1), (7, 0), (7, 1), (8, 0), (8, 1), (9, 0), (9, 1)}

The algorithm to pick a random sock from the pile changes slightly too:

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

or:

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

while

while len(socks) != 0: can be simplified to while socks:

Pick the first sock

becomes simply:

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

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

The socks.copy() is to prevent changes to the original input. Since the elements are immutable tuples, there is no need for deepcopy

picking a second sock

while loop

Instead of a first selection, with afterwards a while-loop with the comparison, I would use a while True: loop with a break on a match

yield

Instead of appending to a list, and afterwards returning the list, making a generator and yielding the attempts is a cleaner option

        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

aggregating

Instead of keeping the attempts in a list, I would either use a defaultdict(list) or a Counter for this purpose. This simplifies the aggregation

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()
}

or

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}

This is a lot more readable than the two list(map(..)) operations

performance

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

I tested this with both 10 and 30 pairs of socks, and performance is about the same

\$\endgroup\$
  • \$\begingroup\$ I expect this approach to be a lot faster for large numbers of socks, because removal is... ? \$\endgroup\$ – Koray Tugay Sep 20 '18 at 14:38
  • \$\begingroup\$ Sorry but I do not agree at all that socks should be represented in a Set in the given circumstances. You tell it yourself already: Since set's can not contain identical items but we need identical items here.. \$\endgroup\$ – Koray Tugay Sep 20 '18 at 14:40
  • \$\begingroup\$ If you're so arrogantly sure your solution is best, why ask for code review? Sofe of the approaches I took are valid for both representations as set or list. And to tackle hving the identical socks in the pile, you can construct a tuple (design, id), which is what I did here. Perhaps check the proposal before dismissing it \$\endgroup\$ – Maarten Fabré Sep 21 '18 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.