Python recursive bisection algorithm to Mathematica

Question

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.

Thank you in advance!

// 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!

Answer 1

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:

Answer 2

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}
 ]

Answer 3

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.