randyk has asked for the
wisdom of the Perl Monks concerning the following question:
I have an expansion involving N factors:
(a[0][0] + a[0][1]) (a[1][0] + a[1][1])
(a[2][0] + a[2][1]) ... (a[N1][0] + a[N1][1])
for which I'm trying to find general expressions for
the 2^N terms involved when this is all multiplied
out. Getting an expression for two of the terms
is straightforward when the 2nd indices of the
a coefficients are the same:
$C[0] = 1;
$C[$N1] = 1;
for ($i=0; $i<$N; $i++) {
$C[0] *= $a>[$i]>[0];
$C[$N1] *= $a>[$i]>[1];
}
but I'm stuck on the problem of getting the other
terms. Can someone see a way to do this? Thanks.
UPDATE
Just to clarify the notation, what's desired is
expressions for the 2**N
coefficients of the expansion. For example, for
N = 2 factors and 2**N = 4 terms:
(a[0][0] + a[0][1]) * (a[1][0] + a[1][1]) =
C[0] + C[1] + C[2] + C[3],
where
C[0] = a[0][0] * a[1][0]
C[1] = a[0][0] * a[1][1]
C[2] = a[0][1] * a[1][0]
C[3] = a[0][1] * a[1][1]
No meaning is intended for the
order of the indices of the C array.
There's a number of approaches suggested
below that will get me going  thanks to all
who responded!
Re: Obtaining terms in an expansion
by ikegami (Pope) on Jan 05, 2006 at 21:31 UTC

my $C;
if (@$ar) {
$C = 1;
foreach my $row (@$arr) {
my $sum = 0;
foreach my $ele (@$row) {
$sum += $ele;
}
$C *= $sum;
}
}
By the way, you shoulnd'y use $a and $b as variable names to avoid conflicts with some special variables.
Update: Or maybe
my $cols = @{$arr>[0]};
my $C;
foreach my $col_idx (0 .. $cols1) {
$C>[$col_idx] = 1;
foreach my $row (@$arr) {
$C>[$col_idx] *= $row>[$col_idx];
}
}
 [reply] [d/l] [select] 

I should have supplied an example of what I was looking
for. For example, for N=2:
( arr[0][0] + arr[0][1] ) ( arr[1][0] + arr[1][1] )
what I want to find is
C[0] = arr[0][0] arr[1][0]
C[1] = arr[0][0] arr[1][1]
C[2] = arr[0][1] arr[1][0]
C[3] = arr[0][1] arr[1][1]
It doesn't matter if the coefficients come out in this
order, of course.  [reply] [d/l] [select] 

#! perl slw
use strict;
sub expand{
return @{ $_[0] } if @_ == 1;
map{
my $x = $_;
map{ $x * $_ } &expand;
} @{ pop @_ };
}
my @mat = ( [ 1, 2 ], [ 3, 4 ] );
printf +("%s " x @mat ) . '= ', map{ "[ @$_ ] " } @mat;
print join ' ', expand( @mat );
@mat = ( [ 1, 2 ], [ 3, 4 ], [ 5, 6 ], );
printf +("%s " x @mat ) . '= ', map{ "[ @$_ ] " } @mat;
print join ' ', expand( @mat );
@mat = ( [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ], );
printf +("%s " x @mat ) . '= ', map{ "[ @$_ ] " } @mat;
print join ' ', expand( @mat );
__END__
P:\test>junk
[ 1 2 ] [ 3 4 ] = 3 6 4 8
[ 1 2 ] [ 3 4 ] [ 5 6 ] = 15 30 20 40 18 36 24 48
[ 1 2 3 ] [ 4 5 6 ] [ 7 8 9 ] =
28 56 84 35 70 105 42 84 126 32 64 96 40 80 120 48 96 144 36 72 108 45
+ 90 135 54 108 162
Examine what is said, not who speaks  Silence betokens consent  Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco.  Rule 1 has a caveat!  Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
 [reply] [d/l] 

I don't see an operator between arr[0][0] and arr[1][0], so I presume the parenthesis mean you want to multiply.
Your description does not adequately explain what you want, particularly the (a[N1][0] + a[N1][1]).
Indices from your example:
0,0 1,0
0,0 1,1
0,1 1,0
0,1 1,1
Don't follow. They should be:
0,0 1,0
0,0 1,1
1,0 1,0
1,1 1,1
2,0 1,0
2,1 1,1
3,0 1,0
3,1 1,1
...
The wrong element is incrementing  a[0][N1] * a[1][0], a[0][N1] * a[1][1].
Furthermore, this makes no sense. Are a[0][1] and a[1][1] use repeatedly throughout? If so, why not change them into constants?
Celebrate Intellectual Diversity
 [reply] [d/l] [select] 
