Problem Statement
You've been asked to evaluate the performance of a card shuffler for a casino. Unfortunately, the first thing you notice when examining it is that its shuffling algorithm is not very good. For a deck of length N, it simply chooses x and y uniformly between 0 and N-1, inclusive, and then swaps the cards at those indices. (If x and y are the same, nothing happens.) It repeats this N times.
Prove to the casino that it needs a better algorithm or, at the very least, more swaps. Given a permutation of cards (represented by integers from 1 to N), determine the relative probability of permutation being chosen after N swaps, compared to a properly random shuffle. (In other words, return the probability of permutation being chosen, multiplied by N factorial.)
Definition
- Class:
- PermutationBias
- Method:
- relativeProbability
- Parameters:
- int[]
- Returns:
- double
- Method signature:
- double relativeProbability(int[] permutation)
- (be sure your method is public)
Notes
- The return value must have an absolute or relative error less than 1e-9.
Constraints
- permutation will contain between 1 and 35 elements, inclusive.
- permutation will contain each number from 1 to N exactly once, where N is the number of elements in permutation.
Examples
{2,1}
Returns: 1.0
50% of the "swaps" will be useless. So the probability of 0 real swaps is 25%, 1 is 50%, and 2 (equivalent to 0) is 25%. On a 2-element array, the shuffle is uniformly random.
{2,1,3}
Returns: 1.037037037037037
The shuffle favors this permutation slightly.
{1,2,3,4,5,6,7,8,9,10}
Returns: 60.173086681768936
The chance of nothing happening at all is much higher than it should be!
{16,17,10,4,8,18,12,2,3,9,14,15,13,19,5,11,7,6,20,1}
Returns: 1.7716122730889852
{23,5,17,34,9,10,35,7,25,16,28,2,24,33,14,6,12,1,15,26,31,22,32, 11,21,3,19,29,30,20,18,4,27,13,8}
Returns: 0.02517237926141866
{4,3,27,5,7,19,28,16,13,11,6,24,17,2,18,34,31,23,8,33,26,14,15,29, 30,25,32,1,35,22,20,21,9,12,10}
Returns: 0.0015072964807265855
{28,7,10,21,19,17,8,6,32,14,1,25,15,9,3,5,4,24,12,2,23,26,13,29,34, 30,16,18,35,27,33,20,31,11,22}
Returns: 0.0011004012215620421
{2,3,31,23,10,4,12,27,18,11,28,25,1,13,29,6,16,20,21,22,5,24,34,26,9,7,8, 30,17,32,15,14,35,19,33}
Returns: 0.01010976474120278
{1,15,27,4,5,13,7,10,21,2,11,6,14,8,16,17,18,19,26,9,22,23,24,20,30,28,29, 3,31,32,33,34,35,25,12}
Returns: 43.679325046864506
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29, 30,31,32,33,34,35}
Returns: 1.8863106444391528E14
{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29, 30,31,32,33,34,35,1}
Returns: 1.6101671002276434E-4
{1,2,3}
Returns: 1.1111111111111112
{1,3,2}
Returns: 1.037037037037037
{2,1,3}
Returns: 1.037037037037037
{2,3,1}
Returns: 0.8888888888888888
{3,1,2}
Returns: 0.8888888888888888
{3,2,1}
Returns: 1.037037037037037
{1,2}
Returns: 1.0
{1}
Returns: 1.0
{35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}
Returns: 1854.6475734812861
{1,2,3,4}
Returns: 1.640625
{1,2,3,4,5}
Returns: 2.3239680000000003
{1,2,3,4,5,6}
Returns: 4.118274653254078
{1,2,3,4,5,6,7}
Returns: 6.955399055157569
{1,2,3,4,5,6,7,8}
Returns: 13.999428860843182
{1,2,3,4,5,6,7,8,9}
Returns: 27.051883992194696
{1,2,3,4,5,6,7,8,9,10}
Returns: 60.173086681768936
{1,2,3,4,5,6,7,8,9,10,11}
Returns: 129.5741696016075
{1,2,3,4,5,6,7,8,9,10,11,12}
Returns: 313.1876391337455
{1,2,3,4,5,6,7,8,9,10,11,12,13}
Returns: 738.1097912296559
{1,2,3,4,5,6,7,8,9,10,11,12,13,14}
Returns: 1916.1423472432673
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
Returns: 4878.624104221467
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}
Returns: 13486.131038904507
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}
Returns: 36733.62755078363
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18}
Returns: 107410.6736934319
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}
Returns: 310621.27544278814
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
Returns: 955650.6562537493
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21}
Returns: 2916473.443798698
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22}
Returns: 9399787.897273175
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23}
Returns: 3.0123568879053846E7
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24}
Returns: 1.0133911822659653E8
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25}
Returns: 3.396365119958751E8
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26}
Returns: 1.1889209332002065E9
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27}
Returns: 4.1527787870181866E9
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28}
Returns: 1.5086554650096962E10
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29}
Returns: 5.475752903220791E10
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30}
Returns: 2.059694595714759E11
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31}
Returns: 7.748526332824911E11
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32}
Returns: 3.011641453738608E12
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33}
Returns: 1.1717054816957064E13
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34}
Returns: 4.697278842540529E13
{2,4,3,1}
Returns: 1.0546875
{4,5,3,2,1}
Returns: 1.047527424
{4,1,3,5,6,2}
Returns: 1.0187513759758842
{1,5,3,4,2,6,7}
Returns: 4.483109417831541
{2,3,4,1,6,8,5,7}
Returns: 0.4626274108886719
{6,2,7,4,9,1,8,5,3}
Returns: 1.8231271468300827
{9,6,3,1,8,5,7,10,2,4}
Returns: 1.3169812838547459
{3,8,5,7,10,4,9,2,6,1,11}
Returns: 0.9079395973383954
{11,6,4,8,10,3,1,7,5,9,2,12}
Returns: 0.4822369339118767
{8,3,5,7,1,13,11,10,2,12,6,9,4}
Returns: 0.15668943744064728
{1,6,5,10,11,4,2,13,7,14,3,12,8,9}
Returns: 1.6614456839276426
{2,14,4,3,1,13,12,6,5,7,11,9,10,8,15}
Returns: 1.844080169998924
{13,14,12,15,2,11,9,10,8,1,5,3,6,16,4,7}
Returns: 0.1708341113973335
{1,10,14,15,9,12,6,5,4,16,17,13,8,2,3,11,7}
Returns: 0.2819839724787319
{18,5,12,4,11,13,8,16,14,9,17,10,2,1,6,3,15,7}
Returns: 0.14735378435122207
{6,4,19,2,17,10,12,14,1,13,9,15,7,3,11,5,16,18,8}
Returns: 0.39075244753203053
{3,1,6,8,15,11,20,16,2,19,12,10,14,13,5,4,9,17,18,7}
Returns: 0.2487522158354285
{19,6,15,1,3,11,10,13,18,21,20,5,9,17,2,16,4,8,12,14,7}
Returns: 0.23084005314841083
{1,15,10,18,22,11,12,4,7,19,9,16,6,3,13,2,14,5,17,21,8,20}
Returns: 0.12890321772544866
{10,8,12,6,22,13,1,9,16,17,20,21,5,23,4,14,2,15,7,11,18,19,3}
Returns: 0.03574581814280959
{23,15,24,9,1,8,18,7,12,10,6,5,16,4,20,11,17,13,2,19,14,21,3,22}
Returns: 0.3818164949986705
{15,4,17,21,1,8,16,7,24,5,18,12,13,23,2,10,11,14,22,3,9,20,19,6,25}
Returns: 1.5598813095078756
{4,19,23,24,16,5,10,15,12,2,25,26,21,6,13,17,3,22,11,1,20,14,9,7,8,18}
Returns: 0.005459282829144832
{5,10,8,12,11,19,17,22,24,2,16,1,20,15,3,4,6,13,7,18,27,23,14,9,21,25,26}
Returns: 0.09059881581436549
{9,12,8,2,4,1,26,11,14,23,15,7,3,28,21,13,6,20,5,19,16,22,18,10,17,25,24,27}
Returns: 0.017798107397517384
{23,2,28,3,21,1,20,9,13,27,15,7,19,5,18,4,6,11,29,25,10,17,16,26,22,12,14,8,24}
Returns: 0.059017824561163806
{7,4,5,18,30,17,28,27,10,12,3,25,29,9,14,2,6,16,15,13,26,8,19,23,20,22,24,1,11,21}
Returns: 0.022119711982262275
{26,9,17,12,14,1,15,5,28,18,25,21,6,24,7,30,3,13,16,4,27,2,8,31,19,20,29,11,10,22,23}
Returns: 0.014896304645505093
{10,28,4,15,1,23,13,17,8,6,25,32,29,12,22,18,7,31,24,2,30,21,14,11,5,26,27,9,3,20,19,16}
Returns: 0.12301777811872025
{27,26,19,22,23,2,7,12,17,8,11,18,9,3,6,20,13,33,15,10,29,31,14,16,24,32,25,21,1,30,28,5,4}
Returns: 1.4630505325079508
{17,30,15,23,34,29,4,5,10,11,8,16,21,14,22,12,1,28,2,20,27,18,9,33,3,19,32,13,26,25,31,6,7,24}
Returns: 3.773730485956652
{10,1,2,3,4,5,6,7,8,9,35,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34}
Returns: 4.95564897858444E-4
{11,1,2,3,4,5,6,7,8,9,35,10,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34}
Returns: 1.6101671002276434E-4
{1,2,3,4,5,6,29,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,7,30,31,32,33,34,35}
Returns: 6.458710925502241E13
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,25,15,16,17,18,19,20,21,22,23,24,26,27,28,29,30,31,32,33,34,35}
Returns: 1.2644847906963646E11
{5,1,2,3,4,8,6,7,11,9,10,14,12,13,17,15,16,20,18,19,23,21,22,26,24,25,29,27,28,32,30,31,35,33,34}
Returns: 0.24753022191887797
{11,28,5,1,33,7,16,29,23,6,15,14,19,4,31,2,27,12,21,17,18,13,20,10,22,30,26,34,25,8,24,9,32,35,3}
Returns: 1.6101671002276434E-4
{2,19,24,16,29,21,17,13,3,27,8,23,22,4,30,35,26,33,9,7,25,5,20,18,15,14,31,6,32,10,34,28,12,11,1}
Returns: 4.582707728302403E-4
{5,21,10,30,13,11,6,15,25,12,18,7,2,19,28,29,27,4,9,1,34,31,14,32,20,22,33,17,8,3,23,16,35,26,24}
Returns: 2.323375409461818E-4
{33,21,10,14,13,2,5,18,17,8,25,32,12,7,24,29,20,1,22,6,11,15,4,35,34,30,3,19,23,16,28,26,27,9,31}
Returns: 8.368182993527308E-4
{34,20,19,2,29,4,9,30,21,23,27,11,18,15,16,1,13,28,10,6,3,31,7,26,32,35,5,12,17,14,25,33,22,24,8}
Returns: 0.0010582021142621363
{13,25,19,34,23,33,9,31,15,7,26,35,28,1,20,30,14,27,16,10,3,24,11,6,4,29,17,18,8,12,5,2,22,32,21}
Returns: 0.0030418023406899187
{3,13,2,11,20,16,24,35,31,25,19,28,1,12,33,34,21,32,4,30,22,26,7,6,5,17,23,29,15,10,18,9,14,8,27}
Returns: 0.006325644830506475
{9,18,4,35,25,34,20,5,11,7,31,19,2,10,26,33,12,13,6,32,14,24,3,27,16,29,22,1,15,23,28,21,8,17,30}
Returns: 0.019918639684902456
{26,28,2,18,30,34,10,27,23,11,1,31,9,3,24,22,15,6,33,5,21,16,29,35,8,7,20,32,13,25,12,14,4,19,17}
Returns: 0.20090872199108234
{16,10,25,28,33,18,24,19,29,9,26,20,21,1,4,14,15,32,34,22,31,30,13,7,3,12,35,17,2,11,23,6,5,27,8}
Returns: 0.2750128555342798
{25,34,28,10,13,7,6,15,19,33,9,21,5,18,35,27,2,22,11,31,1,14,30,29,32,23,16,12,24,17,20,3,4,26,8}
Returns: 1.1928853078107058
{20,19,8,32,12,7,26,17,21,14,11,5,35,28,34,16,4,29,31,22,9,1,15,33,27,24,23,10,30,18,2,3,6,25,13}
Returns: 10.88614955451488
{31,5,3,30,2,17,15,22,23,6,12,11,19,35,14,32,10,20,13,18,34,9,8,28,21,27,26,29,4,24,1,33,16,25,7}
Returns: 12.179347860588408
{3,14,34,35,21,31,33,11,7,19,27,15,22,20,12,16,29,25,10,4,1,13,26,18,24,23,8,28,17,6,30,32,9,5,2}
Returns: 166.422180091214
{29,2,27,16,5,21,23,17,25,3,10,1,24,30,15,13,8,28,14,26,6,22,7,4,31,20,11,34,12,19,33,35,9,18,32}
Returns: 596.5513820293892
{1,29,3,35,15,17,26,34,23,5,13,32,20,7,10,8,4,27,25,2,21,31,24,9,19,14,18,28,11,30,22,12,33,16,6}
Returns: 6705.778795399996
{11,35,3,27,14,7,12,23,29,4,1,6,32,8,9,21,15,34,19,26,16,24,5,22,30,20,10,28,17,25,31,13,33,18,2}
Returns: 7689.631822846675
{23,4,3,1,26,9,29,8,27,10,35,12,25,30,15,22,34,14,19,20,32,16,2,33,13,5,6,28,31,18,7,21,17,24,11}
Returns: 115782.17700963936
{33,18,25,4,10,27,24,29,11,5,30,12,20,14,23,35,17,2,19,13,21,15,28,32,9,26,6,22,8,3,31,7,1,34,16}
Returns: 553783.0471002739
{24,13,3,31,15,6,34,27,9,33,18,7,2,17,5,16,23,11,26,20,28,22,30,1,29,19,8,21,25,14,4,32,10,12,35}
Returns: 537320.4757906375
{1,31,15,30,10,6,11,8,9,5,7,13,24,25,3,32,17,18,29,22,21,20,23,12,14,34,27,19,28,4,2,16,35,26,33}
Returns: 1623750.695941384
{22,7,27,32,23,6,2,15,9,17,11,24,13,31,8,16,25,20,19,18,21,33,5,29,10,26,3,28,12,30,14,4,1,34,35}
Returns: 1.7417151990884393E7
{33,5,22,4,16,17,7,18,9,10,11,12,13,14,20,2,6,31,30,15,32,3,34,24,25,26,27,28,35,19,8,21,1,23,29}
Returns: 5.429040727075077E7
{22,2,3,18,17,6,27,8,20,21,14,12,13,11,15,16,5,4,19,9,10,1,23,33,25,26,31,29,28,30,7,32,24,35,34}
Returns: 1.740026469622199E8
{1,31,3,4,5,6,26,33,14,10,35,20,22,15,9,16,17,27,19,12,21,25,23,24,13,7,18,28,29,30,2,32,8,34,11}
Returns: 1.3669836848630023E9
{1,2,3,35,8,6,7,18,9,25,11,12,13,14,33,29,17,5,19,21,20,24,23,22,10,26,27,16,28,30,31,32,15,34,4}
Returns: 6.348807044651022E9
{1,2,3,15,5,6,7,16,32,23,11,25,26,14,4,8,12,18,19,9,21,22,10,24,17,13,27,28,29,30,31,20,33,34,35}
Returns: 2.625006048533598E10
{1,2,3,20,12,22,7,8,9,10,11,5,23,14,15,29,17,18,19,4,27,6,13,24,25,26,21,32,16,30,31,28,33,34,35}
Returns: 4.136915772888249E10
{1,2,33,4,11,6,7,8,9,10,5,12,13,14,15,27,17,18,19,20,26,32,23,24,25,21,16,28,31,30,29,22,3,34,35}
Returns: 1.566533896491084E11
{1,2,6,4,5,3,33,8,9,18,11,12,13,14,15,16,17,10,19,20,35,22,23,24,25,26,27,21,29,30,31,32,7,34,28}
Returns: 9.096330237077617E11
{1,2,3,4,5,6,7,8,9,22,11,12,13,14,19,16,17,18,15,20,21,10,23,24,25,35,27,28,33,30,31,32,29,34,26}
Returns: 1.9923197401470728E12
{1,2,3,4,5,27,7,32,9,10,11,12,13,14,28,16,17,18,19,20,21,22,23,24,25,26,6,15,29,30,31,8,33,34,35}
Returns: 6.678391927229998E12
{1,11,3,4,5,6,7,8,9,10,2,12,13,14,15,16,17,18,19,20,21,22,23,24,25,29,27,28,26,30,31,32,33,34,35}
Returns: 2.100137438107787E13
{1,2,3,4,5,6,7,8,9,33,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,10,34,35}
Returns: 6.458710925502241E13
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35}
Returns: 1.8863106444391528E14
{11,3,1,35,22,15,21,17,14,5,31,6,29,18,16,19,20,12,33,10,13,25,34,7,28,26,27,30,8,4,9,23,32,2,24}
Returns: 0.06968595164721482
{35,1,30,27,13,20,25,16,19,17,18,7,24,15,9,2,6,34,23,21,31,12,33,10,3,29,32,5,11,28,26,4,14,22,8}
Returns: 0.0025055231676494056
{12,34,32,8,2,23,27,14,21,26,1,5,10,18,30,6,20,35,29,3,19,13,31,17,33,22,7,25,28,16,9,4,15,24,11}
Returns: 0.004223159730053735
{4,9,7,29,35,20,25,14,11,3,13,28,1,16,2,5,31,23,32,33,12,15,24,30,27,19,6,34,17,22,8,10,21,26,18}
Returns: 4.6065194938948496E-4
{9,20,4,32,35,6,3,5,29,15,2,33,28,21,31,22,7,27,16,24,19,10,14,26,11,25,30,23,13,8,18,17,1,34,12}
Returns: 0.06205154904249148
{5,24,27,22,2,25,18,23,29,1,35,17,32,10,30,13,26,16,34,19,9,20,7,6,15,28,3,4,8,21,12,11,33,14,31}
Returns: 0.01399664667523971
{35,18,6,29,8,16,4,19,26,33,30,3,7,21,14,17,1,28,23,20,10,13,34,25,31,5,2,27,15,12,22,9,11,24,32}
Returns: 0.005817421808824552
{22,10,32,12,29,8,23,5,15,4,18,25,19,33,13,9,24,21,34,31,17,11,3,27,20,1,35,14,2,26,7,6,30,16,28}
Returns: 2.962555251654164E-4
{10,26,8,33,34,4,23,18,11,30,7,27,2,12,9,31,20,1,28,15,22,21,17,24,16,35,32,5,3,13,19,25,6,29,14}
Returns: 0.035595876564026886
{16,3,30,26,13,28,8,25,29,2,1,10,33,17,31,9,35,11,4,24,12,5,34,14,27,32,15,23,7,19,21,18,22,6,20}
Returns: 0.0024979692961337187
{24,28,5,15,23,32,6,31,18,4,26,13,16,2,7,3,35,12,19,20,14,21,25,33,22,8,34,1,27,11,30,17,10,9,29}
Returns: 0.0900233303822752
{4,12,17,3,19,11,18,23,25,7,8,13,35,31,26,24,28,27,1,32,29,16,33,30,2,15,9,20,34,6,14,5,21,10,22}
Returns: 0.01010976474120278
{14,8,24,30,34,6,19,18,7,27,25,1,17,2,5,12,31,23,28,15,13,10,22,20,4,29,35,32,21,3,26,33,9,16,11}
Returns: 0.009869376140182923
{12,22,6,20,13,17,23,15,34,19,32,16,25,4,29,3,8,11,9,5,30,7,2,28,33,31,35,27,26,10,21,24,1,14,18}
Returns: 5.678220162162746E-4
{21,33,23,16,14,29,2,34,11,1,13,15,32,17,6,31,10,24,5,12,25,8,20,19,3,9,22,7,27,4,26,30,28,18,35}
Returns: 0.011660864754780079