DZone Snippets: permutation code

Permutations

scvalex (Alexandru Scvortov) — Wed, 03 Oct 2007 10:00:09 GMT

Generates all permutation of n. Uses the naive (stupid) "let's generate all imaginable possibilities and see which are permutations" algorithm.

Time: O(n!)



#include 



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

	int i = n - 1;

	v[i] = v[i] + 1;

	while ((i >= 0) && (v[i] > n)) {

		v[i] = 1;

		i--;

		if(i >= 0)

			v[i]++;

	}



	if (i < 0)

		return 0;

	return 1;

}



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

	int i;



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

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

	printf("\n");

}



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

	int i, j;



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

		for (j = i + 1; j < n; j++)

			if (v[i] == v[j])

				return 0;



	return 1;

}



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

	int v[128];

	int n = 6;

	int i;

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

		v[i] = i + 1;



	while (next(v,n))

		if (is_perm(v,n))

			printv(v,n);



	return 0;

}

C - Permutation multiplication

scvalex (Alexandru Scvortov) — Thu, 17 May 2007 07:29:30 GMT

This code multiplies the permutations given as imput via in. This uses the normal human search and write algorithm. It goes through the input many times.

Example:
In: (acfg)(bcd)(aed)(fade)(bgfae)
Out: (a d g) (c e b) (f)



typedef char str[64];



void pmul_c(str in, str out) {

  int n = strlen(in);

  char *m = (char*)malloc(sizeof(char) * n + 1);

  memset(m, 0, n);

  m[n] = 0;



  int k = 0;

  int i = 0;

  int c;

  for (; i < n; ++i)

    if (in[i] == '(') {

      m[i] = 1;

      c = in[i + 1];

    } else if (in[i] == ')') {

      m[i] = 1;

      in[i] = c;

    }



  char start;

  char curent;

A2:

  i = 0;

  while (m[i] == 1)

    ++i;

  if (i == n)

    return;

  start = in[i];

  out[k++] = '(';

  out[k++] = start;

  m[i] = 1;



A3:

  curent = in[++i];

  ++i;



A4:

  while ((i < n) && (in[i] != curent))

    ++i;

  if (i < n) {

    m[i] = 1;

    goto A3;

  }



  if (curent != start) {

    out[k++] = curent;

    i = 0;

    goto A4;

  }



  out[k++] = ')';

  goto A2;



  out[k] = 0;

}

All permutations of a list in Python

brewbuck (Scott L) — Tue, 20 Feb 2007 23:46:04 GMT

This function returns a list containing all permutations of the input list. Does not work directly on strings -- explode the string into a list of characters to do that.



def perm(l):

    sz = len(l)

    if sz <= 1:

        return [l]

    return [p[:i]+[l[0]]+p[i:] for i in xrange(sz) for p in perm(l[1:])]

Permutations in Ruby

ntk () — Fri, 19 Jan 2007 15:56:26 GMT





# From: http://www.rubyonrailsblog.com/articles/2006/08/31/permutations-in-ruby-can-be-fun (in the comments)

# Author: Brian Mitchell



class Array

  # The accumulation is a bit messy but it works ;-)

  def sequence(i = 0, *a)

    return [a] if i == size

    self[i].map {|x|

      sequence(i+1, *(a + [x]))

    }.inject([]) {|m, x| m + x}     # this has to be used instead of flatten so I can sequence something

                                    # like [[[4]]] -> [[[4]]] rather than -> [[4]]; ruby 1.9 has an option for flatten

  end

end





p [(0..3), [4,6]].sequence             #=> [[0, 4], [0, 6], [1, 4], [1, 6], [2, 4], [2, 6], [3, 4], [3, 6]]      

p [(0..3).collect, [4, 6]].sequence







# http://wiki.rubygarden.org/Ruby/page/show/ArrayPermute

# Permute an array, and call a block for each permutation

# Author: Paul Battley



    class Array

        def permute(prefixed=[])

            if (length < 2)

                # there are no elements left to permute

                yield(prefixed + self)

            else

                # recursively permute the remaining elements

                each_with_index do |e, i|

                    (self[0,i]+self[(i+1)..-1]).permute(prefixed+[e]) { |a| yield a }

                end

            end

        end

    end





%w[a b c].permute { |x| puts(x.join('')) } 



[0, 1, 2, 3 ].permute { |x| puts(x.join('-')) } 







# http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/32844

# Author: Steven Grady



class Array

  def permutations

    return [self] if size < 2

    perm = []

    each { |e| (self - [e]).permutations.each { |p| perm << ([e] + p) } }

    perm

  end

end



p (1..4).to_a.permutations







# http://blade.nagaokaut.ac.jp/~sinara/ruby/math/combinatorics/array-perm.rb