Re: Obtaining terms in an expansion
by educated_foo (Vicar) on Jan 06, 2006 at 00:01 UTC

So you want to compute an outer product? For two 1dimensional terms (i.e. vectors) you have:
[a1...an]' * [b1...bn] = [a1*b1 ... a1*bn; ...; an*b1 ... an*bn]
which can be written "a_i * b_j" using physicists' tensor notation.
For two 2dimensional terms (i.e. matrices) you have a tensor product like "a_ij * b_kl", and you can generalize this to any rank (and to other operations besides "*"). I think PDL can compute outer products for low ranks, but you'll probably need to create an iterator or some such to avoid running out of memory with higher ranks.  [reply] [d/l] 
Re: Obtaining terms in an expansion
by runrig (Abbot) on Jan 05, 2006 at 22:28 UTC

If I understand correctly, (one way of looking at the problem) you just need a way to combine N iterators where each iterator iterates through two items. list_iter() and comb_iter() in Laziness in a more consistent way would do that. It would also allow each term to have more than two items if you so desired (which I can't tell if that's a goal from your description of the problem).  [reply] 
Re: Obtaining terms in an expansion
by ivancho (Hermit) on Jan 06, 2006 at 00:57 UTC

ok, so the 2^N terms are each a product of N terms, a[i][j], where j can be 0 or 1 and i goes from 0 to N1
ie, each one looks like, say
a[0][0] * a[1][0] * a[2][1] * a[3][0] * ... * a[N1][1]
So, we want do some binary magic.
how about something like:
#!/usr/bin/perl wl
use strict;
use Data::Dumper;
my $N = 4;
my $size = 32;
my $arr = [[1, 2],
[3, 4],
[5, 6],
[7, 8]];
my @C;
foreach my $m (0..2**$N  1) {
my $vec = "";
vec($vec, 0, $size) = $m;
my @bits = split(//, unpack("B*", $vec));
splice(@bits, 0, $size  $N);
# so @bits now contains the binary expansion of $m
# with exactly $N bits, as you can verify by uncommenting
# print join "::", @bits;
$C[ $m ] = 1;
# now we multiply the $N terms $arr>[i][j]
# where j is the ith bit in the binary expansion of $m
$C[ $m ] *= $arr>[ $_ ][ $bits[$_] ] for 0..$N1;
}
print Dumper \@C;
note, $size must be a power of 2, for vec to work, and unless you're on a 64bit machine, it probably cannot be more than 32.
also, this works for $N no more than 31(32?)  but you may have other problems (memory say), if you want to go above that.
Hope this helps.  [reply] [d/l] [select] 
Re: Obtaining terms in an expansion
by trammell (Priest) on Jan 05, 2006 at 23:19 UTC

Does this do what you want?
my $n = $ARGV[0]  5;
my @terms = qw( a[0][0] a[0][1] );
foreach my $i (1 .. $n1) {
@terms = map { ("$_ a[$i][0]","$_ a[$i][1]") } @terms;
}
foreach my $i (0 .. $#terms) {
print "term[$i] = $terms[$i]\n";
}
Update: fixed offbyone error  [reply] [d/l] 

 [reply] 

That's funny, because when I run the program for N=2, I get:
term[0] = a[0][0] a[1][0] a[2][0]
term[1] = a[0][0] a[1][0] a[2][1]
term[2] = a[0][0] a[1][1] a[2][0]
term[3] = a[0][0] a[1][1] a[2][1]
term[4] = a[0][1] a[1][0] a[2][0]
term[5] = a[0][1] a[1][0] a[2][1]
term[6] = a[0][1] a[1][1] a[2][0]
term[7] = a[0][1] a[1][1] a[2][1]
So perhaps I have an offbyone error, but certainly I'm generating 2^N terms.  [reply] [d/l] 
Re: Obtaining terms in an expansion
by tphyahoo (Vicar) on Jan 06, 2006 at 01:01 UTC

I don't like how this question was asked, and seems I'm not the only one  even after your reply to clarify, I still can't understand what you are after or why.
Are you multiplying polynomials? Taking the square root of a hamiltonian? Calculating the angular velocity of a catapulted gerbil? :)
Maybe it would help if you would link to an article describing the process you are trying to model in perl.  [reply] 

For N=2:
(a+b)*(c+d) = ac + ad + bc + bd
For N=3:
(a+b)*(c+d)*(e+f) = ace + acf + ade + adf +
+ bce + bcf + bde + bdf
What I was after was an explicit expression for
each of the 2**N
terms on the righthandside of these equations.
As for why one would want to do this beyond a homework
question, this problem arises in theories of
quantum computing, particularly in trying to
write an arbitrary state in terms of what's called the
computational basis for an Nqubit state.
 [reply] [d/l] 

