Obtaining terms in an expansion

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

Replies are listed 'Best First'.
Re: Obtaining terms in an expansion by ikegami (Patriarch) 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->[0]}; my $C; foreach my $col_idx (0 .. $cols-1) { $C->[$col_idx] = 1; foreach my $row (@$arr) { $C->[$col_idx] = $row->[$col_idx]; } }` [download]	[reply] [d/l] [select]
Re^2: Obtaining terms in an expansion by randyk (Parson) on Jan 05, 2006 at 22:03 UTC
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] )` [download] 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]` [download] It doesn't matter if the coefficients come out in this order, of course.	[reply] [d/l] [select]
Re^3: Obtaining terms in an expansion by BrowserUk (Patriarch) on Jan 06, 2006 at 00:26 UTC
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 @{ $_[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 [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.	[reply] [d/l]
Re^3: Obtaining terms in an expansion by InfiniteSilence (Curate) on Jan 05, 2006 at 22:54 UTC
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[N-1][0] + a[N-1][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[0][N-1] * a[1][0], a[0][N-1] * 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 1-dimensional terms (i.e. vectors) you have: `[a1...an]' * [b1...bn] = [a1b1 ... a1bn; ...; anb1 ... anbn]` [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.	[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 N-1 ie, each one looks like, say `a[0][0] * a[1][0] * a[2][1] * a[3][0] * ... * a[N-1][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.	[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 .. $n-1) { @terms = map { ("$_ a[$i][0]","$_ a[$i][1]") } @terms; } foreach my $i (0 .. $#terms) { print "term[$i] = $terms[$i]\n"; }` [download] Update: fixed off-by-one error	[reply] [d/l]
Re^2: Obtaining terms in an expansion by runrig (Abbot) on Jan 05, 2006 at 23:40 UTC
~~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.	[reply]
Re^3: Obtaining terms in an expansion by trammell (Priest) on Jan 06, 2006 at 15:16 UTC
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]` [download] So perhaps I have an off-by-one 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]
Re^2: Obtaining terms in an expansion by randyk (Parson) on Jan 06, 2006 at 02:05 UTC
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.	[reply] [d/l]
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]
Re^2: Obtaining terms in an expansion by ivancho (Hermit) on Jan 06, 2006 at 01:08 UTC
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, ..., 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]	[reply] [d/l]
Re: Obtaining terms in an expansion by DungeonKeeper (Novice) on Jan 06, 2006 at 08:42 UTC
Math::Combinatorics can be used to iterate through the 2**N ~~permutations~~ subsets.	[reply]
Re^2: Obtaining terms in an expansion by pKai (Priest) on Jan 06, 2006 at 12:52 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! (~~faculty~~factorial). ivancho used the subset theme quite succesfully in this node above.	[reply]
Re^3: Obtaining terms in an expansion by DungeonKeeper (Novice) on Jan 06, 2006 at 13:23 UTC
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.	[reply]
Re^4: Obtaining terms in an expansion by pKai (Priest) on Jan 06, 2006 at 19:34 UTC
Re^5: Obtaining terms in an expansion by ivancho (Hermit) on Jan 06, 2006 at 22:19 UTC
Re^5: Obtaining terms in an expansion by DungeonKeeper (Novice) on Jan 09, 2006 at 10:09 UTC
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]
Re^2: Obtaining terms in an expansion by randyk (Parson) on Jan 05, 2006 at 21:44 UTC
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, ..., 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.	[reply]
Re^3: Obtaining terms in an expansion by jdporter (Paladin) on Jan 06, 2006 at 02:08 UTC
`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.	[reply] [d/l]
Re^2: Obtaining terms in an expansion by BUU (Prior) on Jan 05, 2006 at 21:30 UTC
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]


No such thing as a small change
	PerlMonks