# Author: Shin-ichiro Hara

# For many more permutation snippets see: 

# http://blade.nagaokaut.ac.jp/~sinara/ruby/math/combinatorics/



class Array

  def perm(n = size)

    if size < n or n < 0

    elsif n == 0

      yield([])

    else

      self[1..-1].perm(n - 1) do |x|

	(0...n).each do |i|

	  yield(x[0...i] + [first] + x[i..-1])

	end

      end

      self[1..-1].perm(n) do |x|

	yield(x)

      end

    end

  end

end



if $0 == __FILE__

  ["a", "b", "c", "d"].perm(3) do |x|  

    p x

  end

end







# Based on:

# http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/139290

# Author: Endy Tjahjono



class String

   def perm

       return [self] if self.length < 2

       ret = []

    

       0.upto(self.length - 1) do |n|

          #rest = self.split('')                

          rest = self.split(//u)            # for UTF-8 encoded strings

          picked = rest.delete_at(n)

          rest.join.perm.each { |x| ret << picked + x }

       end



       ret

   end

end



p "abc".perm      #=>  ["abc", "acb", "bac", "bca", "cab", "cba"]







require 'permutation'



# http://permutation.rubyforge.org 

# http://permutation.rubyforge.org/doc/classes/Permutation.html

# sudo gem install permutation --remote

# For more examples see permutation-0.1.4/examples/tsp.rb and permutation_0.1.4/lib/permutation.rb:

# curl http://files.rubyforge.vm.bytemark.co.uk/permutation/permutation-0.1.4.tgz | tar xfz -



perm = Permutation.new(3)   

p perm.map { |p| p.value }        #=>  [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

Another Pyrex Permutation Generator

llimllib (Bill Mill) — Wed, 02 Aug 2006 23:59:41 GMT

// description of your code here



cdef class PermuteJ:



   cdef int n, first

   cdef int lst3[32]

   cdef object lst, lst2



   def __init__(self, lst):

       cdef int i

       self.lst = lst

       self.lst2 = lst[:]

       self.first = 0

       self.n = len(lst) - 1

       if self.n >= 31:

           raise Exception, "Are you kidding?"

       for i from 0 <= i < len(lst):

           self.lst3[i] = i



   def __iter__(self):

       return self



   def __next__(self):

       cdef int j, l, k, x, y, z, sn, length, neg1, neg2, neg3

       cdef int* sl

       cdef object output



       if self.first == 0:

           self.first = 1

           return self.lst2

       if self.n == 1:

           return [self.lst[1], self.lst[0]]



       sn = self.n

       length = sn + 1

       sl = self.lst3

       neg1 = sn

       neg2 = length - 2

       neg3 = length - 3

       while 1:

           if sl[neg2] < sl[neg1]:

               sl[neg2], sl[neg1] = sl[neg1], sl[neg2]

           elif sl[neg3] < sl[neg2]:

               if sl[neg3] < sl[neg1]:

                   sl[neg3], sl[neg2], sl[neg1] = sl[neg1], sl[neg3], sl[neg2]

               else:

                   sl[neg3], sl[neg2], sl[neg1] = sl[neg2], sl[neg1], sl[neg3]

           else:

               j = sn - 3

               if j < 0: raise StopIteration

               y = sl[j]

               x = sl[neg3]

               z = sl[neg1]

               while y >= x:

                   j = j - 1

                   if j < 0: raise StopIteration

                   x = y

                   y = sl[j]

               if y < z:

                   sl[j] = z

                   sl[j+1] = y

                   sl[sn] = x

               else:

                   l = neg2

                   while y >= sl[l]:

                       l = l - 1

                   sl[j], sl[l] = sl[l], y

                   sl[sn], sl[j+1] = sl[j+1], sl[sn]

               k = j + 2

               l = neg2

               while k < l:

                   sl[k], sl[l] = sl[l], sl[k]

                   k = k + 1

                   l = l - 1



           lst = self.lst

           lst2 = self.lst2

           for j from 0 <= j < length:

               lst2[j] = sl[j]



           return lst2

Generate all permutation of a list

korakot (Korakot Chaovavanich) — Tue, 20 Sep 2005 21:40:02 GMT

From Michael Davies's recipe.



def all_perms(str):

    if len(str) <=1:

        yield str

    else:

        for perm in all_perms(str[1:]):

            for i in range(len(perm)+1):

                yield perm[:i] + str[0:1] + perm[i:]

Some example usage



>>> for p in all_perms(['a','b','c']):

	print p



['a', 'b', 'c']

['b', 'a', 'c']

['b', 'c', 'a']

['a', 'c', 'b']

['c', 'a', 'b']

['c', 'b', 'a']

A great use of generator and recursive call.