|
Since 2015.2.11 |
Please look at the calculation formula below.
How, for 24 people, 6 pairs, there are 4.5 trillion combinations.
To extract the combination of people who have not traveled together in the past from this, a little ingenuity is necessary.
* 8 people: 2 pairs of (4, 4)
Supplementary explanation
(4×3×2) : Omit the number of redundancies in one pair.
That is, (01)a,b,c,d (02)a,b,d,c (03)a,c,b,d (04)a,c,d,b (05)a,d,b,c (06)a,d,c,b
(07)b,a,c,d (08)b,a,d,c (09)b,c,a,d (10)b,c,d,a (11)b,d,a,b (12)b,d,b,a
(13)c,a,b,d (14)c,a,d,b (15)c,b,a,d (16)c,b,d,a (17)c,d,a,b (18)c,d,b,a
(19)d,a,b,c (20)d,a,c,b (21)d,b,a,c (22)d,b,c,a (23)d,c,a,b (24)d,c,b,a
will be the same combination.
The last "2" are redundant numbers of 2 pairs of 4, 4 people.
* 12 people: 3 pairs of (4, 4, 4)
Supplementary explanation
The last "(3x2)" is three pairs of redundancy, four, four and four.
* 16 people: 4 pairs of (4, 4, 4, 4)
Supplementary explanation
The last "(4x3x2)" is the redundancy number of 4 pairs of 4, 4, 4 and 4 people.
* 20 people: 5 pairs of (4, 4, 4, 4, 4)
Supplementary explanation
The last "(5 x 4 x 3 x 2)" is a redundant number of 5 pairs of 4, 4, 4, 4 and 4 people.
* 24 people: 6 pairs of (4, 4, 4, 4, 4, 4)
Supplementary explanation
The last "(6 x 5 x 4 x 3 x 2)" is 6 pairs of redundancy, 4, 4, 4, 4, 4, and 4 people.
Devices for solution I think as follows
* Three pairs of 12 people: (4, 4, 4)
11C3 x 35 = 165 x 35 = 5,775
Fix the first one, select 3 from the remaining 11 people, multiply 35 combinations of 4 and 4 people.
* 16 persons: 4 cases of (4, 4, 4, 4)
15C3 x 11C3 x 35 = 455 x 165 x 35 = 2,627,625
Fix the first one, choose 3 from the remaining 15 people, multiply by the amount chosen by "12 people".
* 20 people: 5 groups of (4, 4, 4, 4, 4)
19C3 x 15C3 x 11C3 x 35 = 969 x 455 x 165 x 35 = 2,546,168,625 (About 2.5 billion combinations)
Fix the first one, choose 3 from the remaining 19 people, multiply by the number you chose in "16 people".
* 24 people: 6 groups of (4, 4, 4, 4, 4, 4)
23C3 x 19C3 x 15C3 x 11C3 x 35 = 1,771 x969 x 455 x 165 x 35 = 4,509,264,634,875 (About 4.5 trillion combinations)
Fix the first one, choose 3 from the remaining 23 people, multiply by the amount chosen by "20 people".
Improvement history 2015.12.27
We completed function for 9 to 16 people at 2015.11.15, but the processing speed at that time was as shown in the table below.
(Even so, I made improvements)
| time | First time (no history) |
Second time (history 1) |
Third time (history 2) |
4th time (history 3) |
5th time (history 4) |
6th time (history 5) |
| Before improvement | 1 second | 12 second | 107 second | 112 second | 117 second | 120 second |
| After improvement | 1 second | 1 second | 12 second | 6 second | 1 second | 1 second |
Next, we started to create functions for 20 people.
When processing for 20 people with the above algorithm, it took 48 hours to process.
t took about 7 seconds to extract and compare 100,000 combinations.
( 2.5 billion / 100 thousand ) x 7 second = 25,000 x 7 second = 175,000 second = About 48 hours
Still, we can handle 100,000 streets in 7 seconds, so I think the computer is amazing.
However, as this is not very useful, we added a basic concept of the algorithm.
Additional algorithm
In the past combination, we will carry out processing to eliminate the match pattern to the utmost.
(1) Extraction of people with fewest opponents
(2) I omit the person who is fighting against that person
(3) Select 1st group (4 people) and check whether these 4 people are fighting against each other
(4) If a temporary first group can be formed, the remaining person is extracted
Hereinafter, the above (1) to (4) are repeated.
Improvement result
20 people : ( 4, 4, 4, 4, 4 ) 5 paiers = 2,546,168,625 (About 2.5 billion combinations)
24 people ; ( 4, 4, 4, 4, 4, 4 ) 6 paiers = 4,509,264,634,875 (About 4.5 trillion combinations)
There are enormous combination patterns,
Even when processing is slow, processing can be done in about 8 seconds. [Go to Pattern 8]
Combination with 16 people, 5 times, you can combine with people not going together.
However, if you do not combine it properly, you may not be able to combine from the fourth time.
16 people took 5 times, not combination same combination
In case of 16 persons a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p
| First time | Second time | Third time | Fourth time | Fifth time |
|
a,c,d,e b,g,h,j f,k,l,m i,n,o,p |
a,b,f,i c,g,m,p d,h,k,n e,j,l,o |
a,g,k,o b,c,l,n d,f,j,p e,h,i,m |
a,h,l,p b,d,m,o c,i,j,k e,f,g,n |
a,j,m,n b,e,k,p c,f,h,o d,g,i,l |
Combination (matchup) list
| a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | |
| a | * | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| b | 1 | * | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| c | 1 | 1 | * | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| d | 1 | 1 | 1 | * | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| e | 1 | 1 | 1 | 1 | * | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| f | 1 | 1 | 1 | 1 | 1 | * | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| g | 1 | 1 | 1 | 1 | 1 | 1 | * | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| h | 1 | 1 | 1 | 1 | 1 | 1 | 1 | * | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| i | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | * | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| j | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | * | 1 | 1 | 1 | 1 | 1 | 1 |
| k | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | * | 1 | 1 | 1 | 1 | 1 |
| l | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | * | 1 | 1 | 1 | 1 |
| m | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | * | 1 | 1 | 1 |
| n | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | * | 1 | 1 |
| o | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | * | 1 |
| p | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | * |
The match list is beautifully arranged with "1".
In the fourth round of 16 people, examples which can not be combined
In case of 16 persons a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p
| First time | Second time | Third time | Fourth time | Fifth time |
|
a ,b ,c ,d e ,f ,g ,h i ,j ,k ,l m ,n ,o ,p |
a ,e ,i ,m b ,n ,k ,f c ,g ,j ,o d ,h ,l ,p |
a ,f ,j ,p b ,i ,o ,h c ,e ,l ,n d ,g ,k ,m |
|
Combination (fight) list Three match lists. In the fourth round, we can not combine.
|
Reference
Combination (fight) list Three match lists. When the fourth combination can be made
|
It seems the same as I saw,
If you do not think well of the second and third combinations, the fourth time,
in the past 3 times, someone who came with someone will come out. [To the top of this page]
Combination of golf is strange