# Merging the knots vector to get the common knots vector

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:

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,

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.

• Isn't there already an algorithm for this in Piegl/Tiller? Jul 29, 2016 at 12:51
• 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. Jul 29, 2016 at 22:24
• Why goodbye ShutaoTang?
– Kuba
Nov 9, 2016 at 14:20

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.

• @ShutaoTang I must say I find them useful :)
– Kuba
Jul 29, 2016 at 14:04