 Perl Monk, Perl Meditation PerlMonks

### Obtaining terms in an expansion

by randyk (Parson)
 on Jan 05, 2006 at 21:19 UTC Need Help??

randyk has asked for the wisdom of the Perl Monks concerning the following question:

I have an expansion involving N factors:

```(a + a) (a + a)
(a + a) ... (a[N-1] + a[N-1])
[download]```
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 = 1;
\$C[\$N-1] = 1;
for (\$i=0; \$i<\$N; \$i++) {
\$C *= \$a->[\$i]->;
\$C[\$N-1] *=  \$a->[\$i]->;
}
[download]```
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 + a) * (a + a) =
C + C + C + C,
where
C = a * a
C = a * a
C = a * a
C = a * a
[download]```
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!

Replies are listed 'Best First'.
Re: Obtaining terms in an expansion
by ikegami (Pope) on Jan 05, 2006 at 21:31 UTC

It's not clear to me what you want. Maybe it's something like

```my \$C;

if (@\$ar) {
\$C = 1;
foreach my \$row (@\$arr) {
my \$sum = 0;
foreach my \$ele (@\$row) {
\$sum += \$ele;
}
\$C *= \$sum;
}
}
[download]```

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->};

my \$C;

foreach my \$col_idx (0 .. \$cols-1) {
\$C->[\$col_idx] = 1;
foreach my \$row (@\$arr) {
\$C->[\$col_idx] *= \$row->[\$col_idx];
}
}
[download]```
I should have supplied an example of what I was looking for. For example, for N=2:
```( arr + arr ) ( arr + arr )
[download]```
what I want to find is
```C = arr arr
C = arr arr
C = arr arr
C = arr arr
[download]```
It doesn't matter if the coefficients come out in this order, of course.

If 2^N could become m^n, then you could use a recursive solution: (Updated: cleaned up slightly!)

```#! perl -slw
use strict;

sub expand{
return @{ \$_ } 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
[download]```

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.
I don't see an operator between arr and arr, so I presume the parenthesis mean you want to multiply.

Your description does not adequately explain what you want, particularly the (a[N-1] + a[N-1]).

Indices from your example:

```0,0 1,0
0,0 1,1
0,1 1,0
0,1 1,1
[download]```
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
...
[download]```
The wrong element is incrementing -- a[N-1] * a, a[N-1] * a.

Furthermore, this makes no sense. Are a and a use repeatedly throughout? If so, why not change them into constants?

Celebrate Intellectual Diversity

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 1-dimensional terms (i.e. vectors) you have:
```[a1...an]' * [b1...bn] = [a1*b1 ... a1*bn; ...; an*b1 ... an*bn]
[download]```
which can be written "a_i * b_j" using physicists' tensor notation. For two 2-dimensional 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.
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).
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 N-1
ie, each one looks like, say
a * a * a * a * ... * a[N-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 i-th bit in the binary expansion of \$m
\$C[ \$m ] *= \$arr->[ \$_ ][ \$bits[\$_] ] for 0..\$N-1;
}

print Dumper \@C;
[download]```

note, \$size must be a power of 2, for vec to work, and unless you're on a 64-bit 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.
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 || 5;
my @terms = qw( a a );
foreach my \$i (1 .. \$n-1) {
@terms = map { ("\$_ a[\$i]","\$_ a[\$i]") } @terms;
}
foreach my \$i (0 .. \$#terms) {
print "term[\$i] = \$terms[\$i]\n";
}
[download]```
Update: fixed off-by-one error
You have N terms going in, and N terms coming out. He says in the OP that he wants 2^N expressions returned. This is considered 2 terms, so there are 4 expressions returned.

Update: my mistake. Did not read carefully enough.

That's funny, because when I run the program for N=2, I get:
```term = a a a
term = a a a
term = a a a
term = a a a
term = a a a
term = a a a
term = a a a
term = a a a
[download]```
So perhaps I have an off-by-one error, but certainly I'm generating 2^N terms.
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.

I apologize if the motivation wasn't clear. At a mathematical level, it's a problem of multiplying N polynomials, each of which has two terms:

```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
[download]```
What I was after was an explicit expression for each of the 2**N terms on the right-hand-side 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 N-qubit state.

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**N-1) to contain the variables. Then you would create an array Terms[2**N-1] 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**N-1].

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

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*\$N-1;
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>
[download]```

-QM
--
Quantum Mechanics: The dreams stuff is made of

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] + a[i] terms (i=0, 1, 2, ..., N-1)
+ represents a two-level quantum state. N such terms multiplied togeth
+er thus represents a product state of N two-level 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.
[download]```
Re: Obtaining terms in an expansion
by DungeonKeeper (Novice) on Jan 06, 2006 at 08:42 UTC

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.

In a way you are correct, except that it's "factorial" not "faculty" - I used the word permutations a bit too loosely.

However, the module Math::Combinatorics can still be used to iterate through the 2**N subsets as well as the nCr combinations and the N! permutations.

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.
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] + a[i] terms (i=0, 1, 2, ..., N-1) represents a two-level quantum state. N such terms multiplied together thus represents a product state of N two-level 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.
```my \$prod = 1; # multiplicative identity, of course

for ( @a )
{
my(\$x,\$y) = @\$_;
\$prod *= \$x + \$y;
}
[download]```

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.
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?

Log In?
 Username: Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://521350]
Approved by Old_Gray_Bear
Front-paged by kwaping
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (3)
As of 2021-04-19 06:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?