Velocity Reviews > Perl > A case with Combinations in Sets

# A case with Combinations in Sets

anirbid.banerjee@gmail.com
Guest
Posts: n/a

 02-19-2008
Hi,

I have two Sets A and B with N DISTINCT elements each. Both A and B
are related to each other so that B contains complement of A. For eg.A
= {a, b, c} , B = {a*, b* c*}. I would need a perl script to generate
all possible combinations between A and B satisfying the following
conditions:

a) The number of elements in the Combined set n(C) = N.
b) None of the combination should contain both an element and its
complement : i.e. {a, a*, b}, {b,c, c*} are invalid combinations.
c) There should be exactly 2^N combinations.

Regards,
Anirbid

xhoster@gmail.com
Guest
Posts: n/a

 02-19-2008
"(E-Mail Removed)" <(E-Mail Removed)> wrote:
> Hi,
>
> I have two Sets A and B with N DISTINCT elements each. Both A and B
> are related to each other so that B contains complement of A. For eg.A
> = {a, b, c} , B = {a*, b* c*}. I would need a perl script to generate
> all possible combinations between A and B satisfying the following
> conditions:

Since set B is completely and readily determined by set A, there is really
no point in actually having it. Just let it be implied by A.

> a) The number of elements in the Combined set n(C) = N.
> b) None of the combination should contain both an element and its
> complement : i.e. {a, a*, b}, {b,c, c*} are invalid combinations.
> c) There should be exactly 2^N combinations.

So take all numbers from 0 to 2^N and map each bit-position to one of the
elements in A. Call the ones the elements and the zeros the complements to
the elements.

\$n=6;
foreach (0..2**\$n-1) {
print sprintf "%0\${n}b", \$_ ;
};

Xho

--
The costs of publication of this article were defrayed in part by the
this fact.