I believe that to solve this you would need to create two separate arrays; one to contain the variables on the left side of the equation and another to contain each of the terms on the right side of the equation.
Since you know that you will have 2**N variables on the left side, you would want to create an array named, say, Variable{2**N1) to contain the variables. Then you would create an array Terms[2**N1] to contain the terms generated by multiplying the polynomials.
I don't think one would need a two dimensional array. The first part of the program code could pop up a message box asking what N is, and then it would create the arrays as I described above. Then the code would step through array Variable[] multiplying the variables as appropriate and placing the resulting terms into array Terms[]. So the expansion is simply the sum of the elements of array Terms[2**N1].
I am new to Perl so I am still working on actual code to do what I've described. I think that this is an interesting problem.
jdporter added code and p tags
 [reply] [d/l] [select] 

Completely irrelevant time waster:
#!/your/perl/here
use strict;
use warnings;
{ # closure for sub terms
my @term_list = ('A'..'Z', 'a'..'z');
sub terms
{
my $N = shift;
my $last = 2*$N1;
my @pairs;
my $index = 0;
my $globber = '';
while ( $index < $last )
{
$globber .= '{'
. $term_list[$index++]
. ','
. $term_list[$index++]
. '}';
}
my $terms = join ' + ', glob($globber);
return $terms;
}
} # end closure for sub terms
foreach my $n (1..5)
{
my $terms = terms($n);
print "N=$n: <", $terms, ">\n";
}
exit;
__OUTPUT__
N=1: <A + B>
N=2: <AC + AD + BC + BD>
N=3: <ACE + ACF + ADE + ADF + BCE + BCF + BDE + BDF>
N=4: <ACEG + ACEH + ACFG + ACFH + ADEG + ADEH + ADFG + ADFH + BCEG + B
+CEH + BCFG + BCFH + BDEG + BDEH + BDFG + BDFH>
N=5: <ACEGI + ACEGJ + ACEHI + ACEHJ + ACFGI + ACFGJ + ACFHI + ACFHJ +
+ADEGI + ADEGJ + ADEHI + ADEHJ + ADFGI + ADFGJ + ADFHI + ADFHJ + BCEGI
+ + BCEGJ + BCEHI + BCEHJ + BCFGI + BCFGJ + BCFHI + BCFHJ + BDEGI + BD
+EGJ + BDEHI + BDEHJ + BDFGI + BDFGJ + BDFHI + BDFHJ>
QM

Quantum Mechanics: The dreams stuff is made of
 [reply] [d/l] 

hmm.. that seems pretty clear to me : here
The problem arises in something we're looking at involving quantum ent
+anglement  each of the a[i][0] + a[i][1] terms (i=0, 1, 2, ..., N1)
+ represents a twolevel quantum state. N such terms multiplied togeth
+er thus represents a product state of N twolevel states. We're then
+seeing if a general state can be written in this form  if it cannot,
+ then the degree to which it can't is a measure of the degree of enta
+nglement.
 [reply] [d/l] 
Re: Obtaining terms in an expansion
by DungeonKeeper (Novice) on Jan 06, 2006 at 08:42 UTC

 [reply] 

Actually 2**N is the number of subsets of a set of cardinality N, while the number of permutations of a set of N distinct elements is N! (facultyfactorial).
ivancho used the subset theme quite succesfully in this node above.
 [reply] 

 [reply] 



Re: Obtaining terms in an expansion
by choedebeck (Beadle) on Jan 05, 2006 at 21:24 UTC

Could you elaborate on why you need to do this? It sounds an awful lot like homework to me.  [reply] 

It's not a homework problem, although I can see how it
might look like one. The problem arises in something
we're looking at involving quantum entanglement  each of
the a[i][0] +
a[i][1] terms
(i=0, 1, 2, ..., N1)
represents a twolevel quantum state.
N such terms multiplied together thus represents
a product state of N twolevel states. We're
then seeing if a general state can be written in this
form  if it cannot, then the degree to which it can't is
a measure of the degree of entanglement.
 [reply] 

my $prod = 1; # multiplicative identity, of course
for ( @a )
{
my($x,$y) = @$_;
$prod *= $x + $y;
}
That does what you describe, but it's not 2^N. Not sure where the discrepancy lies...
We're building the house of the future together.
 [reply] [d/l] 

Who cares if it's homework? He's provided a clear and concise explanation of his problem, he provided the code he's tried so far, what more do you want? Does it really matter for which purpose the ultimate solution will be applied?
 [reply] 

