Perl Chemical adder (non Perl help Welcomed)

PB0711 · 02-02-2006, 11:57 AM

Hey everybody,

Well so far I got pretty far (for me) but the complexity has gone up and so I cannot figure it out. Any help with either the algorithm or the Perl itself would be very much appreciated.
So this is what I have a hash with 4 different elements (carbon=12, Nitrogen=15, Oxygen=16, and Hydrogen=1). I then have to match different possibilities of these to a overall number (Mass number). So for example I have to find what "15" could be. It could be CH3 or N. I would then print this to a file telling me that 15 could be CH3 or N.

Cheers,

PB

PS I would give you my code but I really don't think it will help any!

graemef · 02-02-2006, 12:34 PM

I can't help you with perl but the algorithm I can...

Sort the list in descending order of Mass.
Move through the list until you have a Mass equal to or less than your total
Your solution will consist of a list of all the remaining elements (one entry for each remaining element)
For each solution revise the mass and repeat the process from 2, but remember to record the position in the list and don't go backwards. (otherwise you will get duplicated solutions such as CH3, HCH2, H2CH and H3C)

This can be implemented using a recursive function with the stopping condition being when each solution has a required mass value of 0.

Given your example the algorithm will work as follows:

Target Mass = 15

Oxygen=16
Nitrogen=15
Carbon=12
Hydrogen=1

Solutions (1st iteration)
Nitrogen=15 Revised Target=0
Carbon=12 Revised Target=3
Hydrogen=1 Revised Target=14

Solutions (2nd iteration)
Nitrogen=15 Revised Target=0
Carbon=12 + Hydrogen=1 + Hydrogen=1 Revised Target=1
Hydrogen=1 + Hydrogen=1 + Hydrogen=1 Revised Target=12

Solutions (3rd iteration)
Nitrogen=15 Revised Target=0
Carbon=12 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 Revised Target=0
Hydrogen=1 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 Revised Target=11

Solutions (4th iteration)
Nitrogen=15 Revised Target=0
Carbon=12 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 Revised Target=0
Hydrogen=1 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 Revised Target=10

eventually...

Solutions (15th iteration)
Nitrogen=15 Revised Target=0
Carbon=12 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 Revised Target=0
Hydrogen=1 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 + Hydrogen=1 Revised Target=0

Giving N, CH3 and H15

You may then need additional rules to exclude certain combinations (I doubt if H15 is valid).

graeme.

PB0711 · 02-02-2006, 05:27 PM

Thank you!

One quick question, I probably should have given a better example but what happens if it's something like 29 where it could be C2H5, CNH3 or COH. Probably just if statements? Must say the loops are getting me very confused.

PB

graemef · 02-02-2006, 05:50 PM

If you manage to use recursion then it will work.

For each valid value add it to the list decrement the target mass and then call the function again with the new data. So one call may generate several calls of the same function.

Target Mass = 29

Oxygen=16
Nitrogen=15
Carbon=12
Hydrogen=1

First Iteration will have

Oxygen TargetMass = 13
Nitrogen TargetMass = 14
Carbon TargetMass = 17
Hydrogen TargetMass = 28

The second round of recursive calls will give you:
Oxygen + Carbon TargetMass = 1
Oxygen + Hydrogen TargetMass = 12
Nitrogen + Carbon TargetMass = 2
Nitrogen + Hydrogen TargetMass = 13
Carbon + Carbon TargetMass = 5
Carbon + Hydrogen TargetMass = 16
Hydrogen + Hydrogen TargetMass = 27

Check out how recursive functions are written.

graeme.

microsoft/linux · 02-02-2006, 08:53 PM

Quote:

Originally Posted by graemef

You may then need additional rules to exclude certain combinations (I doubt if H15 is valid).

graeme.

Actually, it might be, you'd get 7.5 H2. That is, 7.5 moles of H2, I think. Maybe not.....I'm not fully sure, but I'm just a high school Chem II student, so correct me if I'm wrong.

graemef · 02-02-2006, 08:59 PM

My last foray into a chemistry lab was over twenty-five years ago so I've no idea, but I can always rustle you up a recursive algorithm!

PB0711 · 02-02-2006, 11:51 PM

It's actually for a mass spectra program. So since the molecules, which have been ionized are banging into Helium gas as they fly down a time of flight tube, anything is possible. However, for 15 Hydorgens to come off without being dectected would unusal. If you want to know me about the whole Mass Spectra thing send me a message on the LQ thingy.

PB

PS THANK YOU for the help on the recursive function!

PB0711 · 02-04-2006, 05:43 PM

I'm sorry to be a pain but could I just ask for a little help on the recursive function

. I've done a google and have done some reading

. I understand them, but don't know where to start. If you were to write it , not in perl, I know you don't know perl, but in your own programming language or even psudo code where would you start? As I understand it I need one function for every chemical element that I have, right?

Thank again, and sorry to be a pain.

PB

graemef · 02-05-2006, 11:35 AM

Okay I'll try and give you something...

So we are starting off with a structure that holds the data, I'll call it Elements and a mass target that I'll call Mass.

We require a recursive function that will build the possible combinations, which I'll call Combinations.

The signature for Combination will be as follows

Code:

Combination (Element, Mass, Posn, Result)

#  where:
#  Element is a sorted list of elements (in ascending order) Input
#  Mass is the target Mass                                   I/O
#  Posn is the current position in the Element array         I/O
#  Result is the current result                              Output (temp)
#  Return value a string with each value separated by a semicolon

Pseudo code:

Code:

# Check that the Mass is positive
If Mass <= 0
   Return Result + "; " # This is added to signify the end of one result

#  Traverse the array until a valid element can be found
While Element[Posn].ElementsMass > Mass
   Posn = Posn -1

# Now pointing at a valid element so create combination results using each of the remaining elements
While Posn > 0
Begin
   Result = Result + Element[Posn].ElementsCode
   newMass = Mass - Element[Posn].ElementsMass
   combinationString = Combination(Element, newMass, Posn, Result)
   Posn = Posn -1
End

return combinationString

# end of recursive function Combination

This function may be called as follows:

result = Combination (Element, 15, size(Element), "").

Points to be wary of.

The way I use the structure Elements is probably not the same as the way you have it set up so the code will need to reflect that, but I hope you can understand what I was getting at
recursive functions can lead to problems if they are not terminated correctly. Here the termination is with the if Mass <= 0. If Mass is < 0 then the result is actually invalid and you would return blank rather than Result, however that should never happen if you have an element with a value of 1. But it would be good to split that into two parts == 0 and < 0.
Add debugging diagnostics so that you can see what is happening when you build it
I think that I have the result being set up correctly. But check by going through it yourself. (The more eyes the better.)

graeme

hasenschlau · 02-06-2006, 03:56 AM

using the algorithm from graemef (nice!) I would write something like that in perl:

#a list with the masses ordered
my @element_masses= (16, 15, 12, 1);

#a list of hashes containing the results
my @list_of_results;

#a hash containing the results to start with
my %a_result= ('16' => 0,
'15' => 0,
'12' => 0,
'1' => 0);

#the value we want to start with
my $val= 29;

#start the function
&find_molecules($val, 0, \%a_result);

#to print the results on your screen
foreach my $rh_result(@list_of_results){
foreach(keys %{$rh_result}){
print ($_, "\t", $rh_result->{$_}, "\n");
}
print "*******************\n";
}

sub find_molecules{
my ($current_val, $current_index, $rh_result)= @_;

#we go through all the element_masses, which weren't below equal or below zero before..
for(my $i=$current_index; $i<=$#element_masses; $i++){

#if the current_val is equal the current element_mass
if(!($current_val-$element_masses[$i])){
#we add the result to the list_of_results
my %a_result= %{$rh_result};
$a_result{$element_masses[$i]}++;
push @list_of_results, \%a_result;

#if the difference is greater than zero, we keep on going
}elsif($current_val-$element_masses[$i] > 0){
my %a_result= %{$rh_result};

#we add the current element_mass to the result hash
$a_result{$element_masses[$i]}++;

#and call ourselves with the new parameters..
&find_molecules($current_val-$element_masses[$i], $i, \%a_result);
}
}
}

well, I guess now you like to get only existing molecules.. so I would use another hash which uses the result-hashes as keys (in the form of a string) and a list with possible molecules as the results..

hope that I helped you
hasenschlau