Statistics

Problem Statement for "RandomSwaps"

Problem Statement

Suppose that we have an array with arrayLength distinct elements. A quite common task in programming is to randomly permute this array. Novices who encounter this situation often implement the following algorithm:

  • Choose a positive integer swapCount.
  • swapCount times randomly choose two distinct indices and swap the corresponding elements.

This method of permuting an array is bad, because some permutations of the array will be more likely than others. In this problem, you shall compute how bad this method is for a given situation.

You will be given four ints: arrayLength, swapCount, a and b. Consider the element of the array that initially had the index a. Write a method that will compute the probability that this element will have the index b at the end of the process described above.

Definition

Class:
RandomSwaps
Method:
getProbability
Parameters:
int, int, int, int
Returns:
double
Method signature:
double getProbability(int arrayLength, int swapCount, int a, int b)
(be sure your method is public)

Notes

  • The indices of elements that are going to be swapped are generated with a uniform probability distribution, i.e., each pair of indices has got the same probability of being chosen.
  • The indices are zero-based, i.e., the array contains elements with indices 0 to arrayLength-1, inclusive.
  • The returned value must have an absolute or relative error less than 1e-9.

Constraints

  • arrayLength will be between 2 and 1,000, inclusive.
  • swapCount will be between 1 and 100,000, inclusive.
  • a and b will be between 0 and arrayLength-1, inclusive.

Examples

  1. 5

    1

    0

    0

    Returns: 0.6

    There are ten possible pairs of indices to swap: (0,1), (0,2), (0,3), (0,4), (1,2), (1,3), (1,4), (2,3), (2,4), and (3,4). Out of these ten, the last six leave the element 0 untouched. Thus the probability is 6/10.

  2. 5

    1

    0

    3

    Returns: 0.1

    Only the swap (0,3) will move the element from position 0 to position 3. The probability of choosing this swap is 1/10.

  3. 5

    2

    0

    0

    Returns: 0.4

    Now there are two possibilities: Either the 0-th element stays in its place for the whole time, or it is swapped away and back again. The probability of the first possibility is (6/10)^2, for the second possibility it is (4/10)*(1/10).

  4. 100

    500

    3

    3

    Returns: 0.010036635745123007

    For 100 elements, even after 500 swaps, the permutation won't be random enough.

  5. 2

    1

    0

    0

    Returns: 0.0

  6. 2

    1

    0

    1

    Returns: 1.0

  7. 2

    1

    1

    0

    Returns: 1.0

  8. 2

    1

    1

    1

    Returns: 0.0

  9. 1000

    100000

    1

    3

    Returns: 0.0010

  10. 1000

    10000

    47

    997

    Returns: 9.999999980198375E-4

  11. 996

    8976

    23

    23

    Returns: 0.001004030387635356

  12. 979

    9432

    11

    11

    Returns: 0.0010214545726463526

  13. 1000

    10000

    134

    134

    Returns: 0.0010000019781824516

  14. 2

    100000

    0

    0

    Returns: 1.0

  15. 2

    100000

    0

    1

    Returns: 0.0

  16. 2

    98765

    0

    1

    Returns: 1.0

  17. 3

    333

    2

    2

    Returns: 0.3333333333333333

  18. 3

    1

    1

    2

    Returns: 0.3333333333333333

  19. 3

    1

    2

    2

    Returns: 0.3333333333333333

  20. 3

    2

    1

    2

    Returns: 0.3333333333333333

  21. 3

    2

    2

    2

    Returns: 0.3333333333333333

  22. 3

    3

    1

    2

    Returns: 0.3333333333333333

  23. 3

    3

    2

    2

    Returns: 0.3333333333333333

  24. 3

    4

    0

    1

    Returns: 0.3333333333333333

  25. 3

    4

    1

    1

    Returns: 0.3333333333333333

  26. 3

    5

    0

    2

    Returns: 0.3333333333333333

  27. 3

    5

    0

    0

    Returns: 0.3333333333333333

  28. 1000

    47

    47

    47

    Returns: 0.9102011623170692

  29. 1000

    213

    24

    254

    Returns: 3.474410834317587E-4

  30. 1000

    999

    999

    999

    Returns: 0.13592918707313337

  31. 1000

    4700

    0

    999

    Returns: 9.999188199335141E-4

  32. 976

    7547

    362

    557

    Returns: 0.0010245899732474594

  33. 764

    5366

    424

    424

    Returns: 0.0013096640581993224

  34. 13

    98765

    1

    1

    Returns: 0.07692307692307693

  35. 987

    7654

    23

    534

    Returns: 0.0010131710455277341

  36. 746

    3522

    533

    234

    Returns: 0.001340378947277188

  37. 436

    3256

    333

    424

    Returns: 0.002293577283284885

  38. 1000

    1

    34

    34

    Returns: 0.998

  39. 1000

    1

    44

    676

    Returns: 2.002002002002002E-6

  40. 1000

    9

    21

    45

    Returns: 1.7874401585442643E-5

  41. 976

    32

    23

    656

    Returns: 6.515999944043824E-5

  42. 997

    9800

    46

    355

    Returns: 0.0010030090242864138

  43. 986

    9765

    53

    53

    Returns: 0.0010142011810771873

  44. 943

    9965

    535

    542

    Returns: 0.0010604453863906687

  45. 857

    47433

    465

    532

    Returns: 0.0011668611435239206

  46. 1000

    100000

    1

    2

    Returns: 0.0010

  47. 1000

    100000

    0

    0

    Returns: 0.0010

  48. 1000

    100000

    3

    4

    Returns: 0.0010

  49. 1000

    100000

    12

    13

    Returns: 0.0010

  50. 1000

    100000

    2

    3

    Returns: 0.0010

  51. 1000

    100000

    3

    9

    Returns: 0.0010

  52. 1000

    100000

    0

    997

    Returns: 0.0010

  53. 1000

    100000

    0

    1

    Returns: 0.0010

  54. 2

    100000

    0

    1

    Returns: 0.0

  55. 1000

    100000

    2

    2

    Returns: 0.0010

  56. 1000

    100000

    500

    500

    Returns: 0.0010

  57. 100

    100000

    1

    2

    Returns: 0.01

  58. 1000

    65535

    23

    45

    Returns: 0.0010

  59. 1000

    100000

    100

    100

    Returns: 0.0010

  60. 1000

    100000

    200

    500

    Returns: 0.0010

  61. 999

    99999

    42

    666

    Returns: 0.001001001001001001

  62. 999

    99999

    9

    99

    Returns: 0.001001001001001001

  63. 2

    1

    0

    1

    Returns: 1.0

  64. 1000

    2000

    1

    5

    Returns: 9.818306173489915E-4

  65. 1000

    100000

    5

    6

    Returns: 0.0010

  66. 1000

    100000

    1

    998

    Returns: 0.0010

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: