Thursday Code Puzzler: String Permutations

 Groovy code

def s = "abc"
println s.toList().permutations().collect({ it.join('') }).sort()

 You can sort the string first to make a better performace:

scala> "rock".sorted.permutations.foreach(println)
ckor
ckro
cokr
cork
crko
crok
kcor
kcro
kocr
korc
krco
kroc
ockr
ocrk
okcr
okrc
orck
orkc
rcko
rcok
rkco
rkoc
rock
rokc

Java - O(n!)

public static void permute(char[] start, char[] end) {
	if(end.length <= 1) out.println(valueOf(start)+valueOf(end));
	else for (int i = 0; i < end.length; i++) {
	      char[] newEnd = Chars.concat(copyOf(end, i), copyOfRange(end, i+1, end.length)); 
	      char[] newStart = copyOf(start,start.length+1);
	      newStart[newStart.length-1] = end[i];
	      permute(newStart, newEnd);
      }
}
static void permute(String string) {
	char[] chars = string.toCharArray();
	sort(chars); // O(n*log(n))
	permute(new char[0], chars); // O(n!)
}

Unlike other languages, JavaScript doesn't have a collections library built into the language but there are numerous collection libraries available from 3rd party developers and of these I tend to use JS.Class because it is well supported by its author and I can easily pick and chose only the components from the library that my application will actually use.

For solving this challenge I am using the JS.SortedSet object from the JS.Class library and what follows is the code solution in its entirety:

var perm = function(window, undefined) {
  "use strict";
  var s = 'abccba',
    i,
    ii, len, temps = '',
    list = [],
    result;
  /*
   * Make one pass of the string for each one of its characters, bypassing the current character.
   */
 for(i = 0, len = s.length; i < len; i += 1) {
    for(ii = 0; ii < len; ii += 1) {
      if(s[ii] !== s[i]) {
        temps = s[i] + s[ii];
        list.push(temps);
        console.log(temps);
        temps = '';
      }
    }
  }console.log(list);
  result = new JS.SortedSet(list);
  result.forEach(function(x) {
    console.log(x);
  });
};
Running the above (the console.log statements print its parameter to the browser's console) the following output is returned:

ab
ac
ba
bc
ca
cb

As displayed above, all duplicates have been removed from the result which is, after all, what one would expect from a set of values. Also, since I used the JS.SortedSet object its collection is maintained in proper sorted order.

You can cut and paste the above code into a web page's script tag and run it but you will first need to download the JS.Class library which can be found at  http://jsclass.jcoglan.com.

And there you have it, a solution to this challenge in JavaScript.