# Example 880 — The shuffle left one in place as expected `the_shuffle_left_one_in_place_as_expected.eml` - A test rejects a shuffle whenever any item is left in its original position, on the grounds that a random shuffle should move everything, and it checks every position of every run exactly. How often a uniform random shuffle leaves something in place is computed below. ## EML ```eml # Self-authored for the EML case corpus (no external origin). A test rejects a # shuffle whenever any item is left in its original position, on the grounds that # a random shuffle should move everything, and it checks every position of every # run exactly. How often a uniform random shuffle leaves something in place is # computed below. # # The test is careful. It reads the real output of the shuffle, not a mock; it # checks every position against the original; it runs many trials; and the # intent is exactly 'the shuffle is uniformly random'. # # A uniform random permutation leaves each item in place with probability one in # n, so the expected number of items left in place is exactly one for any n, and # about 63 in 100 shuffles leave at least one - the test fails a correct shuffle # most of the time and passes a rotation that is not random at all. 10 => items 10000 => trials 3679 => no_fixed_point_per_myriad 1 => expected_items_left_in_place 10000 - no_fixed_point_per_myriad => at_least_one_left_in_place_per_myriad int(trials * at_least_one_left_in_place_per_myriad / 10000) => correct_shuffles_the_test_rejects 0 => fixed_points_of_a_rotate_by_one trials => rotations_the_test_accepts "items shuffled : " + str(items) ^0 "trials : " + str(trials) ^0 "" ^0 "expected items left in place : " + str(expected_items_left_in_place) + ", for any n" ^0 "shuffles with none in place : " + str(no_fixed_point_per_myriad) + " per ten thousand" ^0 "shuffles with at least one : " + str(at_least_one_left_in_place_per_myriad) + " per ten thousand" ^0 "correct shuffles the test rejects : " + str(correct_shuffles_the_test_rejects) + " of " + str(trials) ^0 "" ^0 "a rotate-by-one, items in place : " + str(fixed_points_of_a_rotate_by_one) ^0 "rotations the test accepts : " + str(rotations_the_test_accepts) + " of " + str(trials) ^0 "" ^0 # ---- what the test verified ---- "the shuffle test" ^0 " reads : the real shuffle output, not a mock" ^0 " checks : every position against the original" ^0 " runs : many trials" ^0 " intent : the shuffle is uniformly random" ^0 " positions unchecked : 0" ^0 " verdict : THE SHUFFLE LEFT AN ITEM IN PLACE" ^0 "" ^0 " checking every position of the real output over many" ^0 " trials is the part done right here, and it is why the" ^0 " count of items left in place is exact" ^0 "" ^0 # ---- how often a random shuffle leaves one in place ---- "fixed points of a uniform permutation" ^0 " chance a given item stays put : one in " + str(items) ^0 " expected items that stay put : " + str(items) + " times one in " + str(items) + ", exactly " + str(expected_items_left_in_place) ^0 " chance none stays put : about one over e, " + str(no_fixed_point_per_myriad) + " per" ^0 " ten thousand, for any n beyond a handful" ^0 " so 'something stayed' : the usual outcome of a correct" ^0 " shuffle, " + str(at_least_one_left_in_place_per_myriad) + " times in ten thousand" ^0 " and 'nothing stayed' : what a rotation guarantees" ^0 "" ^0 # ---- what the caller got ---- "the verdicts" ^0 " correct uniform shuffle : rejected " + str(correct_shuffles_the_test_rejects) + " times in " + str(trials) ^0 " rotate-by-one, not random : accepted " + str(rotations_the_test_accepts) + " times in " + str(trials) ^0 " is the fixed-point count wrong : no; it is exact" ^0 " is 'nothing in place' a mark of randomness : no; it is a" ^0 " mark of a permutation with no fixed points, which a" ^0 " rotation always is and a random shuffle usually is not" ^0 "" ^0 # ---- null control ---- # The same shuffle, tested on the distribution over many trials: the average # number of fixed points should be about 1, and every permutation should appear # about equally often. 6321 => nc_correct_shuffle_rejected_per_myriad_by_the_no_fixed_point_test 0 => nc_correct_shuffle_rejected_per_myriad_by_the_distribution_test 10000 => nc_rotation_rejected_per_myriad_by_the_distribution_test "null control - test the distribution, not one run's fixed points" ^0 " correct shuffle rejected, no-fixed-point test : " + str(nc_correct_shuffle_rejected_per_myriad_by_the_no_fixed_point_test) + " per ten thousand" ^0 " correct shuffle rejected, distribution test : " + str(nc_correct_shuffle_rejected_per_myriad_by_the_distribution_test) ^0 " rotation rejected, distribution test : " + str(nc_rotation_rejected_per_myriad_by_the_distribution_test) + " per ten thousand" ^0 " no shuffle and no trial changed; the property tested" ^0 " stopped being one run's fixed points and started being" ^0 " the shape of many runs" ^0 "" ^0 # ---- the rule ---- "what a no-item-in-place test guarantees" ^0 " the accepted shuffle moved every item : exactly, every" ^0 " position checked against the original" ^0 " the accepted shuffle is random : not addressed; a uniform" ^0 " permutation leaves " + str(expected_items_left_in_place) + " item in place on average and at" ^0 " least one " + str(at_least_one_left_in_place_per_myriad) + " times in ten thousand, so the test rejects" ^0 " the random shuffle and accepts the rotation" ^0 "" ^0 "randomness is a property of the distribution, not of any one outcome; a single" ^0 "result that looks unrandom is what randomness produces most of the time, and a" ^0 "test that forbids it selects for the one thing that is never random" ^0 "" ^0 "It checks every position of the real output over many trials - the fixed-point" ^0 "count is exact. But a uniform shuffle leaves " + str(expected_items_left_in_place) + " item in place on average and at" ^0 "least one " + str(at_least_one_left_in_place_per_myriad) + " times in ten thousand, so the test rejected " + str(correct_shuffles_the_test_rejects) + " correct" ^0 "shuffles and accepted " + str(rotations_the_test_accepts) + " rotations, until it tested the distribution." ^0 ``` ## Python (deterministic transpilation) ```python items = 10 trials = 10000 no_fixed_point_per_myriad = 3679 expected_items_left_in_place = 1 at_least_one_left_in_place_per_myriad = 10000 - no_fixed_point_per_myriad correct_shuffles_the_test_rejects = int(trials * at_least_one_left_in_place_per_myriad / 10000) fixed_points_of_a_rotate_by_one = 0 rotations_the_test_accepts = trials print("items shuffled : " + str(items)) print("trials : " + str(trials)) print("") print("expected items left in place : " + str(expected_items_left_in_place) + ", for any n") print("shuffles with none in place : " + str(no_fixed_point_per_myriad) + " per ten thousand") print("shuffles with at least one : " + str(at_least_one_left_in_place_per_myriad) + " per ten thousand") print("correct shuffles the test rejects : " + str(correct_shuffles_the_test_rejects) + " of " + str(trials)) print("") print("a rotate-by-one, items in place : " + str(fixed_points_of_a_rotate_by_one)) print("rotations the test accepts : " + str(rotations_the_test_accepts) + " of " + str(trials)) print("") print("the shuffle test") print(" reads : the real shuffle output, not a mock") print(" checks : every position against the original") print(" runs : many trials") print(" intent : the shuffle is uniformly random") print(" positions unchecked : 0") print(" verdict : THE SHUFFLE LEFT AN ITEM IN PLACE") print("") print(" checking every position of the real output over many") print(" trials is the part done right here, and it is why the") print(" count of items left in place is exact") print("") print("fixed points of a uniform permutation") print(" chance a given item stays put : one in " + str(items)) print(" expected items that stay put : " + str(items) + " times one in " + str(items) + ", exactly " + str(expected_items_left_in_place)) print(" chance none stays put : about one over e, " + str(no_fixed_point_per_myriad) + " per") print(" ten thousand, for any n beyond a handful") print(" so 'something stayed' : the usual outcome of a correct") print(" shuffle, " + str(at_least_one_left_in_place_per_myriad) + " times in ten thousand") print(" and 'nothing stayed' : what a rotation guarantees") print("") print("the verdicts") print(" correct uniform shuffle : rejected " + str(correct_shuffles_the_test_rejects) + " times in " + str(trials)) print(" rotate-by-one, not random : accepted " + str(rotations_the_test_accepts) + " times in " + str(trials)) print(" is the fixed-point count wrong : no; it is exact") print(" is 'nothing in place' a mark of randomness : no; it is a") print(" mark of a permutation with no fixed points, which a") print(" rotation always is and a random shuffle usually is not") print("") nc_correct_shuffle_rejected_per_myriad_by_the_no_fixed_point_test = 6321 nc_correct_shuffle_rejected_per_myriad_by_the_distribution_test = 0 nc_rotation_rejected_per_myriad_by_the_distribution_test = 10000 print("null control - test the distribution, not one run's fixed points") print(" correct shuffle rejected, no-fixed-point test : " + str(nc_correct_shuffle_rejected_per_myriad_by_the_no_fixed_point_test) + " per ten thousand") print(" correct shuffle rejected, distribution test : " + str(nc_correct_shuffle_rejected_per_myriad_by_the_distribution_test)) print(" rotation rejected, distribution test : " + str(nc_rotation_rejected_per_myriad_by_the_distribution_test) + " per ten thousand") print(" no shuffle and no trial changed; the property tested") print(" stopped being one run's fixed points and started being") print(" the shape of many runs") print("") print("what a no-item-in-place test guarantees") print(" the accepted shuffle moved every item : exactly, every") print(" position checked against the original") print(" the accepted shuffle is random : not addressed; a uniform") print(" permutation leaves " + str(expected_items_left_in_place) + " item in place on average and at") print(" least one " + str(at_least_one_left_in_place_per_myriad) + " times in ten thousand, so the test rejects") print(" the random shuffle and accepts the rotation") print("") print("randomness is a property of the distribution, not of any one outcome; a single") print("result that looks unrandom is what randomness produces most of the time, and a") print("test that forbids it selects for the one thing that is never random") print("") print("It checks every position of the real output over many trials - the fixed-point") print("count is exact. But a uniform shuffle leaves " + str(expected_items_left_in_place) + " item in place on average and at") print("least one " + str(at_least_one_left_in_place_per_myriad) + " times in ten thousand, so the test rejected " + str(correct_shuffles_the_test_rejects) + " correct") print("shuffles and accepted " + str(rotations_the_test_accepts) + " rotations, until it tested the distribution.") ``` ## stdout (executed) ```text items shuffled : 10 trials : 10000 expected items left in place : 1, for any n shuffles with none in place : 3679 per ten thousand shuffles with at least one : 6321 per ten thousand correct shuffles the test rejects : 6321 of 10000 a rotate-by-one, items in place : 0 rotations the test accepts : 10000 of 10000 the shuffle test reads : the real shuffle output, not a mock checks : every position against the original runs : many trials intent : the shuffle is uniformly random positions unchecked : 0 verdict : THE SHUFFLE LEFT AN ITEM IN PLACE checking every position of the real output over many trials is the part done right here, and it is why the count of items left in place is exact fixed points of a uniform permutation chance a given item stays put : one in 10 expected items that stay put : 10 times one in 10, exactly 1 chance none stays put : about one over e, 3679 per ten thousand, for any n beyond a handful so 'something stayed' : the usual outcome of a correct shuffle, 6321 times in ten thousand and 'nothing stayed' : what a rotation guarantees the verdicts correct uniform shuffle : rejected 6321 times in 10000 rotate-by-one, not random : accepted 10000 times in 10000 is the fixed-point count wrong : no; it is exact is 'nothing in place' a mark of randomness : no; it is a mark of a permutation with no fixed points, which a rotation always is and a random shuffle usually is not null control - test the distribution, not one run's fixed points correct shuffle rejected, no-fixed-point test : 6321 per ten thousand correct shuffle rejected, distribution test : 0 rotation rejected, distribution test : 10000 per ten thousand no shuffle and no trial changed; the property tested stopped being one run's fixed points and started being the shape of many runs what a no-item-in-place test guarantees the accepted shuffle moved every item : exactly, every position checked against the original the accepted shuffle is random : not addressed; a uniform permutation leaves 1 item in place on average and at least one 6321 times in ten thousand, so the test rejects the random shuffle and accepts the rotation randomness is a property of the distribution, not of any one outcome; a single result that looks unrandom is what randomness produces most of the time, and a test that forbids it selects for the one thing that is never random It checks every position of the real output over many trials - the fixed-point count is exact. But a uniform shuffle leaves 1 item in place on average and at least one 6321 times in ten thousand, so the test rejected 6321 correct shuffles and accepted 10000 rotations, until it tested the distribution. ``` ## Round-trip `ok: true` — round-trip fixpoint reached (python1 == python2) ## Trace event types eml:run:start · eml:assign · eml:output · eml:run:done