# Python recursive bisection algorithm to Mathematica

I've been sitting on this problem for a while and i am kind of stuck. I am pretty new to Mathematica and have been trying to implement a recusive Algorithm, which splits/bisects a list of items in parts recursively. This means, that when the algorithm loops back it should bisect both already bisected parts. The algorithm stops, when there are no elements left to bisect. Regullary I would do after every bisection some calculation which is not important for this question. More importantly is the question how to handle multiple for loops in Mathematica like it is being done in python.

I have an Python-Code which illustrates the algorithm by printing the bisectionsteps. The first picture shows the algorithm without recursion, to illustrate the first iteration. In the second picture I did it with the while loop and print comand so you can see the functionality. As you can see, j iterates the left side, while k iterates through the right side. As I special problem I find to loop through ((0,len(i)//2) which is an array with only two elements and than plugging them in to i[j:k].

Hopefully there is someone who is experienced with both programming languages and can halp me out.

// edit //

Thnak you very much for the help! Since @Rohit Namjoshi asked in the coments for my try and also for some clarification I will post it. I tried the Do-loop to mimic the procedure in Python since I am more used to that logic. Even though the answers are promising they are hard to understand as a beginer, especially building up on the functions is still hard. Maye it could be Done like in Python?! I will show my try for the inner loop whithout recursion.

The python code loops at first through the list. That's why there are two more brackets so that the first loop for i in cItems gives back the list of numbers itself. In the second step the loops j,k loop through an range without such that j gives us start values for the interval for the bisection and k the end Values. For the Python case it would look like this

sortIx=["a","b","c","d","e","f","g","h","i","j"]
cItems=[sortIx]
cItems = [i[j:k] for i in cItems for j, k in ((0, len(i) // 2), (len(i) // 2, len(i))) if len(i) > 1]
print(cItems)


with: j=(0,5), k=(5,10)

As you can see in the python code (sorry for the screenshot @High Performance Mark), i[j:k] such that the first part of the bisection is i[0,5] and the second i[5,10] where i is in the first iteration ["a","b","c","d","e","f","g","h","i","j".

Output: [['a', 'b', 'c', 'd', 'e'], ['f', 'g', 'h', 'i', 'j']]

Now my Do-Loop-Trial. I defined two functions to give me the start values of the interval j,k so i can loop through that range of two values like in python:

startInterval[cItems_] := {1, Ceiling@(Length[cItems]/2) + 1}
endInterval[cItems_] := {Ceiling@(Length[cItems]/2), Length[cItems]}

In[317]:= startInterval[x[[1]]]
endInterval[x[[1]]]

Out[317]= {1, 6}

Out[318]= {5, 10}


My approach with the Do-Loop looks like this:

Do[i[[j ;; k]],
Do[ Items =  x[[i]] , {i, 1, Length[x]},
Do[ (start = Items)[[j]], {j, Length[startInterval[Items]]}],
Do[ (end =  Items)[[k]], {k, Length[endInterval[Items]]}]]]


They give the right output:

Do[  Items = x[[i]]  , {i, 1, Length[x]}]
Items
startInterval[Items]
endInterval[Items]

{3, 1, 6, 2, 5, 10, 7, 4, 9, 8}

{1, 6}

{5, 10}


Does anyone know where the mistake is or can anyone tell me if that try is even possible? I know for most of you it is absurd to use that logic but especially as an beginner it seems easier to me to not loose track. Hopefully I improved my writing and formating. Thank's in advance!

• Welcome to MSE. Please post the WL code that you have tried. Sep 3 '21 at 19:56
• If you intend to become a regular user of the site learn how to post code, not images of code. We can't cut and paste your code from an image; many of us won't try to reproduce your errors (which is often the first step in solving them) if we have to type your code in. Sep 4 '21 at 12:10

Just for fun...I have voted for @MichaelE2 neat answer:

fn[lst_] :=
Module[{s1},
s1 = NestList[
Flatten[Map[TakeDrop[#, Floor[Length[#]/2]] &, #], 1] /. {} ->
Nothing &, {lst}, Floor[Length[lst/2]] - 1];
panelLabel[lbl_] :=
Panel[lbl, FrameMargins -> 0, Background -> Lighter[Yellow, 0.7]];
Flatten[
Outer[If[
SubsetQ[#1, #2] &&
Length[#2] < Length[#1], #1 \[DirectedEdge] #2,
Nothing] &, #1, #2, 1] & @@@ Partition[s1, 2, 1]] //
Graph[#, VertexLabels -> Placed[Automatic, Above, panelLabel]] &]


where: NestList[ Flatten[Map[TakeDrop[#, Floor[Length[#]/2]] &, #], 1] /. {} -> Nothing &, {lst}, Floor[Length[lst/2]] - 1] is the recursion and the rest window dressing.

For example:

• Hey thank you very much for this idea! I was wondering why is it when I just use the recursion part the function doesn not the same like with the "window-dressing-part" ? For example in the graphic the function only bisects if there is something to bisect. When I use just the function it gives me the last values multiple times and it repeats parts . Have I forgotten some additional constraint ?
– Axha
Sep 9 '21 at 19:44
• @Axha MichaelE2 answer (which I voted for), step by step reproduces the output of the python code. NestList accumulates the bisected components. It just bisects and collects. The window dressing establishes the relationships between ‘parents and children’ of the bisection. I think MichaelE2 is better answer. You could modify NestList to get your output. I’ll let you play with that. That’s part of the fun: more than one way to achieve your aim. Sep 9 '21 at 20:49

This reproduces the OP's example, and being a term-rewriting method, it seems a fitting Mathematica solution:

list = {CharacterRange["a", "j"]};
process = Print; (* hook to process each subdivision *)
Module[{stop},
bisect = {
{x_} :> stop[x],
L_List :>
Sequence @@ ((process[#]; #) &) /@ TakeDrop[L, Floor[Length@L/2]]
};
stop @@ list //. bisect /. {stop -> List}
]


Here's one way to transform a list of elements into a list of lists each of which contains a single element of the list we start with. First, a little list to play with:

list1 = Range[15]


and now a bit of Mathematica

Map[List,list1]


which produces the result

{{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11},{12},{13},{14},{15}}


Not a bisection in sight but possibly the result you seek and written in Mathematica, not in Python.

I've not answered your question at all, but then your question seems to me to be seeking advice on how to write Python in Mathematica. The best response I can offer to that question is simply Don't, instead learn how to achieve the results you want in the Mathematica way using Mathematica's built in functions of which there are very many.

Furthermore, many of us work quite hard to avoid Do (or For) loops - Alternatives to procedural loops and iterating over lists in Mathematica - and would use different approaches to controlling recursive operations.

And I see that someone else has shown you how you might bisect a list as you originally requested so I'll write no more.