miércoles, marzo 18, 2009

Permutaciones con String en Java

A continuación una clasesilla que implemente, para realizar la permutación de String en Java.

La idea es la siguiente, si usted le pasa la palabra "cat", la clase hace cat.length! permutaciones con las diferentes combinaciones para esta cadena, es decir:

[act, atc, cat, cta, tac, tca]

A continuación el código (perdón por los comentarios en ingles):




/**
* Useful class to figure out the permutation of the strings.
* @author jsanca
*
*/
public class StringPermutations {

/**
* Use this method to figure out the permutation of the String.
* @param string
* @return collection with the permutation.
*/
public static Collection doPermutations(String string) {

Collection permutationsCollection = new TreeSet();

// verify the trival case, the permutation of 1 is 1, anything else, will use the permutation.
permutationsCollection.addAll((string.length() == 1) ? Arrays.asList(string)
: permutations(string, string.length()));

return permutationsCollection;
} // permutations.

/// apply the shiftleft over the string
private static String shiftleft(String s) {

return new StringBuilder(s.substring(1)).append(s.substring(0, 1))
.toString();
} // shiftleft.

private static Collection permutations(String string, int depth) {

Collection permutations = new ArrayList();

if (depth >= 1) {

// do the permutations of the current string.
permutations.addAll(permutations(string));
// do the permutations of the next string.
permutations.addAll(permutations(shiftleft(string), --depth));
}

return permutations;
} // permutation.

private static Collection permutations(String string) {

Collection permutations = new HashSet();
String subSet = null;

// stop condition, this is the trivial case for the items.
if (string.length() == 2) {

// basic permutation.
permutations(permutations, string.substring(0, 1), string
.substring(1));
} else {

// do the permutations merging the index with the rest of the subset.
for (int i = 0; i < string.length(); ++i) {

subSet = buildString(string, i);
// combinate the index with the permutation of the rest of the subset.
permutations(permutations, string.subSequence(i, i + 1),
permutations(subSet, subSet.length()));
}
}

return permutations;
} // permutations.

// create a string except the "i" index.
private static String buildString(String string, int i) {

String buildString = null;

if (i == 0) {

buildString = string.substring(1);
} else {

if (i == string.length() - 1) {

buildString = string.substring(0, string.length() - 1);
} else {

buildString = new StringBuilder(string.substring(0, i)).append(
string.substring(i + 1)).toString();
}
}

return buildString;
} // buildString.

// BASIC CASE OF PERMUTATION.
private static void permutations(Collection permutations,
CharSequence permutation1, CharSequence permutation2) {

permutations.add(new StringBuilder(permutation1).append(permutation2)
.toString());
permutations.add(new StringBuilder(permutation2).append(permutation1)
.toString());
} // permutations.

// SCALAR + SET PERMUTATION.
private static void permutations(Collection permutations,
CharSequence aPermutation, Collection permutation) {

CharSequence otherPermutation = null;

for (Iterator iterator = permutation.iterator(); iterator
.hasNext();) {

otherPermutation = iterator.next();
permutations.add(new StringBuilder(aPermutation).append(
otherPermutation).toString());
}
} // permutations.


} // E:O:F:Permutations.


/**
* Util class for Math operations.
* @author jsanca
*
*/
public class MathUtil {

/**
* Calculate the factorial of the number, if it is negative, it will figure out like C++ uint.
* @param number Some number
* @return if the number is 0 will returns 1, in other case will returns the factorial:
* n! = 1 * 2 * 3 * 4 * ... * (n-1) * n
*/
public static double factorial(double number) {

return (0 >= number) ? 1 :
number * factorial(number - 1);
}


}


2 comentarios:

Carlos P. dijo...

Maldito!
Acá va en Perl uno que hice.
..Espero que esta vara no salga muy despichado.

open(FILE_OUTPUT, ">@ARGV[0]"); #in case the output is
$| = 1;

&permutate("abcd", 1);

#GLOBALS
#stores the entry length, so that it can be utilized after the recursive call
$entryDepth = undef;
#string vector of size n (n = string length) used to keep the record of the last permutations
@permStateVector = ();

#calls permutateRec with a fixed deph and initializes the permutation state vector
#@toFile is a boolean parameter that if true permits writing to a file
sub permutate{
my $string = shift;
my $toFile = shift;
my $depth = length($string);
@permStateVector = &fillPermStateVector(0, $string, @permStateVector);
&permutateRec($string, $depth, $toFile);
}

#gets all the permutations in a string and prints them out.
#Printing to a file optional
sub permutateRec{
my $string = shift;
my $depth = shift;
my $toFile = shift;

for (my $i = 1; $i <= $depth; $i++){
$entryDepth = $depth if ($entryDepth == undef);

if ($depth == 1){
my $entry = &permutateEntry(length($string) - $entryDepth, @permStateVector);
print $entry."\n";
print FILE_OUTPUT $entry."\n" if ($toFile);

$entryDepth = undef;
}
&permutateRec($string, $depth - 1, $toFile);
}
}

#modifies the permutation state vector by changing an entry in a specific position
# with a new permutation. After the single entry is modified, the rest of the entries
# in the vector are filled with the new entry (starting from that specific position)
sub permutateEntry{
my $pos = shift;
@permStateVector = @_;
my $entry = @permStateVector[$pos];

$entry = substr($entry, 0, $pos).
&shiftLeftCharsStr(substr($entry, $pos), 1);

@permStateVector = &fillPermStateVector($pos, $entry, @permStateVector);

return $entry;
}

#shift-lefts a string a specific number of characters
sub shiftLeftCharsStr{
my $string = shift;
my $charsNumber = shift;
my $newString = substr($string, $charsNumber).
substr($string, 0, $charsNumber);
return $newString;
}

#fills the permutation state vector with the same string starting from a specific position
sub fillPermStateVector{
my $startingPos = shift;
my $string = shift;
my @permStateVector = @_;
for (my $i = $startingPos; $i < length($string); $i++){
@permStateVector[$i] = $string;
}
return @permStateVector;
}

Carlos P. dijo...

que madre. Al final se perdieron todos los espacios :S