Statistics

Problem Statement for "ShuffleSort"

Problem Statement

Fox Ciel has a deck of N cards numbered from 0 to N-1, inclusive. For each i, the i-th card has an integer cards[i] written on it. It is possible that the integers written on some cards are the same. Such cards are indistinguishable.

Ciel wants to sort the cards. More exactly, she wants to place them in a line on the table so that the integers on the cards form a non-decreasing sequence. To achieve this goal, she takes the entire deck into her hand and applies the following process (starting from step 1).
  1. She shuffles all cards in her hand. This is equivalent to permuting the order of cards uniformly at random.
  2. Let X be the smallest of all integers written on cards she still holds in her hand. Ciel checks the topmost card of the deck she just shuffled. If the card contains an integer greater than X, she proceeds to step 1. Otherwise, she places the card onto the table. (If there are already some cards on the table, the new card is placed on their right to extend the line of sorted cards.) After she does that, if she has no more cards in her hand, she is done. Otherwise, she repeats step 2 (without shuffling the deck!).
Given the int[] cards, return the expected number of times that step 1 (a shuffle of the deck) will be executed during the sorting process described above.

Definition

Class:
ShuffleSort
Method:
shuffle
Parameters:
int[]
Returns:
double
Method signature:
double shuffle(int[] cards)
(be sure your method is public)

Notes

  • The return value must have a relative or an absolute error of less than 1e-9.
  • Informally, the return value can be seen as the average number of card shuffles required to sort a given deck of cards (where the average is taken over very many rounds of the experiment). For a formal definition, you can check http://en.wikipedia.org/wiki/Expected_value.

Constraints

  • cards will contain between 1 and 50 elements, inclusive.
  • Each element of cards will be between 1 and 50, inclusive.

