DZone Snippets: permutations code

Permutations of letters in a word

mcmire () — Sun, 13 Jul 2008 22:21:49 GMT

I've been programming for a while but for some reason figuring this out was really hard - it took me 2 and a half hours. Unsurprisingly, the solution is extremely simple...



#!/usr/bin/ruby

# permute - takes a word and returns all the permutations of the letters in the word



def permute(word="")

  permutations_among(word.split(//))

end

def permutations_among(letters)

  permutations = []

  if letters.size == 1

    permutations << letters.first

  else

    letters.each_with_index do |letter, i|

      surrounding_letters = letters.dup; surrounding_letters.delete_at(i)

      permutations += permutations_among(surrounding_letters).map {|permutation| letter + permutation }

    end

  end

  permutations

end



permute(ARGV.shift).each {|permutation| puts permutation }

Some benchmarks against other implementations:

* Array#permutations: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/32844
* Array#perm: http://blade.nagaokaut.ac.jp/~sinara/ruby/math/combinatorics/array-perm.rb
* geta: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/139290
* String#perm (based on geta)
* Array#each_permutation: http://knanshon.blogspot.com/2006/08/ruby-permutations.html
* permutation: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/140345


                                              user     system      total        real

permutations_among:                       1.680000   0.010000   1.690000 (  1.700779)

Array#permutations:                       1.740000   0.010000   1.750000 (  1.798288)

geta:                                     2.430000   0.010000   2.440000 (  2.506668)

String#perm:                              2.260000   0.010000   2.270000 (  2.280652)

Array#each_permutation:                   0.820000   0.000000   0.820000 (  0.827463)

permutation:                              2.140000   0.010000   2.150000 (  2.171966)

Benchmark code:



require 'benchmark'



N = 1_000

Benchmark.bm(40) do |x|

  letters = %w(a b c d e)

  string = "abcde"

  x.report("permutations_among:") do

    N.times { permutations_among(letters) }

  end

  x.report('Array#permutations:') do

    N.times { letters.permutations }

  end

  x.report('geta:') do

    N.times { geta(string) }

  end

  x.report('String#perm:') do

    N.times { string.perm }

  end

  x.report('Array#each_permutation:') do

    N.times { letters.each_permutation {|perm| } }

  end

  x.report('permutation:') do

    N.times { 0.upto(string.length.factorial-1) {|i| permutation(string, i)} }

  end

end

So, not bad for a first try ;)

Generate permutations

scvalex (Alexandru Scvortov) — Wed, 10 Oct 2007 14:45:36 GMT

Generates all the permutations of {1, 2, ..., n}.

See this for further explanations.



#include 



void printv(int v[], int n) {

	int i;



	for (i = 0; i < n; i++)

		printf("%d ", v[i]);

	printf("\n");

}



/*!

	This just swaps the values of a and b



	i.e if a = 1 and b = 2, after



		SWAP(a, b);



	a = 2 and b = 1

*/

#define SWAP(a, b) a = a + b - (b = a)



/*!

	Generates the next permutation of the vector v of length n.



	@return 1, if there are no more permutations to be generated



	@return 0, otherwise

*/

int next(int v[], int n) {

	/* P2 */

	/* Find the largest i */

	int i = n - 2;

	while ((i >= 0) && (v[i] > v[i + 1]))

		--i;



	/* If i is smaller than 0, then there are no more permutations. */

	if (i < 0)

		return 1;



	/* Find the largest element after vi but not larger than vi */

	int k = n - 1;

	while (v[i] > v[k])

		--k;

	SWAP(v[i], v[k]);



	/* Swap the last n - i elements. */

	int j;

	k = 0;

	for (j = i + 1; j < (n + i) / 2 + 1; ++j, ++k)

		SWAP(v[j], v[n - k - 1]);



	return 0;

}



int main(int argc, char *argv[]) {

	int v[128];

	int n = 3;



	/* The initial permutation is 1 2 3 ...*/

	/* P1 */

	int i;

	for (i = 0; i < n; ++i)

		v[i] = i + 1;

	printv(v, n);



	int done = 1;

	do {

		if (!(done = next(v, n)))

			printv(v, n); /* P3 */

	} while (!done);



	return 0;

}

Factorial function

Minimiscience (Guildorn Tanaleth) — Thu, 05 Jul 2007 03:50:14 GMT

A (non-recursive) factorial function

int factorial(int x) {

 int fac = 1;

 for (int i=2; i<=x; i++) fac *= i;

 return fac;

}

Also, with this function defined, you can use two macros for calculating combinations & permutations:

#define nCr(n, r) (factorial(n) / factorial(n-r) / factorial(r))

#define nPr(n, r) (factorial(n) / factorial(n-r))