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.
CodePudding user response：
combinations will give you every combination of elements in your list. Then combine those into 'games', and look for ones where every pair starts with the same letter:
from itertools import combinations
data = ['a1', 'a2', 'b1', 'b2', 'c1', 'c2', 'd1', 'd2']
# find all pairs in the data
pairs = combinations(data, 2)
# find all sets of pairs
games = combinations(pairs, len(data) / 2)
for game in games:
if all(x[0] == y[0] for x, y in game):
print(f"{game} - Found")
else:
print(f"{game} - Not found")
CodePudding user response：
If an included library is okay for you, you could try to use random.choice().
I also added a small part which estimates the probability of finding the right twin.
Try the following:
import random
twins= ['a1', 'a2', 'b1', 'b2', 'c1', 'c2', 'd1', 'd2']
twinsToFind= ['a1','a2', 'b1', 'b2', 'c1', 'c2', 'd1', 'd2']
# Loop over the list
for i in range(0, 4):
searcher = twins[0]
# remove the searching twin, since he shouldn't find "himself"
twinsToFind.remove(searcher)
# also remove him from the list, since he won't search again
twins.remove(searcher)
# variable for the probability of finding the right twin
prob = 0
# loop over to second list to check how possible it is to find the right twin
for y in twinsToFind:
if searcher[0] == y[0]:
prob = 1
# estimating the probability
prob = prob/len(twinsToFind)
# printing the probability
# casting it to inc gets rid of the digits behind the comma
# multiplying it with 100 gives the probability in percent
print("The probability to find the right twin is: " str(int(prob*100)) "%")
# find a random twin
found = random.choice(twinsToFind)
# print a message if it's the right twin
if searcher[0] == found[0]:
print("==> Right twin found: " searcher found)
# remove the "found" twin from the list, because he won't search again
twins.remove(found)
# remove the found twin from the second list, because he shouldn't be found again
# (yeah, sounds a bit dark, but you get it, I guess)
twinsToFind.remove(found)
print("Found:" searcher "<->" found)
CodePudding user response：
Let me provide the math for the probability: if we have n children in m groups with gi siblings in each group, e.g.
n = 8 = 2 3 1 2 children in total
m = 4 (g1 .. g4)
g1 = 2 (a1, a2) - twins
g2 = 3 (b1, b2, b3) - triplet
g3 = 1 (c1) - the only child
g1 = 2 (d1, d2) - twins
then the probability p will be (we can permutate groups as whole - m! and children within each group - gi!)
p = (m! * g1! * ... * gi! * ... * gm!) / n!
in the example above we have
p = (4! * 2! * 3! * 1! * 2!) / n! =
= (24 * 2 * 6 * 1 * 2) / 40320 =
= 576 / 40320 =
= 1 / 70 ~
~ 0.0143
For 'a1', 'a2', 'b1', 'b2', 'c1', 'c2', 'd1', 'd2' we have
n = 8
m = 4
g1 = g2 = g3 = g4 = 2
p = (4! * 2! * 2! * 2!) / 8! =
= (24 * 2 * 2 * 2) / 40320 =
= 384 / 40320 =
= 1 / 105 ~
~ 0.00952
Code:
def factorial (x):
result = 1
for i in range(2, (x 1)):
result = result * i
return result;
children = ['a1', 'a2', 'b1', 'b2', 'c1', 'c2', 'd1', 'd2']
groups = {};
for child in children:
group = child[:1]
if (group in groups):
groups[group] = 1
else:
groups[group] = 1;
probability = factorial(len(groups))
for key in groups:
probability *= groups[key]
probability /= factorial(len(children))
print (probability)
CodePudding user response：
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