9
$\begingroup$

I have this list:

 ss = {E^(-3 I k x - 3 I t ω), E^(-3 k x - 3 I t ω), E^(
 3 I k x + 3 I t ω), E^(3 k x + 3 I t ω), 
 E^((-1 + 2 I) k x - 3 I t ω), E^(3 I k x - 3 I t ω), 
 E^(-I k x - 3 I t ω), E^(-k x - 3 I t ω), E^(
  I k x - 3 I t ω), E^((1 + 2 I) k x - 3 I t ω), 
  E^((2 - I) k x - 3 I t ω), E^(k x - 3 I t ω), 
  E^((2 + I) k x - 3 I t ω), E^(3 k x - 3 I t ω), E^(
  3 I k x - I t ω), E^(3 I k x + I t ω), E^(
  3 k x - I t ω), E^(3 k x + I t ω), 
  E^(-3 I k x - I t ω), E^((2 - I) k x - I t ω), 
  E^(-3 I k x + I t ω), E^((1 - 2 I) k x + I t ω), 
  E^((1 - 2 I) k x + 3 I t ω), E^(-3 I k x + 3 I t ω), 
  E^(-3 k x - I t ω), E^(-I k x - I t ω), 
  E^(-k x - I t ω), E^(I k x - I t ω), E^(
  k x - I t ω), E^(I k x + I t ω), E^(
   k x + I t ω), E^(I k x + 3 I t ω), E^(
   k x + 3 I t ω), E^((-1 - 2 I) k x + I t ω), 
   E^(-I k x + 3 I t ω), E^((-1 - 2 I) k x + 3 I t ω), 
   E^(-I k x + I t ω), E^(-3 k x + I t ω), 
   E^((-2 + I) k x + I t ω), E^(-k x + I t ω), 
   E^((-2 + I) k x + 3 I t ω), E^(-k x + 3 I t ω), 
    E^((-2 - I) k x + 3 I t ω), E^(-3 k x + 3 I t ω)};

This list has 44 elements. In fact, it has 22 pairs of functions and their conjugates, for example E^(-3 I k x - 3 I t ω) and E^(3 I k x + 3 I t ω). What I need is just to select the functions without the conjugates, so my list is shrunk to a size of 22. I have so many similar lists and want this to be automatic.

$\endgroup$
1
  • $\begingroup$ The code that I gave does not remove actual duplicates with non zero imaginary parts, for example DeleteDuplicates[{1 + I, 1 + I}, #1 == ReplaceAll[#2, Complex[x1_, x2_] -> Complex[x1, -x2]] &] has the output {1 + I, 1 + I}. This is in principle what was asked (you asked to remove conjugates not all duplicates) but it might be unexpected. You could include another DeleteDuplicates to remove all duplicates or use the code by @user293787. $\endgroup$ Commented Oct 2, 2022 at 17:39

5 Answers 5

7
$\begingroup$

Motivation and explanation (code section below)

( This section can be skipped )

The desired output can be achieved with ComplexExpand but that function can be a bit heavy as it transforms Exp into Cos and Sin which is unnecessary for this task. Moreover, Conjugate assumes every variable is potentially complex so it does not help without including assumptions on the variables. Another option is to make an easy home-cooked conjugation for the problem at hand. Let's see how.

E^((1 - 2 I) k x + 3 I t \[Omega]) // FullForm

out: (* Power[E,Plus[Times[Complex[1,-2],k,x],Times[Complex[0,3],t,\[Omega]]]] *)

Manually changing all the I's to -I we have:

E^((1 + 2 I) k x - 3 I t \[Omega]) // FullForm

out: (* Power[E,Plus[Times[Complex[1,2],k,x],Times[Complex[0,-3],t,\[Omega]]]] *)

The change is that Complex[1,-2] became Complex[1,2] and Complex[0,3] became Complex[0,-3], this is the home-cooked conjugation that we will use.


The code :

ssr = DeleteDuplicates[ss,
      #1 == ReplaceAll[#2, Complex[r1_, r2_] -> Complex[r1, -r2]] &]

Note: this code does not remove actual duplicates with non zero imaginary parts for example DeleteDuplicates[{1 + I, 1 + I}, #1 == ReplaceAll[#2, Complex[x1_, x2_] -> Complex[x1, -x2]] &] has the output {1 + I, 1 + I}. This is in principle what was asked but it might be unexpected.

We can check that ssr has the same output as the method using ComplexExpand in the answer provided by @MarcoB:

ssr == DeleteDuplicates[ss,
       ComplexExpand@Conjugate@#1 == ComplexExpand@#2 &]

out: (* True *)

The timing is different (I used AbsoluteTiming):

Using ComplexExpand : 0.44 s

Custom conjugate with ReplaceAll : 0.0054 s


Note: Not every function has a conjugate in the list given. This can be checked with the code below:

Complement[ss, ReplaceAll[ss, Complex[r1_, r2_] -> Complex[r1, -r2]]]

( Explanation of the code above if needed (an example might be easier to understand than what I wrote): there are two types of elements in the list ss, those that have a conjugate and those that don't. For those that do, the action of conjugation swaps the elements with their conjugates but no new elements are created. For the elements that do not have a conjugate, conjugations creates new elements. Complement above asks for the elements in the original ss that do not exist in the conjugated list. Such elements in the original ss can not have a conjugate as conjugation would swap but not create new distinct elements. Hence they are the ones with no conjugate. )

There are 8 terms that do not have a conjugate. Hence, as the original list has 44 elements, the list that we obtain after removing conjugates has (44-8)/2+8=26 elements.


Time complexity of DeleteDuplicates and DeleteDuplicatesBy

I was unaware that DeleteDuplicatesBy is a lot faster than DeleteDuplicates when a test function is included. @user293787 pointed this out in the comments under the answer given there. I was authorized to include this information in my answer (although any mistakes below are my own).

Specifically, @user293787 pointed out that when a generic test function is used, when the number of duplicates scales with the size of the list and seemingly (at least from my personal tests although this is still unclear to me) when the number of possible pairwise comparisons also scales with the size of the list (unlike duplicates modulo 2 for example), then DeleteDuplicates does a naive comparison of all possible pairs which, if the length of the list is $n$, that number of comparisons scales like $n^2$. DeleteDuplicatesBy essentially Maps a function to each list and then applies the usual algorithm for DeleteDuplicates when no test function is specified. As @user293787 pointed out, when no test function is used, DeleteDuplicates can use Sort (maybe Ordering is easier to reproduce DeleteDuplicates, not sure). Fast sorting algorithms have a time complexity of $n\log(n)$ on average and $n$ in the best case, see this Wikipedia page or this geeksforgeeks page.

To show this I will compare the method proposed by @user293787 in the comments with the method above that uses DeleteDuplicates . I will use a similar test list as the one used by OP.

Note!: The code by @user293787 deletes both conjugates and duplicates. This might or might not be desired. To compare the two methods I also included an extra DeleteDuplicates in the method above as it does not delete duplicates with a non zero imaginary part (OP did not request that all duplicates should be removed just the conjugates)

Table[ss = 
  Exp[a*RandomChoice[Range[-2, 2], i] + 
    I*b*RandomChoice[Range[-2, 2], i]];
 
 s1 = 
  AbsoluteTiming[
   DeleteDuplicates@
    DeleteDuplicates[
     ss, #1 == 
       ReplaceAll[#2, Complex[x1_, x2_] -> Complex[x1, -x2]] &]];
 
 s2 = AbsoluteTiming[DeleteDuplicatesBy[ss, ccpair]];
 
 If[s1[[2]] != s2[[2]], Abort[]];
 
 {{i, s1[[1]]}, {i, s2[[1]]}}, {i, 10, 1000, 100}] // 
OperatorApplied[Table][10] // Mean // Transpose // 
ListPlot[#, 
PlotLegends -> {"DeleteDuplicates", "DeleteDuplicatesBy"}, 
AxesLabel -> {"list length", "time (s)"}] &

output:

comparison

To conclude, for small list lengths, the choice depends on the preferred syntax. For larger list lengths where no duplicates are desired, it might be better to use the DeleteDuplicatesBy method given in the comments by @user293787 (after writing that number sequence so much I ended up remembering it so well that I could almost forget my own passwords)

$\endgroup$
7
  • $\begingroup$ Thanks for your answer. However, I don't know why your last command for checking the existence of conjugates fails to show that E^((2 - I) k x - I t [Omega]), E^((-2 + I) k x + I t [Omega]) are conjugates. $\endgroup$
    – qahtah
    Commented Oct 2, 2022 at 12:07
  • $\begingroup$ @qahtah Hi, the last command does not fail as the two quantities you mentioned are not conjugates. k x is real, changing 2 k x to -2 k x is not a conjugation. $\endgroup$ Commented Oct 2, 2022 at 13:31
  • $\begingroup$ @qahtah see user293787's answer for an even faster way. That said, sometimes readability (for others reading your code and for yourself in the future when you have to read it again) should be considered more than speed if the code is fast enough that computer time is not much of an issue. $\endgroup$ Commented Oct 2, 2022 at 15:18
  • $\begingroup$ @qahtah also to be on the safe side, including ExpandAll on both sides of the equality could be good. That said, if the the list was generated algorithmically, a priori, an element and its conjugate would be factorized the same way. To see why compare: DeleteDuplicates[{2*r + 2*I, 2 (I + r)}] with DeleteDuplicates[{2*r + 2*I, 2 (I + r)}, ExpandAll[#1] == ExpandAll[#2] &] $\endgroup$ Commented Oct 2, 2022 at 15:31
  • 1
    $\begingroup$ If you click on "Show activity on this post" and then "Show vote summaries", it lists a total of 4 up (one of which from me) and 0 down. This probably does not exclude that somebody gave you an upvote and then removed it again, I do not know. I would not worry about it. $\endgroup$
    – user293787
    Commented Oct 2, 2022 at 16:33
7
$\begingroup$
DeleteDuplicates[ss, ComplexExpand@ Conjugate@ #1 == ComplexExpand@ #2 &]

(* Out, 26 elements:
{E^(-3 I k x - 3 I t ω), E^(-3 k x - 3 I t ω), 
 E^(3 k x + 3 I t ω), E^((-1 + 2 I) k x - 3 I t ω),
 E^(3 I k x - 3 I t ω), E^(-I k x - 3 I t ω), 
 E^(-k x - 3 I t ω), E^(I k x - 3 I t ω), 
 E^((1 + 2 I) k x - 3 I t ω), E^((2 - I) k x - 3 I t ω), 
 E^(k x - 3 I t ω), E^((2 + I) k x - 3 I t ω), 
 E^(3 I k x - I t ω), E^(3 I k x + I t ω), 
 E^(3 k x - I t ω), E^((2 - I) k x - I t ω), 
 E^((1 - 2 I) k x + I t ω), E^(-3 k x - I t ω),
 E^(-I k x - I t ω), E^(-k x - I t ω),
 E^(I k x - I t ω), E^(k x - I t ω),
 E^((-1 - 2 I) k x + I t ω), E^((-2 + I) k x + I t ω),
 E^((-2 + I) k x + 3 I t ω), E^((-2 - I) k x + 3 I t ω)}
*)
$\endgroup$
4
$\begingroup$

This function generates a pair of a complex number and its complex conjugate:

ccpair[z_]:=Sort[ExpandAll[ComplexExpand[{z,Conjugate[z]}]]];

(* example *)
ccpair[x+I*y]

(* {x-I y,x+I y} *)

One can then use

DeleteDuplicatesBy[ss,ccpair]

(* {E^(-3 I k x-3 I t ω),E^(-3 k x-3 I t ω),E^(3 k x+3 I t ω),
    E^((-1+2 I) k x-3 I t ω),E^(3 I k x-3 I t ω),E^(-I k x-3 I t ω),
    E^(-k x-3 I t ω),E^(I k x-3 I t ω),E^((1+2 I) k x-3 I t ω),
    E^((2-I) k x-3 I t ω),E^(k x-3 I t ω),E^((2+I) k x-3 I t ω),
    E^(3 I k x-I t ω),E^(3 I k x+I t ω),E^(3 k x-I t ω),
    E^((2-I) k x-I t ω),E^((1-2 I) k x+I t ω),E^(-3 k x-I t ω),
    E^(-I k x-I t ω),E^(-k x-I t ω),E^(I k x-I t ω),E^(k x-I t ω),
    E^((-1-2 I) k x+I t ω),E^((-2+I) k x+I t ω),E^((-2+I) k x+3 I t ω),
    E^((-2-I) k x+3 I t ω)} *)

Notes.

  • Since ccpair is only applied once to each entry, this will scale pretty well to larger lists, with essentially linear time complexity.
  • The ExpandAll above is intended to put the expressions into some sort of normal form. If expressions are always Exp of some polynomial, then I would probably first take the Log, apply the DeleteDuplicatesBy operation to polynomials, then apply Exp again:
  Exp[DeleteDuplicatesBy[ss/.E^p_:>p,ccpair]]
  (* same result as above but faster *)
$\endgroup$
13
  • 2
    $\begingroup$ Using the idea in the answer by @userrandrand, an alternative definition of ccpair would be ccpair[z_]:=Sort[ExpandAll[{z,z/.Complex[u_,v_]:>Complex[u,-v]}]]. If OP has very long lists (say several hundred entries) and speed is a concern, then I think the fastest solution so far is this answer here using DeleteDuplicatesBy (not DeleteDuplicates) together with the new version of ccpair in this comment. $\endgroup$
    – user293787
    Commented Oct 2, 2022 at 6:50
  • 1
    $\begingroup$ If list has length $n$ and one uses DeleteDuplicates[list,test] then I expect test will be invoked $\mathcal{O}(n^2)$ many times, if it compares each element with each, which is the best it can do if no axiomatic assumptions are made about test. (Fewer are needed for SameQ because one can sort. This explains why DeleteDuplicates[list,SameQ] is much faster than DeleteDuplicates[list,SameQ[##]&].) If one uses DeleteDuplicatesBy[list,f] then f will only be invoked $\mathcal{O}(n)$ many times, after that it will essentially run a DeleteDuplicates[...,SameQ] which is fast. $\endgroup$
    – user293787
    Commented Oct 2, 2022 at 14:23
  • 1
    $\begingroup$ Thank you, that makes sense, I did not consider that DeleteDuplicates might use nlog[n] sorting algorithms whereas DeleteDuplicates[list,test] might do a naive n^2 computation testing all pairs. I compared SameQ with SameQ[##]& on the test list below. I did not see n^2 scaling for SameQ[##]& but it was clearly slower. The code I used: test = SameQ[##] &; Mean[Table[ Table[AbsoluteTiming[ DeleteDuplicates[RandomChoice[Range[4], i], test]] // First, {i, 1, 10^4, 10^2}], 10]] // ListPlot $\endgroup$ Commented Oct 2, 2022 at 15:09
  • 2
    $\begingroup$ Feel free to include in your post whatever you find interesting and relevant. $\endgroup$
    – user293787
    Commented Oct 2, 2022 at 17:10
  • 1
    $\begingroup$ @E.Chan-López around 0.02 seconds. DeleteDuplicatesBy[ss, ComplexExpand[Re[#]] &] has a similar timing $\endgroup$ Commented Oct 2, 2022 at 20:37
2
$\begingroup$

Using GroupBy:

Normal[GroupBy[ss, ComplexExpand[#*ComplexExpand[Conjugate[#]]] &]][[All, 2]][[All, 1]]

enter image description here

Using GatherBy:

GatherBy[ss, ComplexExpand[#*ComplexExpand[Conjugate[#]]] &][[All, 1]]

enter image description here

Sorting with the real part and using GatherBy is much faster than the previous sort:

GatherBy[ss, ComplexExpand[Re[#]] &][[All, 1]]
(*{0.060014, {E^(-3 I k x - 3 I t ω), E^(-3 k x - 3 I t ω),
E^(3 k x + 3 I t ω), E^((-1 + 2 I) k x - 3 I t ω), 
E^(3 I k x - 3 I t ω), E^(-I k x - 3 I t ω), 
E^(-k x - 3 I t ω), E^(I k x - 3 I t ω), 
E^((1 + 2 I) k x - 3 I t ω), E^((2 - I) k x - 3 I t ω), 
E^(k x - 3 I t ω), E^((2 + I) k x - 3 I t ω), 
E^(3 I k x - I t ω), E^(3 I k x + I t ω), 
E^(3 k x - I t ω), E^((2 - I) k x - I t ω), 
E^((1 - 2 I) k x + I t ω), E^(-3 k x - I t ω), 
E^(-I k x - I t ω), E^(-k x - I t ω), 
E^(I k x - I t ω), E^(k x - I t ω), 
E^((-1 - 2 I) k x + I t ω), E^((-2 + I) k x + I t ω),
E^((-2 + I) k x + 3 I t ω), E^((-2 - I) k x + 3 I t ω)}}*)
$\endgroup$
1
$\begingroup$

A hash-free variant of E. Chan-López answer

GatherBy[Re /@ ss, ComplexExpand][[All, 1, 1]]

{E^(-3 I k x - 3 I t ω), E^(-3 k x - 3 I t ω), E^(3 k x + 3 I t ω), E^((-1 + 2 I) k x - 3 I t ω), E^(3 I k x - 3 I t ω), E^(-I k x - 3 I t ω), E^(-k x - 3 I t ω), E^(I k x - 3 I t ω), E^((1 + 2 I) k x - 3 I t ω), E^((2 - I) k x - 3 I t ω), E^(k x - 3 I t ω), E^((2 + I) k x - 3 I t ω), E^(3 I k x - I t ω), E^(3 I k x + I t ω), E^(3 k x - I t ω), E^((2 - I) k x - I t ω), E^((1 - 2 I) k x + I t ω), E^(-3 k x - I t ω), E^(-I k x - I t ω), E^(-k x - I t ω), E^(I k x - I t ω), E^(k x - I t ω), E^((-1 - 2 I) k x + I t ω), E^((-2 + I) k x + I t ω), E^((-2 + I) k x + 3 I t ω), E^((-2 - I) k x + 3 I t ω)}}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.