Solved

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

Posted on 2009-05-02
450 Views
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?

0
Question by:tps2009

LVL 73

Expert Comment

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 Comment

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

LVL 73

Expert Comment

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

LVL 84

Expert Comment

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

LVL 84

Expert Comment

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

Author Comment

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

LVL 84

Accepted Solution

#!/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

LVL 20

Expert Comment

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

## Featured Post

### Suggested Solutions

Graph 5 47
Graph Function 6 47
Interest rate formula 7 42
What statistical method/formula can be used for Range and Trend? 4 50
Notes 8.5 Archiving Steps and Tips This article covers setting up a Notes archive, and helps understand some of the menu choices making setting up and maintaining a Notes archive file easier.
Skype is a P2P (Peer to Peer) instant messaging and VOIP (Voice over IP) service – as well as a whole lot more.
This video will demonstrate how to find the puppet warp tool from the edit menu and where to put the points to edit.