Message Boards Message Boards

0
|
7613 Views
|
6 Replies
|
1 Total Likes
View groups...
Share
Share this post:
GROUPS:

How do I Split this?

I have different lists which, once joined and sorted, I'd like to split whenever an element from one of the lists appears again. For example:

r = {1, 3, 8}

s = {2, 7}

t = {0, 4, 5, 9}

Joined and sorted: {0, 1, 2, 3, 4, 5, 7, 8, 9}

The output I'm looking for is: {{0, 1, 2}, {3, 4}, {5, 7, 8}, {9}}

How can I do it?

POSTED BY: Fernando Benadon
6 Replies
Posted 9 years ago

As a gentle reminder, an answer to this question was also provided by Sean Clarke here. In case you are looking for a function that does not ask for preprocessing, here is a possible approach:

mySplit[list__?VectorQ] := Block[
  {llist = {list}, templist = Sort@Join@list, range, indexedlist, indices, sortby, endpos},

  range = Range[Length@llist];
  indexedlist = Sort[(Sequence @@ Transpose[{llist[[#]], ConstantArray[#, Length@llist[[#]]]}]) & /@ range]; 
  indices = indexedlist[[All, 2]];

  sortby[{}] = {};
  sortby[l_] := Block[{temprange = range, ctr = 1},
    While[ctr <= Length@l && MemberQ[temprange, l[[ctr]]], temprange[[l[[ctr++]]]] = 0];
    {--ctr, Sequence @@ sortby[Drop[l, ctr]]}];

  endpos = Accumulate@sortby[indices];
  MapThread[templist[[#1 ;; #2]] &, {Prepend[Most@endpos, 0] + 1, endpos}]
  ];

For your inputs

p = {1, 3, 8} ; q = {2, 7} ; r = {0, 4, 5, 9} ;

we get

mySplit[p, q, r]
(* {{0, 1, 2}, {3, 4}, {5, 7, 8}, {9}} *)

This function should work for any number of lists, without any particuliar condition regarding their elements (e.g., a given number can appear several times in a same list and be in other lists as well). Note that the output depends on the order according to which the arguments are given, because of the way Join and Sort work together. For instance considering the lists

a = {0, 5, 3} ; b = {2, 1} ; c = {3, 4, 5, 0, 0, 0} ;

we obtain

mySplit[a, b, c]
(* {{0, 0}, {0}, {0, 1}, {2, 3, 3}, {4, 5}, {5}} *)

mySplit[b, c, a]
(* {{0}, {0}, {0, 0, 1}, {2, 3, 3}, {4}, {5, 5}} *)
POSTED BY: Xavier Roy

Well done, Xavier and Sean.

without any particuliar condition regarding their elements

not literally

 In[4]:= mySplit[{}, {}, {}, {}]
    <snip>
 Out[4]= MapThread[templist[[#1 ;; #2]] &, {1 + Most[0, {}], {}}]

but this is trivial to fix.

Finally, both methods give

In[13]:= mySplit[{1}, {1, 2}, {2}]
Out[13]= {{1, 1}, {2, 2}}

In[15]:= benadonSort[{1}, {1, 2}, {2}]
Out[15]= {{1, 1}, {2, 2}}

the problem owner must decide whether that is correct, possibly he expects

{{1, 1, 2 (* from third list *)}, {2 (* from second list *)}}

as solution (take values from as much as many lists possible before opening a new group). With other words, not only the sequence of lists, but also the sorting of values with respect to the list index matters. It is of course undefined under operations like

SortBy[..., First]
POSTED BY: Udo Krause
Posted 9 years ago

@Udo, Thanks for pointing out the issue. This can be fixed for instance by adding

If[templist === {}, Return["Expecting at least one non-empty list."]];

rigth after the local declarations of Block. I agree about your other point, perhaps the question owner can specify its expectations for such cases.

POSTED BY: Xavier Roy

One needs a function to check whether a list number is repeating, this function is benadonC :

 In[146]:= Clear[r, s, t, cache, benadonC, pred]
           r = {1, 3, 8};
           s = {2, 7};
            t = {0, 4, 5, 9};
            benadonC[l_List, o_Integer] := If[(* Print["elem = ",l]; *)pred == l,
                  0,(* else *)
                  pred = l;
                  If[(* Print["cache: ", cache,"| o = ",o]; *)
                   IntersectingQ[cache, {o}],
                   cache = {};
                   pred = {\[Infinity], \[Infinity]};
                   1, (* else *)
                   cache = Flatten[{cache, {o}}];
                   0
                   ]
                  ]

it uses two global variables, cache and pred and then it's as easy as

 In[151]:= cache = {}; pred = {\[Infinity], \[Infinity]};
    First /@ (Transpose /@ SplitBy[SortBy[
     Join[Transpose[{r, ConstantArray[1, Length[r]]}],
          Transpose[{s, ConstantArray[2, Length[s]]}],
          Transpose[{t, ConstantArray[3, Length[t]]}]], First], 
        benadonC[#, Last[#]] &])

 Out[152]= {{0, 1, 2}, {3, 4}, {5, 7, 8}, {9}}

uncomment the print statements to see how SplitBy visits the elements.

By the way, benadonC has an error if one of the lists contains repeated elements:

Set

r = {1, 3, 8, 3};

to get

In[18]:= cache = {}; pred = {\[Infinity], \[Infinity]};
First /@ (Transpose /@ 
   SplitBy[SortBy[Join[Transpose[{r, ConstantArray[1, Length[r]]}],
      Transpose[{s, ConstantArray[2, Length[s]]}],
      Transpose[{t, ConstantArray[3, Length[t]]}]], First], 
    benadonC[#, Last[#]] &])

Out[19]= {{0, 1, 2}, {3, 3, 4}, {5, 7, 8}, {9}}

but the correct result is

 {{0, 1, 2}, {3}, {3, 4}, {5, 7, 8}, {9}}

that flaw comes from the repetition check. Can you fix it?

POSTED BY: Udo Krause

Can you fix it?

Lets fix it with a procedural benadonC

Clear[benadonSort, benadonC]
benadonC[l_List?VectorQ] := Block[{o1 = 1, cache = {}, r = {}},
  For[o = 1, o <= Length[l], o++,
   If[IntersectingQ[cache, {l[[o]]}],
    r = Join[r, {{o1, o - 1}}];
    cache = {l[[o]]};
    o1 = o, (* else *)
    cache = Join[cache, {l[[o]]}]
   ]
  ];
  Join[r, {{o1, Length[l]}}]
]

benadonSort[l1_List?VectorQ, l2_List?VectorQ, l3_List?VectorQ] := 
 Block[{i, v},
   {v, i} = Transpose[
     SortBy[
      Join[
       Transpose[{l1, ConstantArray[1, Length[l1]]}],
       Transpose[{l2, ConstantArray[2, Length[l2]]}],
       Transpose[{l3, ConstantArray[3, Length[l3]]}]
      ], First
     ]
    ];
    Part[v, #]& /@ (Span @@@ benadonC[i])
   ] /; Length[l1] > 0 && Length[l2] > 0 && Length[l3] > 0

and test a bit more than before

In[88]:= benadonSort[r, s, t]
Out[88]= {{0, 1, 2}, {3, 4}, {5, 7, 8}, {9}}

In[89]:= benadonSort[{1, 3, 8, 3}, s, t]
Out[89]= {{0, 1, 2}, {3}, {3, 4}, {5, 7, 8}, {9}}

In[92]:= benadonSort[{1, 3, 8, 3}, Join[s, {7}], t]
Out[92]= {{0, 1, 2}, {3}, {3, 4}, {5, 7}, {7, 8, 9}}

In[93]:= benadonSort[{1, 3, 8, 3}, Join[s, {7, 7}], t]
Out[93]= {{0, 1, 2}, {3}, {3, 4}, {5, 7}, {7}, {7, 8, 9}}

In[90]:= benadonSort[{1, 1, 1, 1}, {2, 2, 2, 2, 2, 2}, {3, 3}]
Out[90]= {{1}, {1}, {1}, {1, 2}, {2}, {2}, {2}, {2}, {2, 3}, {3}}

Jobs for the week-end:

  • enhance benadonSort to run with an arbitrary finite positive number of non-empty lists
  • make benadonC functional
POSTED BY: Udo Krause
Posted 9 years ago
r = {1, 3, 8, 0};
s = {2, 7, 9};
t = {0, 4, 5, 9};
Split[Sort[Join[r, s, t]], ! SameQ[#1, #2] &]

{{0}, {0, 1, 2, 3, 4, 5, 7, 8, 9}, {9}}

POSTED BY: Michael Helmle
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract