Re: Re[2]: Minimal number of transformations
- To: mathgroup at smc.vnet.net
- Subject: [mg103221] Re: Re[2]: [mg103144] Minimal number of transformations
- From: Leonid Shifrin <lshifr at gmail.com>
- Date: Thu, 10 Sep 2009 07:34:14 -0400 (EDT)
- References: <200909090843.EAA05869@smc.vnet.net>
Hi Maxim,
In this case, I think you should be even more specific. I can see
two types of transformations: to move an element from one sublist to
another one, and to move some element within the same sublist. Are both
of these counted? For example
{{a,b},{c,d}}-> {{a,c,b},{d}} should then be what - 2? (one step to move
c to the first sublist, then another one to move c within the first
sublist). Also, you should specify the rules - how elements are moved
from one sublist to another - for example they are always appended in
front of a sublist.
Also, for moving elements within a sublist: you say that {a,b,c}->{b,c,a}
is one transformation. I can see two transpositions a<->b and then
a<->c, or a single syclic shift. You must provide a fixed notion of
transformation here, for example a single two-element transposition
of adjacent (or not necessarily adjacent) elements. If you count
transposition of any two elements (not necessarily adjacent) as a single
transformation, then indeed {a,b,c}->{b,c,a} is one. But you have to
state all these rules, otherwise the problem is IMO not well defined.
Regards,
Leonid
On Thu, Sep 10, 2009 at 1:45 PM, Maxim Volkov <musimba at gmail.com> wrote:
> 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
> 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>
- Minimal number of transformations