29
\$\begingroup\$

Is solving Sudoku too hard? Even the brute force version? Here's a coding exercise that's a little easier. I hope. :-P

Write the shortest function to implement bogosort. In specific, your function should:

  • Take an array (or your language's equivalent) as input
  • Check if its elements are in sorted order; if so, return the array
  • If not, shuffle the elements, and start again

The shortest entry wins. In the case of a tie, a function that supports a custom comparator (and/or pseudorandom number generator) is favoured. Any remaining ties are resolved by favouring the earlier submission.


Clarifications: You can use any element type you want, as long as there's some way to order them, of course. Also, the shuffling has to be uniform; none of this "I'll just quicksort it and call it shuffled" business. :-)

\$\endgroup\$
12
  • \$\begingroup\$ What are the element types? int or strings? \$\endgroup\$
    – Alexandru
    Feb 2, 2011 at 21:39
  • \$\begingroup\$ @Alexandru: Either is fine. You choose. \$\endgroup\$ Feb 2, 2011 at 21:40
  • \$\begingroup\$ Adding a custom comparator will increase the code length so a winning entry will not have a custom comparator. I think breaking the tie doesn't make sense. \$\endgroup\$
    – Alexandru
    Feb 2, 2011 at 21:57
  • 1
    \$\begingroup\$ It's possible that this algorithm can fail when using pseudo random generator. eg when the length of the list exceeds say 2000, there are 2000! states for the list which may exceed the number of interal states of the prng. \$\endgroup\$
    – gnibbler
    Feb 2, 2011 at 22:38
  • 2
    \$\begingroup\$ Yes, the relevant quote from wikipedia "However, if a pseudorandom number generator is used in place of a random source, it may never terminate, since these exhibit long-term cyclic behavior." \$\endgroup\$
    – gnibbler
    Feb 2, 2011 at 23:30

44 Answers 44

17
\$\begingroup\$

Perl 6: 23 chars

@s.=pick(*)until[<=] @s
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Is this a function in perl? It looks nice :) \$\endgroup\$
    – Eelvex
    Feb 3, 2011 at 18:14
  • 1
    \$\begingroup\$ If you don't know, [<=] checks if a list is sorted: [<=] (1, 2, 3,) == (1 <= 2 <= 3) == (1 <= 2) and (2 <= 3), and .pick(n) chooses n random elements from a list, and .pick(*) lets Perl pick all elements. use.perl.org/~masak/journal/40459 \$\endgroup\$
    – Ming-Tang
    Feb 4, 2011 at 1:47
  • \$\begingroup\$ This must be Perl 6. I've never seen pick used before, let alone [<=]. Where in the documentation are those? \$\endgroup\$
    – Mr. Llama
    Oct 15, 2013 at 20:33
  • \$\begingroup\$ @GigaWatt This is Perl 6 (not Perl 5). [] is reduce operator which takes operator between square brackets. For example, [<=] 1, 2, 3 is 1 <= 2 <= 3 (and yes, you do ranges like this in Perl 6). In this case, it's used to determine if elements are in order. .pick(*) method shuffles the list (pick(N) picks N elements from list). .= calls method, and assigns the result to the variable. As for documentation - well, for now only Perl 6 specification exists - feather.perl6.nl/syn, but it exists. \$\endgroup\$ Jan 3, 2014 at 17:54
8
\$\begingroup\$

APL(Dyalog), 20

{⍵≡⍵[⍋⍵]:⍵⋄∇⍵[?⍨⍴⍵]}

Explanation

is the (right) argument
⍵≡⍵[⍋⍵]: Checks if sorted equals itself
:⍵: If yes, then return
∇⍵[?⍨⍴⍵]: Else, generate an array of 1 to ⍴⍵ (length of ) in random order, reorder according to that (⍵[...]), and apply the function to it ()


Suddenly revisiting this problem and...

APL(Dyalog), 19

{∧/2≤/⍵:⍵⋄∇⍵[?⍨⍴⍵]}

