#include <stdio.h>

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;
}

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;
}

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:])]

# 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]]

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

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:]

>>> 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']