Back to General discussions forum
Two clarifications for the admin:
FOR i = 0 ... N-1
as N shuffles or 1 shuffle?Thanks!
-- Christopher P. Matthews.
Still not getting any arrays to sort here. Did a couple of the other problems and now I'm ready to reattempt this one.
Are these assertions correct?
Assertion #1: With a seed of 918255, the series of random values generated has 598 values, with beginning and ending values '997983', '012278', '413431',...,'086028', '416182', '918255'
.
Assertion #2: With these random values, after the first shuffle, the first sample input array has the following values, beginning with 0 shuffles:
random: 997983, i: 0 j: 0, array: [61, 91, 35, 135, 105, 120, 161], shuffles: 0
random: 12278, i: 1 j: 0, array: [91, 61, 35, 135, 105, 120, 161], shuffles: 0
random: 413431, i: 2 j: 4, array: [91, 61, 105, 135, 35, 120, 161], shuffles: 0
random: 359508, i: 3 j: 2, array: [91, 61, 135, 105, 35, 120, 161], shuffles: 0
random: 759127, i: 4 j: 5, array: [91, 61, 135, 105, 120, 35, 161], shuffles: 0
random: 985306, i: 5 j: 0, array: [35, 61, 135, 105, 120, 91, 161], shuffles: 0
random: 474162, i: 6 j: 3, array: [35, 61, 135, 161, 120, 91, 105], shuffles: 0
random: 38996, i: 0 j: 6, array: [105, 61, 135, 161, 120, 91, 35], shuffles: 1
etc...
Again, all four sample arrays fail to sort within the 598 random values. I don't see how the fourth array even gets to 1391 shuffles.
You're looking in the wrong direction. The solution has nothing to do with the amount of numbers in a generator series; it is perfectly OK to reuse the same values. These are not important. It's more of a permutation thing. Rather than focusing on how many unique numbers your generator produces, think more along the lines of how many unique ways your array can be permuted. That will allow you to set your upper bound of iterations (think N!). I hope that I have not given away too much (or to little!) information; I'd never dream to take the fun out of solving these kinds of problems. Please let me know if you still need help, but I've got a feeling that a smart person like yourself will have no trouble figuring it out :-)
-- Christopher P. Matthews
Got it! Your clue about upper bounds was the hint I needed. I also wrote a clever function to check whether the array was sorted instead of using an equality comparison to Python's built-in sort. I think the side effects of sorted() may have been interfering with my bogosorter. Here's the function:
def is_sorted(iterable, key=lambda x,y: x<=y):
"""
Return if iterable is sorted using a key function (defaults to non-decreasing order).
More efficient in time and memory than using iterable == sorted().
key argument must be a function taking exactly two arguments and returning True or False.
"""
return all(iter(key(iterable[i], iterable[i+1]) for i in range(len(iterable)-1)))
Glad this one is done. It was a bit tricky to tie the generator into the problem, but I'm glad I learned how to make infinite length generator functions.
I used Scheme for my first version of the solution, and I also wrote my own sorted predicate. And I was able to bootleg a generator by making a closure. LISP is awesome :-P
Well I'm glad I was able to help you with this problem, because I see that you've solved quite a few that I have yet to solve. I hope that I may call on you in the near future?
Until then, happy coding!
-- Christopher P. Matthews