Programming a probability of twins reunion

Question

I have a problem as below, I tried but I couldn't find the right result. I want to solve it in a simple way without using an extra library. I don't have any data to share because I can't establish a correct logic.

4 twins (8 children in total) play with their eyes closed. The children in the randomly distributed group hold each other's hands in pairs when a moment comes. How to write a python script that lists all possibilities and marks the probability that siblings hold each other's hand?

list = ['a1', 'a2', 'b1', 'b2', 'c1', 'c2', 'd1', 'd2']

I want to get a result like this:

[a1a2, b1b2, c1c2, d1d2] - Found
[a1a2, b1b2, c1d1, c2d2] - Not found
[a1a2, b1b2, c1d2, c2d1] - Not found
[a1a2, b1b2, c1d1, c2d2] - Not found
[a1a2, b2b1, c1d1, c2d2] - Not found
...
all possible matches
...

Thanks for help.

Answer 1

Creating all pairings and comparing to correct pairing

First, define a function to generate all pairings, and a function to generate the correct pairing:

def all_pairings(l):
  if len(l) == 0:
    return [[]]
  else:
    return [[(l[0],l[i])] + p for i in range(1,len(l)) for p in all_pairings(l[1:i]+l[i+1:])]

def adjacent_pairing(l):
    it = iter(l)
    return zip(it, it)

Then it's just a for-loop:

children = ['a1', 'a2', 'b1', 'b2', 'c1', 'c2', 'd1', 'd2']

correct_pairing = set(adjacent_pairing(children))

for pairing in all_pairings(children):
    sentence = 'Found' if set(pairing) == correct_pairing else 'Not found'
    print(', '.join(''.join(pair) for pair in pairing), ' -- ', sentence)

Output:

a1a2, b1b2, c1c2, d1d2  --  Found
a1a2, b1b2, c1d1, c2d2  --  Not found
a1a2, b1b2, c1d2, c2d1  --  Not found
a1a2, b1c1, b2c2, d1d2  --  Not found
...
a1d2, a2d1, b1b2, c1c2  --  Not found
a1d2, a2d1, b1c1, b2c2  --  Not found
a1d2, a2d1, b1c2, b2c1  --  Not found

Shuffling the pairings

I suggest using random.shuffle to shuffle the possible pairings before iterating (otherwise, the correct pairing is always the first pairing generated, which is a bit boring).

import random

l = list(all_pairings(children))
random.shuffle(l)
for pairing in l:
    sentence = 'Found' if set(pairing) == correct_pairing else 'Not found'
    print(', '.join(''.join(pair) for pair in pairing), ' -- ', sentence)

Output:

a1a2, b1d2, b2d1, c1c2  --  Not found
a1d1, a2d2, b1c2, b2c1  --  Not found
a1b2, a2c2, b1c1, d1d2  --  Not found
...
a1b1, a2c2, b2d1, c1d2  --  Not found
a1a2, b1b2, c1c2, d1d2  --  Found
a1b2, a2c2, b1d2, c1d1  --  Not found
...
a1c2, a2d2, b1b2, c1d1  --  Not found
a1c2, a2d2, b1c1, b2d1  --  Not found
a1b1, a2b2, c1c2, d1d2  --  Not found

Probability of finding the correct pairing

Assuming all pairings are equiprobable, the probability of finding the correct pairing when picking one pairing randomly is 1 divided by the total number of distinct possible pairings.

How many distinct possible pairings are there?

Choosing an ordered pairing, where the order of the pairs matter, and the order of the two children in each pair matter, is the same as choosing a permutation. It is well known that there are N! possible permutations of N children.

How many ordered pairings correspond to each unordered pairing?

There are 2 possible ways to order the 2 children in each pair; thus there are 2 ** (N / 2) ways to order the 2 children of all pairs.

There are (N / 2)! possible ways to order the N / 2 pairs.

Thus, each pairing corresponds to (N / 2)! * 2 ** (N / 2) ordered pairings.

Thus, there must be N! / ( (N / 2)! * 2 ** (N / 2) ) distinct possible pairings of N children.

For your 8 children, that's 8! / (4! * 2**4) == 105.

The probability of picking the correct pairing, when picking uniformly at random amongst all distinct possible pairings, is 1 over that number:

just slightly under 1% in the case of 8 children.

Expected number of correct pairs in a random pairing

Let's pick a pairing at random among all distinct possible pairings. How many of the pairs in that pairing will be correct, in average?

We can count the number of correct pairs in each pairing in our python program:

for pairing in all_pairings(children):
    nb_correct_pairs = len(set(pairing) & correct_pairing)
    print(', '.join(''.join(pair) for pair in pairing), ' -- ', nb_correct_pairs)

Output:

a1a2, b1b2, c1c2, d1d2  --  4
a1a2, b1b2, c1d1, c2d2  --  2
a1a2, b1b2, c1d2, c2d1  --  2
a1a2, b1c1, b2c2, d1d2  --  2
a1a2, b1c1, b2d1, c2d2  --  1
a1a2, b1c1, b2d2, c2d1  --  1
a1a2, b1c2, b2c1, d1d2  --  2
a1a2, b1c2, b2d1, c1d2  --  1
...
a1d2, a2c1, b1d1, b2c2  --  0
a1d2, a2c2, b1b2, c1d1  --  1
a1d2, a2c2, b1c1, b2d1  --  0
a1d2, a2c2, b1d1, b2c1  --  0
a1d2, a2d1, b1b2, c1c2  --  2
a1d2, a2d1, b1c1, b2c2  --  0
a1d2, a2d1, b1c2, b2c1  --  0

The average number is actually easy to calculate with mathematics.

Let us consider one particular child in a random pairing, for instance child a1. What is the probability that child a1 will hold their twin's hand? Since there are N-1 other children, and by symmetry all children are equally likely, the probability that child a1 will hold their twin's hand is 1/(N-1).

Of course, this applies to all children, not just a1. Thus, in average, 1/(N-1) of the children will hold their own twin's hand. Since there are N children, then in average, N/(N-1) == 1 + 1/(N-1) children will hold their own twin's hand. Since there are 2 children per pair, that means that in average, there will be N / (2(N-1)) == (1 + 1/(N-1)) / 2 correct pairs in a random pairing.

In the case of N == 8, this means 4/7 ≈ 0.571 correct pairs per pairing.

Let us verify experimentally:

l = list(all_pairings(children))
total_correct_pairs = sum(len(set(pairing) & correct_pairing) for pairing in l)
n_pairings = len(l)
expected_correct_pairs = total_correct_pairs / n_pairings
print('Expected number of correct pairs: ', expected_correct_pairs)

Output:

Expected number of correct pairs:  0.5714285714285714