Katie on Rails

On Internets and other things

One More Ruby Array Trick

I was recently working through a series of coding puzzles, and came across one that asks you to write a function that takes a string and produces every possible permutation of its letters. So “abc” could be “abc”, “acb”, “bac”, “bca”, “cab”, “cba”. The book where I found the puzzle had an example of how to solve the problem in Java:

1
2
3
4
5
6
7
8
9
10
11
12
13

void permute( String str ){
int length = str.length(); boolean[] used = new boolean[ length ]; StringBuffer out = new StringBuffer(); char[] in = str.toCharArray();
doPermute( in, out, used, length, 0 ); }
void doPermute( char[] in, StringBuffer out,
boolean[] used, int length, int level ){
if( level == length ){ System.out.println( out.toString() ); return;
}
for( int i = 0; i < length; ++i ){ if( used[i] ) continue;
out.append( in[i] );
used[i] = true;
doPermute( in, out, used, length, level + 1 ); used[i] = false;
out.setLength( out.length() - 1 );
} }

I was halfway through working through the problem in Ruby, when it occurred to me that Ruby might have an easier way of doing things. It does. It has a permutate method that allows us to solve the problem with one line of code. Behold:

1

%w[a b c].permutation.map &:join