Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: Minimal number of transformations

• To: mathgroup at smc.vnet.net
• Subject: [mg103190] Re: [mg103144] Minimal number of transformations
• From: Leonid Shifrin <lshifr at gmail.com>
• Date: Thu, 10 Sep 2009 07:20:00 -0400 (EDT)
• References: <200909090843.EAA05869@smc.vnet.net>

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 lead
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>