# How to program a permutation combination function with filter for rules

I am working on a metal related software where in I have to programmatically make numerous metal alloy  combination ; For example if there are 5 types of metals it will use combination function to make combination of metal ; suppose metals are  X, Y,A,B, & Z  then there combination could be XYABZ , ZABYX  and so on& however there are some predefined rules set by users like  X cannot go with B
Or  Y cannot with Z  and such combination will be removed programmatically

Has any one any idea as to how to approach  this programmatically; should I use brute force of computer to make these combination and then filter them by Rules .. or is there any better efficient logic?

###### Who is Participating?

Commented:
#!/usr/bin/perl
my %rule;
sub permute {
my \$p=shift;
if( @_ ){
!\$rule{\$p->[-1]}{\$_[\$_]} && permute([@\$p,\$_[\$_]],@_[ 0 .. \$_-1, \$_+1 .. \$#_])for 0..\$#_;
}else{
print "@\$p\n";
}
}
while( <DATA> ){
warn "unknown rule \$_" and next unless /(\w+)\s*cannot go with\s*(\w+)/;
\$rule{\$1}{\$2}++;
}
permute([""],qw(a b c X Y A B Z));
__DATA__
a cannot go with b
a cannot go with c
c cannot go with a
X cannot go with B
Y cannot go with Z
0

Commented:
I would put the filtering into the combination generation, so, if you have a set of loops that iterate through the metals

ABXYZ
ABXZY
ABYXZ
ABYZX
etc....

if you hit an illegal combination  "BX"  for example.  you can skip everything below it.  So, in the example above...

ABX     -stop generating permutations here.everything following this will be illegal.
ABYXZ
ABYZX
etc....

0

Author Commented:
Hello sdstuber:

Thanks for the response
but here the core bottle neck we are facing is how on run time these rules will be cheeked against the generating combination

Especially these rules will not be hard coded but defined by users

TPS
0

Commented:
Do you have maximum of 5 metals?  If so, there are only 120 permutations.
With a data set that small you should be able generate all of them and then iterate through them and remove illegal combinations in milliseconds, if not microseconds.
Put the illegal combinations in an array and iterate through them. against the list of all permutations.
0

Commented:
Why does a metal alloy depend on order?  Aren't they all mixed together in solution anyway?
0

Commented:
Are the rules always of the form
<a> cannot go with<b>
0

Author Commented:

suppose there are A,b,c metals then

rules are of the nature <a> cannot go with <b>
but (for two metal allows) ac is different then ca

first metal has more % then second metal
0

Commented:
So "a cannot go with b" disallows all of the following: ab, abc, cab, acb as well as ba, bac, bca, ...
0