Was just thinking about sorting an array in the check makes it kind of pointless (not saying that Bogosort is meaningful), a more accurate implementation would be ∧/2≤/⍵, and that happens to lower the char count.

\$\endgroup\$
7
\$\begingroup\$

APL (22)

{(⍳X←⍴⍵)≡⍋⍵:⍵⋄∇⍵[X?X]}

Usage:

    {(⍳X←⍴⍵)≡⍋⍵:⍵⋄∇⍵[X?X]} 3 2 1
1 2 3

Explanation:

  • ⍋⍵: returns the indexes of the items in sorted order, so ⍋30 10 20 gives 2 1 3
  • (⍳X←⍴⍵)≡⍋⍵:⍵ Store the length of input list in X. If range [1..X] is equal to the sorted index order, the list is sorted, so return it.
  • ⋄∇⍵[X?X]: if this is not the case, recurse with shuffled array.
\$\endgroup\$
7
\$\begingroup\$

Ruby - 33 characters

g=->l{l.shuffle!!=l.sort ?redo:l}
\$\endgroup\$
4
  • \$\begingroup\$ 1 char less: g=proc{|l|0until l.sort==l.shuffle!} \$\endgroup\$
    – AShelly
    Jan 31, 2012 at 21:59
  • \$\begingroup\$ @AShelly, your version doesn't work. My version (5 chars less) f=->l{l.sort!=l.shuffle!?redo:l} (Ruby 1.9) \$\endgroup\$
    – Hauleth
    Mar 11, 2012 at 20:07
  • \$\begingroup\$ can someone please explain to me why redo works with a proc but not in a classical method with def...end? I thought redo only works with loops? \$\endgroup\$ Jul 27, 2012 at 20:19
  • 1
    \$\begingroup\$ Ok never mind, i found something in 'The Ruby Programming Language' book: ”redo […] transfers control back to the beginning of the proc or lambda“. It simply is that way. \$\endgroup\$ Jul 27, 2012 at 20:26
6
\$\begingroup\$

Mathematica, 40 37

