Re[2]: Minimal number of transformations
- To: mathgroup at smc.vnet.net
- Subject: [mg103216] Re[2]: [mg103144] Minimal number of transformations
- From: Maxim Volkov <musimba at gmail.com>
- Date: Thu, 10 Sep 2009 07:25:00 -0400 (EDT)
- References: <200909090843.EAA05869@smc.vnet.net> <34c814850909091040x194eaa68ld60f646d3ee5cb53@mail.gmail.com>
- Reply-to: Maxim Volkov <Musimba at gmail.com>
Hi Leonid,
Thanks for the answer. But I think I haven't made myself clear. Not
only the order of sublists is important, but so is the order of
elements in the sublists.
ex.: {{a, b, c}} != {{b, c, a}}
So the most difficult part here is to find minimal number of inner
list transformations. In case of the above example it is one
transformation:
a is moved from the first position to the last.
> Hi Maxim,
> assuming that the order of sublists matters ( that is, that lists
> {{1,2},{3,4}} and {{3,4},{1,2}} are
> considered different), that the order of elements inside sublists
> does not matter (that is, {{1,2},{3,4}} and {{2,1},{4,3}} are
> considered the same), and that both lists contain the same set of
> distinct elements, we just need to count the number of elements that
> must be taken from one of the sublists and
> placed to some other one. The following code will hopefully do this:
> ClearAll[transformDistance, listOfDistinctQ, sublist, transforms];
> Protect[sublist];
> listOfDistinctQ[x : {{__} ..}] :=
> Length[Flatten[x]] == Length[Union[Flatten[x]]];
> listOfDistinctQ[___] := False;
> transforms[start_?listOfDistinctQ, end_?listOfDistinctQ] /;
> Length[start] == Length[end] &&
> Union[Flatten[start]] === Union[Flatten[end]] :=
> Rule @@@ DeleteCases[
> SplitBy[
> #[[Ordering[#[[All, 1]]]]] &@
> Flatten[
> Map[MapIndexed[Thread[{#1, sublist @@ #2}] &, #] &,
> {start, end}],
> 2],
> First], {x_, x_}];
> transformDistance[start_, end_] := Length[transforms[start, end]];
> The function <transforms> returns a list of transformation steps that lea=
d from start list to
> end list. The function transformDistance gives the number of transforms,=
which is just the
> length of the list of rules returned by <transforms>. The head <sublist> =
is introduced simply
> for better visualization.
>
> Examples:
> In[1] =
> ClearAll[a,b,c,d,e,f,];
> In[2] =
> transforms[{{a, b, c}, {d, e, f}}, {{a, b, c, d}, {e, f}}]
> Out[2] = {{d, sublist[2]} -> {d, sublist[1]}}
> In[3] = transforms[{{a, b}, {c, d}, {e, f}}, {{c, b, a}, {e}, {d, f}}]
> Out[3] = {{c, sublist[2]} -> {c, sublist[1]}, {d, sublist[2]} -> {d,
> sublist[3]}, {e, sublist[3]} -> {e, sublist[2]}}
> In[4] = transforms[{{a, b}, {c, d}, {e, f}}, {{c, d}, {e, f}, {a, b}}]
> Out[4] = {{a, sublist[1]} -> {a, sublist[3]}, {b, sublist[1]} -> {b,
> sublist[3]}, {c, sublist[2]} -> {c, sublist[1]}, {d,
> sublist[2]} -> {d, sublist[1]}, {e, sublist[3]} -> {e,
> sublist[2]}, {f, sublist[3]} -> {f, sublist[2]}}
> Hope this helps.
> Regards,
> Leonid
> On Wed, Sep 9, 2009 at 12:43 PM, Maxim <musimba at gmail.com> wrote:
> Hello everyone,
> Is there any Mathematica function that can calculate the minimal
> number of transofrmations needed to go from one list to another.
> For instance:
> To go from
> before = { {1, 2, 3}, {4, 5, 6} }
> to
> after = { {6, 1, 2, 3}, {4, 5} }
> one transformation is needed: moving of the number 6 from second inner
> list to the first.
> The lists have some specific properties:
> 1. List Depth is always 3
> 2. Numbers in the lists are always unique and are sequential numbers:
> 1, 2, 3, ...
> 3. Flatten[Length[before]] == Flatten[Length[after]], which means
> numbers are never removed or added from/to the list.
> This is somewhat similat to EditDistance, except that it should work
> on list of lists and it should be able to count element moves, rather
> than substitutions.
> Thanks!
- References:
- Minimal number of transformations
- From: Maxim <musimba@gmail.com>
- Minimal number of transformations