Examples

  1. {1}

    Returns: 1.0

    There is just 1 card, but Ciel will still shuffle the cards once anyway.

  2. {1,2}

    Returns: 2.0

    After a single shuffle of the cards, their order from top to bottom can be (1, 2) or (2, 1). If it is (1, 2), then both cards will be placed on the table and the process will stop. Otherwise, no cards will be placed on the table and shuffle will have to be repeated. In average, the process will end after 2 card shuffles.

  3. {2,3,1}

    Returns: 4.0

    The elements of cards are not necessarily given in a sorted order.

  4. {15,16,4,8,42,23}

    Returns: 16.0

  5. {1,1,1,1,1,1,1,1}

    Returns: 1.0

    All cards are the same, so just one shuffle is always enough.

  6. {1,1,2,2,3,3}

    Returns: 10.0

  7. {1,2,2,2,2,3}

    Returns: 8.083333333333334

  8. {18,35,1,20,25,29,9,13,15,6,46,32,28,12,42,46,43,28,37,42,5,3,4,43,33,22,17,19,46,48,27,22,39,20,13,18,50,36,45,4,12}

    Returns: 706.6666666666666

  9. {34,24,15,42,12,4,19,48,45,13,8,38,10,24,42,30,29,17,36,41,43,39}

    Returns: 222.5

  10. {41,43,15,49,47,6}

    Returns: 16.0

  11. {30,21,1,7,2,44,49,30,24,35,5,7,41,17,27,32,9,45,40,27,24,38,39,19,33,30,42,34,16,40,9,5,31,28,7,24,37,22,46,25}

    Returns: 637.5000000000001

  12. {21,30,28,24,48,13,37,41,12,37,6,18,6,25,32,3,1,1,42,25,17,31}

    Returns: 203.5

  13. {42,8,38,8,38,4,34}

    Returns: 17.5

  14. {10,10,9,22,39,23,47,7,31,14,19,1,42,13,6,11,10,25,38,49,34,46,42,3,1,42,37,25,21,47,22,49,50,19,35,32,35,4,50,19,39,1,39,28,18}

    Returns: 797.0

  15. {44,49,34,8,22,11,18,14,15,10,17,36,2,1,50,20,7,49,4,25,9,45,10,40,3,46,36,44}

    Returns: 358.5

  16. {24,38,15,4,49,1,9,19,31,47,49,32,40,49,10,8,23,23,39,43,39,30,41,8,9,42,16,39,7,12,3,35,23,6,29,47,13,37,26,34,20,43,45}

    Returns: 810.6666666666666

  17. {32,49,23,2,22,50,8,27,43,40,26,13,1,11,4,20}

    Returns: 121.0

  18. {39,2,40,6,24,3,36,33,36,39,27}

    Returns: 52.0

  19. {8,33,33,20,5,22,40,27,30,19,43,26,6,35,50,42,13}

    Returns: 133.5

  20. {11,19,4,40,24,30,47,38,30,50,38,17,50,44,46,48,17,37,6,39,33,6,35,15,2,17,22,37,14,14,6,36,4,13,9,33,46,14,7,22,9,47,33,32,45}

    Returns: 759.4999999999999

  21. {23,30,12,36,1,24,17,45,10,43,40,4,25,5,11,46,50,37,14,25,23,19,19,38,6,9,42,3,26,28,15,15,25,35,25,23,10,34,21,38,48,19,28,24,21,14}

    Returns: 838.9166666666666

  22. {43,36,3,31,14,28,3,50,28,26,44,25,24,23,12,32,4,33}

    Returns: 140.5

  23. {44,26,32,43,43}

    Returns: 9.5

  24. {37,15,1,38,11,14,25,21,21,36,34,12,11,47,18,36,1,41,45,46,25,20}

    Returns: 195.0

  25. {27,45,9,3,22,17,29,44,2,35,19,15,20,3,1,38,11,27,11,8,21,16,27,28,44}

    Returns: 267.33333333333337

  26. {15,10,33,37,16,38,38,25}

    Returns: 28.0

  27. {28,30,29,24,21,3,13,24,47,38,12,46,26,15,11,3,17,31,27,12,22,12,48,4,21}

    Returns: 251.0

  28. {25,39,14,41,2,13,30,1,14,9,29,16,8,28,1,9,40,4,11,8,25,28,9,14,38,2,1,11,29,44,35,6,41,12,5,36,7,23,1,24}

    Returns: 583.3333333333333

  29. {7,17,27,8,27,8,38,22,20,12,47,23,18,13,18,47,36,42,24,30,30,16,10,33,47,6,4,13,35,35,5,23,8,20,33}

    Returns: 492.83333333333337

  30. {8,34,12,36,18,49,26,39,24,43,5,12,42}

    Returns: 73.5

  31. {10,26,22,21,27,35,6,34,1,49,30,2,44,35,38,35,7,44,27,6,13,49,32,1,14}

    Returns: 259.1666666666667

  32. {6,6,43,13,12,28,25,29,3,44,47,24,41,14,26,23,19,11,18,33,13,46,20,32,41,39,36,41,48,40,41,46,4,15,2,41,45,9,36,10,43}

    Returns: 739.7666666666667

  33. {15,32,4,30,26}

    Returns: 11.0

  34. {43,48,50,7,12,28,18,42}

    Returns: 29.0

  35. {41,14,25,2,28,16,34,14,43,25,2,43,10,21,29,28,35,26,37,49,21,38,48,5,4,22,14,7,14}

    Returns: 325.58333333333337

  36. {22,40,41,15,43,20,14,42,5,19}

    Returns: 46.0

  37. {1,6,26,40,4,23,49,48,35,49,22,15,14,26,46,13,47,29,20,13,20,36,40,45,16,41,46,9,19,21,2,24}

    Returns: 456.5

  38. {1,1,1,1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,7,7,7,7}

    Returns: 296.65476190476187

  39. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 1.0

  40. {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,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}

    Returns: 1226.0

  41. {8, 50, 48, 1, 38, 23, 29, 33, 45, 39, 40, 26, 40, 47, 21, 33, 32, 25, 9, 7, 36, 16, 11, 42, 28, 30, 43, 26, 18, 48, 28, 49, 3, 36, 22, 15, 22, 11, 39, 20, 24, 14, 16, 14, 39, 22, 27, 31, 13, 32 }

    Returns: 1048.6666666666667

  42. {1 }

    Returns: 1.0

  43. {15, 16, 4, 8, 42, 23 }

    Returns: 16.0

  44. {1, 1, 1, 2, 3, 4, 5 }

    Returns: 14.333333333333336

  45. {2, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 3.5928571428571416

  46. {11, 24, 49, 50, 33, 17, 12, 9, 1, 2, 19, 23, 45, 23, 11, 7, 8, 37, 47, 7, 48, 46, 45, 44, 43, 34, 33, 32, 31, 27, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 25, 24, 48, 49, 30, 31, 32, 20, 50, 39 }

    Returns: 1006.0

  47. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2 }

    Returns: 21.666748983944416

  48. {2, 3, 1, 3, 15, 16, 17, 2, 3, 42, 19, 45, 22 }

    Returns: 61.83333333333334

  49. {15, 16, 8, 8, 42, 23 }

    Returns: 13.0

  50. {1, 2, 3, 4, 5, 6, 7, 8, 9, 2, 3, 4, 15, 25, 26, 26, 26, 7, 37, 45, 32, 22, 22, 13, 13, 42, 5, 11, 23, 21, 23, 4, 3, 4 }

    Returns: 408.66666666666663

  51. {15, 16, 4, 8, 42, 15, 16, 4, 8, 42, 15, 16, 4, 8, 42, 15, 16, 4, 8, 42, 15, 16, 4, 8, 42, 15, 16, 4, 8, 42, 15, 16, 4, 8, 42, 15, 16, 4, 8, 42, 1, 2, 3, 4, 5, 6, 7 }

    Returns: 464.4710317460318

  52. {32, 38, 33, 8, 42, 34, 26, 26, 4, 46, 38, 20, 32, 18, 35, 11, 7, 5, 7, 50, 2, 2, 12, 35, 45, 50, 24, 36, 43, 27, 8, 19, 17, 38, 3, 33, 37, 34, 4, 21, 2, 5, 1, 27, 28, 13, 11, 17, 48, 16 }

    Returns: 980.6666666666665

  53. {1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 6, 7, 7, 7, 2, 2, 3 }

    Returns: 110.66666666666669

  54. {3, 2, 1, 1, 1, 4, 4, 4 }

    Returns: 17.166666666666664

  55. {1, 1, 1, 1, 1, 1, 1, 1, 34 }

    Returns: 3.7178571428571416

  56. {1, 1, 1, 1, 1, 1, 1, 1, 22, 33, 22 }

    Returns: 10.653571428571428

  57. {1, 1, 2 }

    Returns: 2.5

  58. {1, 2, 1 }

    Returns: 2.5

  59. {1, 1, 1, 2 }

    Returns: 2.833333333333333

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: