4
$\begingroup$

Given that I have the following knots vector U1, U2, U3

U1 = {0.25, 0.25, 0.5, 0.5, 0.75, 0.75, 0.8};
U2 = {0.21, 0.25, 0.3, 0.6, 0.7, 0.8};
U3 = {0.25, 0.3, 0.7, 0.8};

Now I would like to calculate their common knots vector , i.e., a knots vector that contains all of the elements of U1, U2, U3 and has the least length. For example, containing all of the elements of U1 means containing {0.25, 0.25, 0.5, 0.5, 0.75, 0.75, 0.8}, rather than {0.25, 0.5, 0.75, 0.8}.

Then with the help of common knots vector, I want to compute the complementary elements of each knots vector. For this case, the common knots vector is:

commonKnotsVector = {0.21, 0.25, 0.25, 0.3, 0.5, 0.5, 0.6, 0.7, 0.75, 0.75, 0.8}

and the corresponding complementary elements are

(*
 U1 --> {0.21, 0.3, 0.6, 0.7}
 U2 --> {0.25, 0.5, 0.5, 0.75, 0.75}
 U3 --> {0.21, 0.25, 0.5, 0.5, 0.6, 0.75, 0.75}
*)

For the common knots vector, my algorithm as shown below:

enter image description here

commonKnotsVector[knots_] :=
  Module[{step1, step2, step3, step4},
   step1 = SortBy[Join @@ Tally /@ knots, First];
   step2 = GatherBy[step1, First];
   step3 = Last /@ (SortBy[#, Last] & /@ step2);
   step4 = step3 /. {x_, n_} :> ConstantArray[x, n];
   Flatten[step4]
]

commonKnotsVector[{u1, u2, u3}]
(*{0.21, 0.25, 0.25, 0.3, 0.5, 0.5, 0.6, 0.7, 0.75, 0.75, 0.8}*)

For the complementary elements,

enter image description here

knotsVectorMinus[commonKnotsVector_, knots_] := 
  Module[{step1, step2},
   step1 = GatherBy[Join[Tally@commonKnotsVector, Tally[knots]], First];
   step2 = step1 /. {{{x_, n1_}, {x_, n2_}} :>{x, Abs[n1 - n2]},
                     {{x_, n1_}} :> {x, n1}};
   Flatten[step2 /. {x_, n_} :> ConstantArray[x, n]]
 ]

knotsVectorMinus[commonKnotsVector, #] & /@ {u1, u2, u3}
(*{{0.21, 0.3, 0.6, 0.7}, 
  {0.25, 0.5, 0.5, 0.75, 0.75}, 
  {0.21, 0.25, 0.5, 0.5, 0.6, 0.75, 0.75}}*)

I think my method is not the best/efficient, so I asked this question to seek other elegnant/effective solution.

$\endgroup$
  • $\begingroup$ Isn't there already an algorithm for this in Piegl/Tiller? $\endgroup$ – J. M. will be back soon Jul 29 '16 at 12:51
  • $\begingroup$ The second operation is equivalent to (18100). I am now trying to see if I can use that to craft a method that is over-all faster than Kuba's code. $\endgroup$ – Mr.Wizard Jul 29 '16 at 22:24
  • $\begingroup$ Why goodbye ShutaoTang? $\endgroup$ – Kuba Nov 9 '16 at 14:20
5
+200
$\begingroup$

If order does not matter and it is not meant to be C fast:

reCounts = Catenate @* KeyValueMap[ConstantArray];

c = Counts /@ {U1, U2, U3};
m = Merge[c, Max];
commKV = reCounts @ m
{0.25, 0.25, 0.5, 0.5, 0.75, 0.75, 0.8, 0.21, 0.3, 0.6, 0.7}
compEl = reCounts@Merge[KeyUnion[{m, #}, 0 &], Apply[Subtract]] & /@ c
{{0.21, 0.3, 0.6, 0.7}, 
 {0.25, 0.5, 0.5, 0.75, 0.75}, 
 {0.25, 0.5, 0.5, 0.75, 0.75, 0.21, 0.6}
}

Depending of application, this may be useful:

Merge[KeyUnion[Counts /@ {U1, U2, U3}, 0 &], {Max[#], Max[#] - #} &]
<|0.25 -> {2, {0, 1, 1}}, 
  0.5 -> {2, {0, 2, 2}}, 
  ... 
  value -> {counts in commonKV, {counts in specific compV}}
 |>

in one line you have all information, now the question is what do you want to do with this.

$\endgroup$
  • 3
    $\begingroup$ @ShutaoTang I must say I find them useful :) $\endgroup$ – Kuba Jul 29 '16 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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