NestWhile[RandomSample,#,Sort@#!=#&]&

With whitespace:

NestWhile[RandomSample, #, Sort@# != # &] &
\$\endgroup\$
2
  • \$\begingroup\$ If you ignore errors, you can save three bytes with #//.l_/;Sort@l!=l:>RandomSample@l& \$\endgroup\$ Sep 30, 2015 at 14:41
  • \$\begingroup\$ 13sh bytes in Mthmca. \$\endgroup\$ Jul 20, 2016 at 9:10
5
\$\begingroup\$

J - 34 27

f=:({~?~@#)^:(1-(-:/:~))^:_

eg:

f 5 4 1 3 2
1 2 3 4 5

f 'hello'
ehllo

The {~ ?~@# part shuffles the input:

({~ ?~@#) 1 9 8 4
4 8 9 1
({~ ?~@#) 'abcd'
bdca
\$\endgroup\$
4
\$\begingroup\$

Python 61

Sorts in place.

import random
def f(l):
 while l!=sorted(l):random.shuffle(l)
\$\endgroup\$
7
  • \$\begingroup\$ Your function does not return the array on success. \$\endgroup\$
    – hallvabo
    Feb 3, 2011 at 13:47
  • \$\begingroup\$ Sorts in place. The passed array is modified. \$\endgroup\$
    – Alexandru
    Feb 3, 2011 at 14:38
  • \$\begingroup\$ The question does say that the function is supposed to return the array though - even if it isn't technically necessary to get the result. \$\endgroup\$ Feb 3, 2011 at 18:01
  • 1
    \$\begingroup\$ from random import* can save a char. \$\endgroup\$
    – ugoren
    May 28, 2012 at 10:39
  • 1
    \$\begingroup\$ This may not always work: (from python random module documentation): "Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated." \$\endgroup\$
    – Matt
    Jul 27, 2012 at 17:06
3
\$\begingroup\$

Python 94

from itertools import*
def f(a):return [x for x in permutations(a) if x==tuple(sorted(a))][0]

Other python answers use random.shuffle(). The documentation of the python random module states:

Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated.

\$\endgroup\$
2
  • \$\begingroup\$ Do a lambda instead; I think it would be shorter. Also note that you can do return[x... as opposed to return [x.... Same with permutations(a) if -- it could be permutations(a)if. \$\endgroup\$
    – 0WJYxW9FMN
    Feb 12, 2017 at 21:42
  • \$\begingroup\$ lambda a: [x for x in __import__("itertools").permutations(a) if x==tuple(sorted(a))][0] is 88 bytes \$\endgroup\$
    – Citty
    Nov 6, 2019 at 18:11
3
\$\begingroup\$

K, 31 25

{while[~x~x@<x;x:x@(-#x)?#x];x}

{x@(-#x)?#x}/[{~x~x@<x};]

.

k){x@(-#x)?#x}/[{~x~x@<x};] 3 9 5 6 7 9 1
`s#1 3 5 6 7 9 9

.

k){x@(-#x)?#x}/[{~x~x@<x};] "ascsasd"
`s#"aacdsss"
\$\endgroup\$
2
\$\begingroup\$

Python (69 chars)

from random import*
def f(a):
 while a>sorted(a):shuffle(a)
 return a

Sorts integers in increasing numeric order. Note that recursive solutions, like

from random import*;f=lambda a:a>sorted(a)and(shuffle(a)or f(a))or a

will fail due to stack overflow for even small inputs (say N>5), because Python does not do tail-call optimisation.

\$\endgroup\$
2
\$\begingroup\$

D without custom comparator: 59 Characters

R f(R)(R r){while(!isSorted(r))r.randomShuffle();return r;}

More Legibly:

R f(R)(R r)
{
    while(!r.isSorted)
        r.randomShuffle();

    return r;
}

D with custom comparator: 69 Characters

R f(alias p,R)(R r){while(!isSorted!p(r))r.randomShuffle();return r;}

More Legibly:

R f(alias p, R)(R r)
{
    while(!isSorted!p(r))
        r.randomShuffle();

    return r;
}
\$\endgroup\$
2
\$\begingroup\$

Scala 73:

def s(l:Seq[Int]):Seq[Int]=if(l==l.sorted)l else s(util.Random.shuffle l)

In Scala, we can check whether the compiler did a tail-call optimization:

@annotation.tailrec
def s(l:Seq[Int]):Seq[Int]=if(l==l.sorted)l else s(util.Random shuffle l)

and yes, it did. However, for a short List of 100 values:

val rList = (1 to 100).map(x=>r.nextInt (500))
s(rList) 

took nearly 4 months to complete. ;)

\$\endgroup\$
2
\$\begingroup\$

C# (184 chars)

T[]S<T>(T[]i)where T:IComparable<T>{T l=default(T);while(!i.All(e=>{var r=e.CompareTo(l)>=0;l=e;return r;})){i=i.OrderBy(a=>Guid.NewGuid()).ToArray();l=default(T);}return i.ToArray();}

It's not really nice to do this in C#. You have to support generics to support both value and reference types. There is no array shuffle function or function to check if something is sorted.

Does anybody got any tips to make this better?

Edit Version that only sorts int (134 chars):

int[]S(int[]i){var l=0;while(!i.All(e=>{var r=e>=l;l=e;return r;})){i=i.OrderBy(a=>Guid.NewGuid()).ToArray();l=0;}return i.ToArray();}
\$\endgroup\$
2
\$\begingroup\$

GNU/BASH 65

b(){ IFS=$'\n';echo "$*"|sort -C&&echo "$*"||b $(shuf -e "$@");}
\$\endgroup\$
1
  • \$\begingroup\$ Hmm, can I get a special exception to the return the array rule since bash functions can only literally return an unsigned byte? \$\endgroup\$
    – kojiro
    Oct 16, 2013 at 2:03
2
\$\begingroup\$

C++11, 150 characters

#include<deque>
#include<algorithm>
void B(std::deque &A){while(!std::is_sorted(A.begin(),A.end())std::random_shuffle(myvector.begin(),myvector.end());}

Just.. made for fun.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ std::random_shuffle is not uniform. In the clarifications it is stated: "Also, the shuffling has to be uniform" \$\endgroup\$
    – STDQ
    Jun 4, 2016 at 21:30
  • \$\begingroup\$ Okay... i didn't know it was not uniform. \$\endgroup\$
    – user54200
    Jun 5, 2016 at 2:23
  • \$\begingroup\$ It relies on rand() which is not uniform -- see open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3924.pdf . Not many other people are seem to be following so meh i guess it's not a big deal. \$\endgroup\$
    – STDQ
    Jun 6, 2016 at 0:46
  • \$\begingroup\$ So if I use a fully random one like using srand(time(0)) then does it count? \$\endgroup\$
    – user54200
    Jun 6, 2016 at 0:54
  • \$\begingroup\$ Problem is that rand is not guaranteed to have good quality of random numbers let alone uniformity, some produce non-random low-order bits. I guess it doesn't nor should matter in the end. I only got 8 more bytes using a uniform distributor with std::shuffle and so forth, good enough for me. \$\endgroup\$
    – STDQ
    Jun 8, 2016 at 3:52
2
\$\begingroup\$

C++14, 158 bytes

#include <algorithm>
#include <random>
[](int*a,int s){std::random_device r;for(std::knuth_b g(r());!std::is_sorted(a,a+s);std::shuffle(a,a+s,g));return a;};
\$\endgroup\$
1
  • \$\begingroup\$ you can reduce <algorithm> to <regex>; the latter includes the former automatically, also, you can remove whitespaces in the two #includes \$\endgroup\$ Sep 4 at 8:07
2
\$\begingroup\$

Python - 61 chars

Recursive

from random import*;f=lambda l:l==sorted(l)or shuffle(l)>f(l)
\$\endgroup\$
6
  • \$\begingroup\$ Your function returns True or False, not the array. \$\endgroup\$
    – hallvabo
    Feb 3, 2011 at 13:49
  • 2
    \$\begingroup\$ Also note that recursive solutions are doomed to failure even for small inputs. \$\endgroup\$
    – hallvabo
    Feb 3, 2011 at 14:00
  • 1
    \$\begingroup\$ @hallvabo: I actually want to write a tail-recursive solution in Scheme, which won't deplete your stack, of course. \$\endgroup\$ Feb 3, 2011 at 15:35
  • \$\begingroup\$ @hallvabo, Alexandru had already done the obvious Python solution, so I was just going for something different here. Of course the recursive solution is just for fun and not a serious contender \$\endgroup\$
    – gnibbler
    Feb 3, 2011 at 19:48
  • \$\begingroup\$ from random import* might be shorter. \$\endgroup\$
    – 0WJYxW9FMN
    Feb 12, 2017 at 21:43
2
\$\begingroup\$

PowerShell, 85 82 56 55 52 bytes

-26 bytes thanks to mazzy's suggestions
-1 byte thanks to AdmBorkBork
-3 bytes thanks to mazzy

for($l=$args;"$l"-ne($l|sort)){$l=$l|sort{random}}$l

Try it online!

PowerShell does have a relatively cheap array comparison by casting them to strings and comparing that.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Move your param initialization into your for initialization to save a byte -- for($l=$args; \$\endgroup\$ Nov 8, 2019 at 15:04
  • 1
    \$\begingroup\$ nice. -ne casts the right operator to a scalar type of the left operator. so, you can save a few bytes: Try it online! \$\endgroup\$
    – mazzy
    Nov 8, 2019 at 17:07
1
\$\begingroup\$

Javascript 291 characters

min

function f(e){var t=[].concat(e).sort();t.e=function(e){var n=true;t.forEach(function(t,r){if(t!=e[r])n=false});return n};while(!t.e(e.sort(function(){return Math.floor(Math.random()*2)?1:-1}))){console.log(e)}return e}

un-min

function f(a) {
var b = [].concat(a).sort();
b.e = function (z) {
    var l = true;
    b.forEach(function (v, i) {
        if (v != z[i]) l = false;
    });
    return l
};
while (!b.e(a.sort(function () {
    return Math.floor(Math.random() * 2) ? 1 : -1;
}))) {
    console.log(a);
}
return a;
}
\$\endgroup\$
1
  • \$\begingroup\$ I have a feeling I've said this before, but you can remove all the vars. Just make them all implicit globals, it's just about making the code as short as possible. \$\endgroup\$
    – gcampbell
    Jun 3, 2016 at 18:24
1
\$\begingroup\$

Matlab, 59 bytes

Relatively straight forward approach:

x=input('');while~issorted(x);x=x(randperm(numel(x)));end;x
\$\endgroup\$
1
\$\begingroup\$

J, 22 bytes

$:@({~?~@#)`]@.(-:/:~)

This is a recursive, tacit monad using an agenda. Here's how it works:

Let y be our list. First, the verb on the right of the agenda is -:/:~. This a verb graciously provided by Leaky Nun. It matches (-:) whether or not the input is sorted (/:~) using a monadic hook. ((f g) y = y f (g y)) This returns a one or a zero accordingly. The left hand side of the agenda is a gerund of two verbs: on the right is the identity verb ], and on the left is where the recursion takes place. The agenda selects either the identity verb at position 1 if the list is sorted, and the longer verb at position 0 if the list isn't sorted.

$:@({~?~@#) calls $: (the longest verb it is contained in) atop the result of {~?~@# on y. This shuffles the list, as ?~@# takes the permutations of the length of y, being randomly-sorted indices of y. {~, in a monadic hook, returns a list from y whose indices are the right arg. This shuffled list is then called again with the agenda, and repeats until it is sorted.

\$\endgroup\$
1
\$\begingroup\$

Jelly, 6 bytes, language postdates challenge

ẊŒ¿’$¿

Try it online!

Explanation

ẊŒ¿’$¿
     ¿  While
 Œ¿’$     the input is not in its earliest possible permutation (i.e. sorted)
Ẋ       shuffle it

Œ¿ assigns a number to each permutation of a list; 1 is sorted, 2 has the last two elements exchanged, etc., up to the factorial of the list length (which is the list in reverse order). So for a sorted list, this has the value 1, and we can decrement it using in order to produce a "not sorted" test that's usable as a Boolean in a while loop condition. The $ is to cause the condition to parse as a group.

\$\endgroup\$
1
\$\begingroup\$

C++, 166 bytes

Meh.

#import<algorithm>
#import<random>
#define r b.begin(),b.end()
template<class v>
v f(v b){auto a=std::mt19937();while(!std::is_sorted(r))std::shuffle(r,a);return b;}

This should work on all STL containers that have begin() and end().

Ungolfed:

#include <algorithm>
#include <random>
template <class v>
v f(v b) {
    auto a = std::mt19937();
    while (!std::is_sorted(b.begin(),b.end()))
        std::shuffle(b.begin(),b.end(),a);

    return b;
}
\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Extended), 15 bytes

(?⍨∘≢⊇⊢)⍣{⍺≡∧⍺}

Try it online!

\$\endgroup\$
1
1
\$\begingroup\$

Brachylog, 5 bytes

∈&ṣ≤₁

Try it online!

When I first saw ais523's Brachylog answer (as opposed to his Jelly answer, because if I'm not mistaken user62131 was also him), I wondered, what if it used backtracking instead of recursion? So at first, I tried ṣ≤₁. Turns out, since choosing something at random doesn't produce multiple outputs so much as it just produces one output nondeterministically, the shuffle predicate can't be backtracked to, so running that will simply fail unless you're lucky enough to shuffle it right on the first try. After that, I tried pṣ≤₁, which worked most of the time, but since a finitely long list has finitely many permutations, it still failed at random sometimes. After having abandoned the goal of achieving length reduction, I finally came up with this:

         The input
∈        is an element of
         an unused implicit variable,
 &       and the input
  ṣ      shuffled randomly
   ≤₁    which is increasing
         is the output.

(Demonstration of randomness)

Although it actually can be a bit shorter if we take some liberties with I/O...

Brachylog, 4 bytes

⊆ṣ≤₁

Try it online!

In order for the output to be useful, the input must not contain any duplicate elements, because in addition to sorting the input, this bogosort predicate adds in a random number of duplicate elements and zeroes. (Hypothetically, it could add in anything, but it just kind of doesn't.) Ordinarily I wouldn't bother mentioning something so far from correctly functioning, but I feel it's in the spirit of the challenge.

⊆        An ordered superset of the input
 ṣ       shuffled randomly
  ≤₁     which is increasing
         is the output.
\$\endgroup\$
1
\$\begingroup\$

Perl 6, 28 bytes

{({.pick(*)}...~.sort).tail}

Try it online!

Anonymous code block that shuffles the list until it is sorted. Note that it sorts the list at least once, which is allowed. And no, the {.pick(*)} can't be replaced with *.pick(*)

\$\endgroup\$
1
\$\begingroup\$

Pyth, 11 bytes

Wn=Q.SQSQ;Q

Pretty happy with this, probably can be golfed a bit more

Explanation


Wn=Q.SQSQ;Q
W    While
  =Q.SQ    Variable Q (input variable) shuffled 
 n  Does not equal
       SQ    Variable Q sorted
             ;  Do nothing (loop ends)
              Q    And output variable Q

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ You can shorten =Q.SQ to =.SQ for -1 byte (works with other operators too, like =QhQ-> =hQ) \$\endgroup\$
    – ar4093
    Dec 3, 2019 at 8:39
1
\$\begingroup\$

Japt, 11 9 bytes

_eZñ}a@öx

Try it

_eZñ}a@öx     :Implicit input of array U
_             :Function taking an array as argument via parameter Z
 e            :  Test Z for equality with
  Zñ          :  Z sorted
    }         :End function
     a        :Repeat and return the first result that returns true
      @       :Run this function each time and pass the result to the first function
       öx     :  Random permutation of U
\$\endgroup\$
1
\$\begingroup\$

Brachylog (v2), 5 bytes

≤₁|ṣ↰

Try it online!

Function submission. (The TIO link uses a command-line argument that automatically wraps a function into a full program.)

Explanation

≤₁|ṣ↰
≤₁      Assert that {the input} is (nonstrictly) sorted in ascending order
  |     Output it
  |     Exception handler: if an assertion fails:
   ṣ      Randomly shuffle {the input}
    ↰     and run this function recursively on it, {outputting its output}

Prolog (the language that Brachylog compiles into) is tail-recursive, so this function ends up being compiled into a tight loop.

\$\endgroup\$
1
\$\begingroup\$

Java, 252

Requires java 10 as the varkeyword is used.

import java.util.*;interface B{static int c(List<String>a,int i){return i>0?Math.max(a.get(i-1).compareTo(a.get(i)),c(a,i-1)):-1;}
static void main(String[]p){var a=Arrays.asList(p);while(c(a,a.size()-1)>0)Collections.shuffle(a);System.out.print(a);}}

Explained

import java.util.*;                              // you don't get a lot for free in java
interface B{
  static int c(List<String>a,int i){             // recursive comparator method, i is index to compare a[i-1] with a[i]
    return i>0?                                  // still not at the first element?
           Math.max(                             // return the max of...
             a.get(i-1).compareTo(a.get(i)),     // - string comparison of a[i-1] and a[i]
             c(a,i-1))                           // - recursive call c for i-1
           :-1;                                  // i=0 -> return -1
  }
  static void main(String[]p){                   // entry point
    var a=Arrays.asList(p);                      // convert the input array in a List (so we can use Collections functions)
    while(c(a,a.size()-1)>0)                     // as long as c()>0, at least one element is not in correct order
      Collections.shuffle(a);                    // shuffle the list
    System.out.print(a);                         // print the ordered list
  }
}

Try it online

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.