我有如下問題，我嘗試過，但找不到正確的結果。我想在不使用額外庫的情況下以簡單的方式解決它。我沒有任何資料可以分享，因為我無法建立正確的邏輯。
4 個雙胞胎（共 8 個孩子）閉著眼睛玩耍。隨機分布的組中的孩子在時機到來時成對地握住彼此的手。如何寫一個python腳本，列出所有的可能性并標記兄弟姐妹牽手的概率？
list = ['a1', 'a2', 'b1', 'b2', 'c1', 'c2', 'd1', 'd2']
我想得到這樣的結果：
[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
...
感謝幫助。
uj5u.com熱心網友回復：
創建所有配對并與正確配對進行比較
首先，定義一個生成所有配對的函式，以及一個生成正確配對的函式：
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)
那么它只是一個 for 回圈：
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)
輸出：
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
打亂配對
我建議random.shuffle在迭代之前使用shuffle 可能的配對（否則，正確的配對總是生成的第一個配對，這有點無聊）。
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)
輸出：
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
找到正確配對的概率
假設所有配對都是等概率的，則在隨機選擇一對時找到正確配對的概率為 1 除以不同可能配對的總數。
有多少種不同的可能配對？
選擇一個有序配對，其中配對的順序很重要，每對中兩個孩子的順序很重要，這與選擇排列相同。眾所周知，兒童N!可能存在排列組合N。
每個無序配對對應多少個有序配對？
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).
當然，這適用于所有孩子，而不僅僅是a1. 因此，平均而言，1/(N-1)有的孩子會握住自己雙胞胎的手。既然有N孩子，那么一般來說，N/(N-1) == 1 1/(N-1)孩子們都會牽著自己雙胞胎的手。由于每對有 2 個孩子，這意味著平均而言，N / (2(N-1)) == (1 1/(N-1)) / 2隨機配對中會有正確的配對。
在 的情況下N == 8，這意味著4/7 ≈ 0.571每對配對正確。
讓我們通過實驗驗證：
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)
輸出：
Expected number of correct pairs: 0.5714285714285714
uj5u.com熱心網友回復：
如果包含的庫適合您，您可以嘗試使用 random.choice()。
我還添加了一小部分來估計找到正確雙胞胎的概率。
請嘗試以下操作：
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)
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/391638.html
上一篇：找到加權排名的演算法？
下一篇：使用拆分合并方法就地反轉陣列