#!/usr/local/bin/perl

########################################################################################
# Wed 31 Mar 2004 01:02:30 PM EST
#
# generation of r-permutations from n objects in lexicographic order
# algorithm from Page&Wilson "An Introduction to Computational Combinatorics"
#
#
# in case of oligonucleotides r=length of oligonucleotide
# (n=4: A, T, C, G)
#

#Short summary of the algorithm for elements 1,2,3,..,n:
# start with permutation 1,1,...,1
#to calculate r-permutation k(1),k(2),...,k(r)
#	1. Find the largest i such that k(i)<n
#	2. Add 1 to k(i)
#	3. Set k(i+1)=...=k(r)=1

########################################################################################

unless (@ARGV==1) {die "provide length of oligonucleotide in the command line";}

$n=4;
$r=$ARGV[0];
@nuc=qw(A C G T);

#starting oligo is AA...A (11..1)
@perm=();
for($i=0;$i<$r;$i++){
    $perm[$i]=1;
    print "$nuc[$perm[$i]-1]";
}
print "\n"; 

while ($flag==0){ #determine new permutation until the oligo becomes TT..T
    for($i=$r-1;$i>=0;$i--){
	if($perm[$i]!=$n){
	    $perm[$i]++;
	    for($j=$i+1;$j<=$r;$j++){
		$perm[$j]=1;
	    }
	    last;
	}
    }

    for($i=0;$i<$r;$i++){
	print $nuc[$perm[$i]-1];
    }
    print "\n"; 

    for($i=0;$i<$r;$i++){
	if($perm[$i]==$n){
	    $flag++;
	}	
    }
    if($flag==$r){
	$flag=1;
    }
    else{
	$flag=0;
    }	

}