I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: String Permutations

11.08.2012
| 6953 views |
  • submit to reddit

It's been a while, but the Thursday code puzzlers are back! The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you think is suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

String Permutations

Taking a String as a parameter, list all the possible permuations of that string alphabetically.

There's a few different ways to achieve this. If you wish, you can express the efficiency of the algorithm you come up with using Big O notation.

Catch up on all our previous puzzlers here

Comments

Vijay Nathani replied on Thu, 2012/11/08 - 4:20am

 Groovy code

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

Robby Pelssers replied on Thu, 2012/11/08 - 9:00am

Scala code:     

******************

"rock".permutations.toList.sorted

List(ckor, ckro, cokr, cork, crko, crok, kcor, kcro, kocr, korc, krco, kroc, ockr, ocrk, okcr, okrc, orck, orkc, rcko, rcok, rkco, rkoc, rock, rokc)

sun east replied on Fri, 2012/11/09 - 12:58am in response to: Robby Pelssers

 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

Vijay Nathani replied on Fri, 2012/11/09 - 2:19am in response to: sun east

Implementation dependent optimizations may not be a good idea unless we also have tests to ensure the same.

Daniel Seidler replied on Fri, 2012/11/09 - 3:46am

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!)
}

Alexander DiMauro replied on Wed, 2012/11/14 - 6:29am

Ruby:

puts "ruby".chars.to_a.permutation.map(&:join).sort

Jeff Schwartz replied on Thu, 2012/11/15 - 11:11am

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.

Jeff Schwartz replied on Fri, 2012/11/16 - 3:30pm in response to: Vijay Nathani

I believe if the code gets the right results then that is the test case.

Marian Kamenistak replied on Mon, 2013/11/04 - 11:37am

Using Java generics:


	public static <T> Set<List<T>> perm(List<T> input){
		return perm(new ArrayList<T>(), input, new HashSet<List<T>>());
	}

	public static <T> Set<List<T>> perm(List<T> formed, List<T> rests, Set<List<T>> result){
		if(rests.size() == 0){
			result.add(formed);
			return result;
		}else{
			Set<List<T>> round = new HashSet<List<T>>();
			for(T rest1 : rests){
				List<T> newFormed = new ArrayList<T>(formed);
				newFormed.add(rest1);
				List<T> newRests = new ArrayList<T>(rests);				
				newRests.remove(rest1);
				//formed + rest1:
				Set<List<T>> newPerm = perm(newFormed, newRests, result);
				round.addAll(newPerm);				
			}
			return round;
		}
	}

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.