[Problem 125] Bogosort

Back to General discussions forum

Matthew Cole     2016-01-10 06:37:15

Two clarifications for the admin:

  1. Are we attempting to sort the original array in increasing or decreasing order? (ie. is [1,2,3,4,5,6,7] sorted or not?)
  2. For purposes of the value we must return, are we counting each shuffle loop FOR i = 0 ... N-1 as N shuffles or 1 shuffle?

Thanks!

Christopher Matthews     2016-01-10 11:54:42
  1. We are to sort the array in ascending order. Your example is correct.
  2. If you had the for i = 0 to n - 1 in a function called `shuffle', for example, then each call to the function would be one shuffle.

-- Christopher P. Matthews.

Matthew Cole     2016-01-18 22:13:35

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.

Christopher Matthews     2016-01-19 17:25:20

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

Matthew Cole     2016-01-19 20:49:51

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.

Christopher Matthews     2016-01-20 04:47:21

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

Please login and solve 5 problems to be able to post at forum