Re^2: Obtaining terms in an expansion

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.

Comment on Re^2: Obtaining terms in an expansion Download Code

Replies are listed 'Best First'.
Re^3: Obtaining terms in an expansion by Scott7477 (Chaplain) on Jan 06, 2006 at 06:46 UTC
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 2N variables on the left side, you would want to create an array named, say, `Variable{2N-1)` to contain the variables. Then you would create an array `Terms[2N-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[2N-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	[reply] [d/l] [select]
Re^3: Obtaining terms in an expansion by QM (Parson) on Jan 07, 2006 at 17:10 UTC
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	[reply] [d/l]